State complexity of union and intersection for two-way nondeterministic finite automata

Michal Kunc, Alexander Okhotin

Research output

6 Citations (Scopus)

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 = p1 +⋯+ pk and n = q1 +⋯+ql, where all numbers p1,⋯ , pk, q1,⋯ , ql ≥ 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 languageEnglish
Pages (from-to)231-239
Number of pages9
JournalFundamenta Informaticae
Volume110
Issue number1-4
DOIs
Publication statusPublished - 20 Sep 2011

Scopus subject areas

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

Fingerprint Dive into the research topics of 'State complexity of union and intersection for two-way nondeterministic finite automata'. Together they form a unique fingerprint.

Cite this