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

• Autorzy: Kunc M. , Okhotin A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

finite automata; two-way automata; state complexity; partitions into sums of primes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 231--239
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Kunc M.

autor

Okhotin A.

• Department of Mathematics, Masaryk University, Brno 61137, Czech Republic,

Bibliografia

• [1] P. Berman, A. Lingas, "On complexity of regular languages in terms of finite automata", Report 304, Institute of Computer Science, Polish Academy of Sciences, Warsaw, 1977.
• [2] M. Chrobak, "Finite automata and unary languages", Theoretical Computer Science, 47 (1986), 149-158. Errata: 302 (2003), 497-498.
• [3] V. Geffert, C. Mereghetti, G. Pighizzini, "Converting two-way nondeterministic unary automata into simpler automata", Theoretical Computer Science, 295:1-3 (2003), 189-203.
• [4] V. Geffert, C. Mereghetti, G. Pighizzini, "Complementing two-way finite automata", Information and Computation, 205:8 (2007), 1173-1187.
• [5] M. Holzer,M. Kutrib, "Nondeterministic descriptional complexity of regular languages", International Journal of Foundations of Computer Science, 14 (2003), 1087-1102.
• [6] G. Jirásková, A. Okhotin, "On the state complexity of operations on two-way finite automata", Developments in Language Theory (DLT 2008, Kyoto, Japan, 16-19 September, 2008), LNCS 5257, 443-454.
• [7] C. A. Kapoutsis, "Removing bidirectionality from nondeterministic finite automata", Mathematical Foundations of Computer Science (MFCS 2005, Gdańsk, Poland, August 29-September 2, 2005), LNCS 3618, 544-555.
• [8] C. A. Kapoutsis, "Two-way automata versus logarithmic space", Computer Science in Russia (CSR 2011, St. Petersburg, Russia, 14-18 June 2011), LNCS 6651, 359-372.
• [9] M. Kunc, A. Okhotin, "Describing periodicity in two-way deterministic finite automata using transformation semigroups", Developments in Language Theory (DLT 2011, Milan, Italy, 19-22 July 2011), LNCS 6795, 324-336.
• [10] M. Kunc, A. Okhotin, "State complexity of operations on two-way deterministic finite automata over a unary alphabet", Descriptional Complexity of Formal Systems (DCFS 2011, Limburg, Germany, 25-27 July 2011), LNCS 6808, 222-234.
• [11] E. Landau, "¨Uber die Maximalordnung der Permutationen gegebenen Grades" (On the maximal order of permutations of a given degree), Archiv der Mathematik und Physik, Ser. 3, 5 (1903), 92-103.
• [12] Yu. Lyubich, "Bounds for the optimal determinization of nondeterministic autonomic automata", Sibirskii Matematicheskii Zhurnal, 2 (1964), 337-355, in Russian.
• [13] A. N.Maslov, "Estimates of the number of states of finite automata", SovietMathematics Doklady, 11 (1970), 1373-1375.
• [14] C. Mereghetti, G. Pighizzini, "Optimal simulations between unary automata", SIAM Journal on Computing, 30:6 (2001), 1976-1992.
• [15] C. Mereghetti, G. Pighizzini, "Two-way automata simulations and unary languages", Journal of Automata, Languages and Combinatorics, 5:3 (2000), 287-300.
• [16] F. R. Moore, "On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata", IEEE Transactions on Computers, 20 (1971), 1211-1214.
• [17] J. Nagura, "On the interval containing at least one prime number", Proceedings of the Japan Academy, Ser. A, 28:4 (1952), 177-181.
• [18] A. Okhotin, "Unambiguous finite automata over a unary alphabet", Mathematical Foundations of Computer Science (MFCS 2010, Brno, Czech Republic, 23-27 August 2010), LNCS 6281, 556-567.
• [19] M. O. Rabin, D. Scott, "Finite automata and their decision problems", IBM Journal of Research and Development, 3 (1959), 114-125.
• [20] B. Ravikumar, O. H. Ibarra, "Relating the type of ambiguity of finite automata to the succinctness of their representation", SIAM Journal on Computing, 18:6 (1989), 1263-1282.
• [21] H.-E. Richert, "¨Uber Zerfällung in ungleiche Primzahlen", Mathematische Zeitschrift, 52 (1950), 342-343.
• [22] W. J. Sakoda, M. Sipser, "Nondeterminism and the size of two way finite automata", STOC 1978, 275-286.
• [23] J. C. Shepherdson, "The reduction of two-way automata to one-way automata", IBM Journal of Research and Development, 3 (1959), 198-200.
• [24] M. Vardi, "A note on the reduction of two-way automata to one-way automata", Information Processing Letters, 30:5 (1989), 261-264.
• [25] S. Yu, Q. Zhuang, K. Salomaa, "The state complexity of some basic operations on regular languages", Theoretical Computer Science, 125 (1994), 315-328.