State Complexity of Basic Operations on Non-Returning Regular Languages

• Autorzy: Eom H.-S. , Han Y.-S. , Jirásková G.

Identyfikatory

DOI

10.3233/FI-2016-1326

• Języki publikacji: EN

Abstrakty

EN

We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reverse, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also study the unary case.

Słowa kluczowe

EN

finite automata; non-returning regular languages; basic operations; state complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 144, nr 2
• Strony: 161--182
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Eom H.-S.

• Department of Computer Science, Yonsei University 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea

autor

Han Y.-S.

• Department of Computer Science, Yonsei University 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea

autor

Jirásková G.

• Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia

Bibliografia

• [1] Maslov AN. Estimates of the number of states of finite automata. Soviet Mathematics Doklady. 1970; 11:1373–1375.
• [2] Yu S, Zhuang Q, Salomaa K. The State Complexities of Some Basic Operations on Regular Languages. Theoretical Computer Science. 1994;125(2):315–328. doi: 10.1016/0304-3975(92)00011-F.
• [3] Yu S. State Complexity of Regular Languages. Journal of Automata, Languages and Combinatorics. 2001; 6(2):221.
• [4] Salomaa A, Wood D, Yu S. On the state complexity of reversals of regular languages. Theoretical Computer Science. 2004;320(2-3):315–329. doi: 10.1016/j.tcs.2004.02.032.
• [5] Câmpeanu C, II KC, Salomaa K, Yu S. State Complexity of Basic Operations on Finite Languages. In: Automata Implementation, 4th International Workshop on Implementing Automata,WIA’99, Potsdam, Germany, July 17-19, Revised Papers; 1999. p.60–70.
• [6] Han Y, Salomaa K. State Complexity of Union and Intersection of Finite Languages. International Journal of Foundations of Computer Science. 2008;19(3):581–595. doi: 10.1142/S0129054108005838.
• [7] Pighizzini G, Shallit J. Unary Language Operations, State Complexity and Jacobsthal’s Function. International Journal of Foundations of Computer Science. 2002;13(1):145–159.
• [8] Holzer M, Kutrib M. Nondeterministic Descriptional Complexity of Regular Languages. International Journal of Foundations of Computer Science. 2003;14(6):1087–1102. doi: 10.1142/S0129054103002199.
• [9] Câmpeanu C, Salomaa K, Yu S. Tight Lower Bound for the State Complexity of Shuffle of Regular Languages. Journal of Automata, Languages and Combinatorics. 2002;7(3):303–310.
• [10] Domaratzki M. State Complexity of Proportional Removals. Journal of Automata, Languages and Combinatorics. 2002;7(4):455–468.
• [11] Domaratzki M, Salomaa K. State Complexity of Shuffle on Trajectories. Journal of Automata, Languages and Combinatorics. 2004;9(2-3):217–232.
• [12] Nicaud C. Average State Complexity of Operations on Unary Automata. In: Mathematical Foundations of Computer Science 1999, 24th International Symposium, MFCS’99, Szklarska Poreba, Poland, September 6-10, Proceedings; 1999. p. 231–240.
• [13] Jirásková G, Okhotin A. State complexity of cyclic shift. RAIRO - Theoretical Informatics and Applications. 2008;42(2):335–360. Available from: http://eudml.org/doc/246037.
• [14] Salomaa A, Salomaa K, Yu S. State complexity of combined operations. Theoretical Computer Science. 2007;383(2-3):140–152. doi: 10.1016/j.tcs.2007.04.015
• [15] Han Y, Salomaa K, Wood D. Operational State Complexity of Prefix-Free Regular Languages. In: Automata, Formal Languages, and Related Topics - Dedicated to Ferenc Gécseg on the occasion of his 70th birthday; 2009. p. 99–115.
• [16] Han Y, Salomaa K. State complexity of basic operations on suffix-free regular languages. Theoretical Computer Science. 2009;410(27-29):2537–2548. doi: 10.1016/j.tcs.2008.12.054
• [17] Berstel J, Perrin D. Theory of Codes. Academic Press, Inc. Orlando; 1985. ISBN: 0120934205.
• [18] Shallit JO. A Second Course in Formal Languages and Automata Theory. Cambridge University Press New York; 2008. ISBN: 0521865727, 9780521865722.
• [19] Wood D. Theory of Computation. John Wiley & Sons, Inc. Boston; 1987. ISBN: 0060472081.
• [20] Yu S. Regular languages. In: Rozenberg G, Salomaa A, editors.Word, Language, Grammar. vol. 1 of Handbook of Formal Languages. Springer-Verlag; 1997. p. 41–110. ISBN: 3-540-60420-0.
• [21] Brzozowski JA. Derivatives of Regular Expressions. Journal of the ACM. 1964;11(4):481–494.
• [22] Brzozowski JA. Quotient Complexity of Regular Languages. Journal of Automata, Languages and Combinatorics. 2010;15(1/2):71–89.
• [23] Jirásková G. State complexity of some operations on binary regular languages. Theoretical Computer Science. 2005;330(2):287–298. doi: 10.1016/j.tcs.2004.04.011.
• [24] Jirásková G, Palmovsk´yM. Kleene Closure and State Complexity. In: Conference on Information Technologies - Applications and Theory, Donovaly, Slovakia, September 11-15, Proceedings; 2013. p. 94–100.
• [25] Jirásková G, Sebej J. Reversal of binary regular languages. Theoretical Computer Science. 2012;449:85–92. doi: 10.1016/j.tcs.2012.05.008.
• [26] Leiss EL. Succint Representation of Regular Languages by Boolean Automata. Theoretical Computer Science. 1981;13:323–330. doi: 10.1016/S0304-3975(81)80005-9.
• [27] Sebej J. Reversal of regular languages and state complexity. In: Conference on Theory and Practice of Information Technologies, ITAT 2010, Hotel Smrekovica, Vĕlká Fatra, Slovak Republic, September 21-25, Proceedings; 2010. p. 47–54.
• [28] Cevorová K. Kleene Star on Unary Regular Languages. In: Descriptional Complexity of Formal Systems - 15th InternationalWorkshop, DCFS 2013, London, ON, Canada, July 22-25, Proceedings; 2013. p. 277–288. doi: 10.1007/978-3-642-39310-5 26.
• [29] Cevorová K. Kleene star on unary non-returning languages. Personal communication. 2014.
• [30] Cmorik R, Jirásková G. Basic Operations on Binary Suffix-Free Languages. In: Mathematical and Engineering Methods in Computer Science - 7th International Doctoral Workshop, MEMICS 2011, Lednice, Czech Republic, October 14-16, Revised Selected Papers; 2011. p. 94–102. doi: 10.1007/978-3-642-25929-6 9.
• [31] Jirásková G, Olejár P. State Complexity of Intersection and Union of Suffix-Free Languages and Descriptional Complexity. In: Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31 - September 1, Proceedings; 2009. p. 151–166.