Special Issue Selected Papers from CIAA2002No Access

NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

MARKUS HOLZER

Institut für Informatik, Technische Universität München, Boltzmannstraße 3, D-85748 Garching bei München, Germany

Search for more papers by this author

and

MARTIN KUTRIB

Institut für Informatik, Universität Giessen, Arndtstraße 2, D-35392 Giessen, Germany

Search for more papers by this author

https://doi.org/10.1142/S0129054103002199Cited by:112 (Source: Crossref)

Abstract

We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operations – concatenation, iteration, λ-free iteration – and the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. Otherwise tight bounds in the order of magnitude are shown.

Keywords:

References

P. Berman, and A. Lingas, "On the complexity of regular languages in terms of finite automata," Technical Report 304, Polish Academy of Sciences, 1977 . Google Scholar
J.-C. Birget, Theoret. Comput. Sci. 119, 267 (1993), DOI: 10.1016/0304-3975(93)90160-U. Crossref, Web of Science, Google Scholar
J.-C. Birget, Math. Systems Theory 26, 237 (1993), DOI: 10.1007/BF01371727. Crossref, Google Scholar
J.-C. Birget, Personal communication, October 2002 . Google Scholar
C. Câmpeanuet al., State complexity of basic operations on finite languages, Proc. 4th International Workshop on Implementing Automata (WIA '99) (2001) pp. 60–70. Google Scholar
C. Câmpeanu, N. Sântean and S. Yu, Theoret. Comput. Sci. 267, 3 (2001). Crossref, Web of Science, Google Scholar
M. Chrobak, Theoret. Comput. Sci. 47, 149 (1986), DOI: 10.1016/0304-3975(86)90142-8. Crossref, Web of Science, Google Scholar
J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Language, and Computation ( Addison-Wesley , Reading, Massachusetts , 1979 ) . Google Scholar
H. B. Hunt, D. J. Rosenkrantz and T. G. Szymanski, J. Comput. System Sci. 12, 222 (1976). Crossref, Web of Science, Google Scholar
T. Jiang and B. Ravikumar, SIAM J. Comput. 22, 1117 (1993), DOI: 10.1137/0222067. Crossref, Web of Science, Google Scholar
E. Landau, Archiv der Math., und Phys. 3, 92 (1903). Web of Science, Google Scholar
E. Landau , Handbuch der Lehre von der Verteilung der Primzahlen ( Teubner , Leipzig , 1909 ) . Google Scholar
E. Leiss, Theoret. Comput. Sci. 13, 323 (1981), DOI: 10.1016/S0304-3975(81)80005-9. Crossref, Web of Science, Google Scholar
C. Mereghetti and G. Pighizzini, J. Aut. Lang., and Comb. 5, 287 (2000). Web of Science, Google Scholar
C. Mereghetti and G. Pighizzini, SIAM J. Comput. 30, 1976 (2001), DOI: 10.1137/S009753979935431X. Crossref, Web of Science, Google Scholar
A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars, and formal systems, Proc. 12th Annual IEEE Symposium on Switching and Automata Theory pp. 188–191. Google Scholar
C. Nicaud, Average state complexity of operations on unary automata, Proc. Mathematical Foundations of Computer Science (MFCS '99) (1999) pp. 231–240. Google Scholar
G. Pighizzini and J. O. Shallit, Int. J. Found. Comput. Sci. 13, 145 (2002), DOI: 10.1142/S012905410200100X. Link, Web of Science, Google Scholar
W. J. Sakoda and M. Sipser, Nondeterminism and the size of two way finite automata, Proc. 10th Annual ACM Symposium on Theory of Computing (STOC '78) pp. 275–286. Google Scholar
K. Salomaa and S. Yu, J. Aut., Lang., and Comb. 2, 177 (1997). Google Scholar
J. O. Shallit and K. Ellul, Personal communication, October 2002 . Google Scholar
S. Sipser, J. Comput. System Sci. 21, 195 (1980), DOI: 10.1016/0022-0000(80)90034-3. Crossref, Web of Science, Google Scholar
L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time, Proc. 5th Annual ACM Symposium on Theory of Computing (STOC '73) pp. 1–9. Google Scholar
M. Szalay, Acta Arithm. 37, 321 (1980). Crossref, Google Scholar
S. Yu, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer, Berlin, 1997) pp. 41–110. Crossref, Google Scholar
S. Yu, J. Aut. Lang. and Comb. 6, 221 (2001). Web of Science, Google Scholar
S. Yu, Bull. EATCS 76, 142 (2002). Google Scholar
S. Yu, Q. Zhuang and K. Salomaa, Theoret. Comput. Sci. 125, 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, Web of Science, Google Scholar