## Abstract

The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m+n and at most m+n+1. For the union operation, the number of states is exactly m+n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n ≥ 2 with m, n ≠ 6 (and with finitely many other exceptions), there exist partitions m = p_{1} +⋯+ p_{k} and n = q_{1} +⋯+q_{l}, where all numbers p_{1},⋯ , p_{k}, q_{1},⋯ , q_{l} ≥ 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n ∉ {4, 6} (with a few more exceptions) into sums of pairwise distinct primes is established as well.

Original language | English |
---|---|

Pages (from-to) | 231-239 |

Number of pages | 9 |

Journal | Fundamenta Informaticae |

Volume | 110 |

Issue number | 1-4 |

DOIs | |

Publication status | Published - 20 Sep 2011 |

## Scopus subject areas

- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics