Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages

• Autorzy: Han Y-S. , Salomaa K. , Wood D.
• Języki publikacji: EN

Abstrakty

EN

We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.

Słowa kluczowe

EN

prefix-freeness; regular language; nondeterministic state complexity; descriptional complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 1-2
• Strony: 93--106
• Opis fizyczny: bibliogr. 27 poz.

Twórcy

autor

Han Y-S.

autor

Salomaa K.

autor

Wood D.

• Intelligence and Interaction Research Center, Korea Institute of Science and Technology P.O.BOX 131, Cheongryang, Seoul, Korea,

Bibliografia

• [1] J. Berstel and D. Perrin. Theory of Codes. Academic Press, Inc., 1985.
• [2] C. Câmpeanu, K. Culik II, K. Salomaa, and S. Yu. State complexity of basic operations on finite languages. In Proceedings of WIA-99, Lecture Notes in Computer Science 2214, 60-70, 2001.
• [3] C. Câmpeanu, K. Salomaa, and S. Yu. Tight lower bound for the state complexity of shuffle of regular languages. Journal of Automata, Languages and Combinatorics, 7(3):303-310, 2002.
• [4] M. Domaratzki. State complexity of proportional removals. Journal of Automata, Languages and Combinatorics, 7(4):455-468, 2002.
• [5] Y. Gao, K. Salomaa, and S. Yu. The state complexity of two combined operations: Star of catenation and star of reversal. Fundamenta Informaticae, 83(1-2):75-89, 2008.
• [6] D. Giammarresi and R. Montalbano. Deterministic generalized automata. Theoretical Computer Science, 215:191-208, 1999.
• [7] I. Glaister and J. Shallit. A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters, 59(2):75-77, 1996.
• [8] Y.-S. Han and K. Salomaa. State complexity of basic operations on suffix-free regular languages. In Proceedings of MFCS-07, Lecture Notes in Computer Science 4708, 501-512, 2007.
• [9] Y.-S. Han and K. Salomaa. State complexity of union and intersection of finite languages. International Journal of Foundations of Computer Science, 19(3):581-595, 2008.
• [10] Y.-S. Han, K. Salomaa, and D. Wood. State complexity of prefix-free regular languages. In Proceedings of DCFS-06, 165-176, 2006. Full version is submitted for publication.
• [11] Y.-S. Han, Y.Wang, and D.Wood. Prefix-free regular languages and pattern matching. Theoretical Computer Science, 389(1-2):307-317, 2007.
• [12] Y.-S. Han and D. Wood. The generalization of generalized automata: Expression automata. International Journal of Foundations of Computer Science, 16(3):499-510, 2005.
• [13] M. Holzer and M. Kutrib. Nondeterministic descriptional complexity of regular languages. International Journal of Foundations of Computer Science, 14(6):1087-1102, 2003.
• [14] J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 2 edition, 1979.
• [15] T. Jiang and B. Ravikumar. MinimalNFA problems are hard. SIAMJournal on Computing, 22(6):1117-1141, 1993.
• [16] J. Jirásek, G. Jirásková, and A. Szabari. State complexity of concatenation and complementation. International Journal of Foundations of Computer Science, 16(3):511-529, 2005.
• [17] G. Jirásková. State complexity of some operations on binary regular languages. Theoretical Computer Science, 330(2):287-298, 2005.
• [18] H. Jürgensen and S. Konstantinidis. Codes. In G. Rozenberg and A. Salomaa, editors, Word, Language, Grammar, volume 1 of Handbook of Formal Languages, 511-607. Springer-Verlag, 1997.
• [19] A. R. Meyer and M. J. Fischer. Economy of description by automata, grammars, and formal systems. In Proceedings of the Twelfth Annual IEEE Symposium on Switching and Automata Theory, 188-191, 1971.
• [20] G. Pighizzini and J. Shallit. Unary language operations, state complexity and Jacobsthal-s function. International Journal of Foundations of Computer Science, 13(1):145-159, 2002.
• [21] A. Salomaa, K. Salomaa, and S. Yu. State complexity of combined operations. Theoretical Computer Science, 383(2-3):140-152, 2007.
• [22] A. Salomaa, D. Wood, and S. Yu. On the state complexity of reversals of regular languages. Theoretical Computer Science, 320(2-3):315-329, 2004.
• [23] K. Salomaa and S. Yu. NFA to DFA transformation for finite languages over arbitrary alphabets. Journal of Automata, Languages and Combinatorics, 2(3):177-186, 1998.
• [24] D. Wood. Theory of Computation. JohnWiley & Sons, Inc., New York, NY, 1987.
• [25] S. Yu. State complexity of regular languages. Journal of Automata, Languages and Combinatorics, 6(2):221-234, 2001.
• [26] S. Yu. On the state complexity of combined operations. In Proceeding of CIAA-06, Lecture Notes in Computer Science 4094, 11-22, 2006.
• [27] S. Yu, Q. Zhuang, and K. Salomaa. The state complexities of some basic operations on regular languages. Theoretical Computer Science, 125(2):315-328, 1994.