Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2011

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: partitions into sums of primes

Sortuj według:

Ogranicz wyniki do:

State Complexity of Union and Intersection for Two-Way Nondeterministic Finite Automata

Kunc M., Okhotin A.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

231-239

The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent the 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≈6 (and with finitely many other exceptions), there exist partitionsm = 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 fewmore exceptions) into sums of pairwise distinct primes is established as well. Keywords: Finite automata, two-way automata, state complexity, partitions into sums of primes.