State Complexity : Recent Results and Open Problems

• Autorzy: Yu S
• Języki publikacji: EN

Abstrakty

EN

In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.

Słowa kluczowe

EN

state complexity; regular language; finite language; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 471--480
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Yu S

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada,

Bibliografia

• [1] J.-C. Birget, Intersection and union of regular languages and state complexity, Information Processing Letters, 43 (1992), 185–190.
• [2] J.-C. Birget, Partial orders on words, minimal elements of regular languages, and state complexity, Theoretical Computer Science, 119 (1993), 267–291.
• [3] A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.T. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40 (1985), 31–55.
• [4] J.A. Brzozowski, Canonical regular expressions and minimal state graphs for definite events, Mathematical theory of Automata, Vol. 12 of MRI Symposia Series, Polytechnic Press, Polytechnic Institute of Brooklyn, NY (1962), 529–561.
• [5] C. Campeanu, K. Culik, K. Salomaa, S. Yu, State complexity of basic operations on finite languages, Proceedings of the Fourth International Workshop on Implementing Automata VIII 1-11, 1999, LNCS 2214, 60–70.
• [6] C. Campeanu, K. Salomaa, S. Yu, Tight lower bound for the state complexity of shuffle of regular languages, Journal of Automata, Languages and Combinatorics, 7, 3 (2002), 303–310.
• [7] C. Campeanu, K. Salomaa, S. Yu, State complexity of regular languages: Finite versus infinite, in Finite vs Infinite – Contributions to an Eternal Dilemma, edited by C. Calude and G. Paun, Springer, 2000, 53–73.
• [8] M. Domaratzki, State complexity and proportional removals, Journal of Automata, Languages and Combinatorics, 7 (2002), 455–468.
• [9] M. Holzer and M. Kutrib, State complexity of basic operations on nondeterministic finite automata, Proceedings of International Conference on Implementation and Application of Automata 2002 (CIAA 2002), Springer, LNCS 2608, 148–157.
• [10] M. Holzer and M. Kutrib, Unary language operations and their nondeterministic state complexity, Developments in Language Theory (DLT 2002), Springer, LNCS 2450, 162–172.
• [11] M. Holzer, K. Salomaa, S. Yu, On the state complexity of k-entry deterministic finite automata, Journal of Automata, Languages and Combinatorics, 6, 4 (2001), 453–466.
• [12] J.E. Hopcroft, An n log n algorithm for minimizing states in a finite automaton, in Theory of Machines and Computations, Z. Kohavi edited, Academic Press, New York, 1971.
• [13] K. Iwama, Y. Kambayashi, and K. Takaki, Tight bounds on the number of states of DFAs that are equivalent to-state NFAs, Theoretical Computer Science, 237 (2000), 485–494.
• [14] G. Jirásková, State complexity of some operations on regular languages, Proceedings of 5th Workshop on Descriptional Complexity of Formal Systems, 2003, 114–125.
• [15] G. Jirásková, State complexity of some operations on binary regular languages, Theoretical Computer Science, to appear.
• [16] G. Jirásková and A. Szabari, State complexity of the concatenation and complementation of regular languages, to appear in CIAA 2004.
• [17] G. A. Kiraz, Compressed storage of sparse finite-state transducers, Proceedings of CIAA 2001, Springer LNCS 2214, (2001), 109–121.
• [18] E. Leiss, Succinct representation of regular languages by boolean automata, Theoretical Computer Science, 13 (1981), 323–330.
• [19] S. Marcus, Gramatici si automate finite (Finite Grammars and Automata), Ed Academiei (the Publishing House of the Romanian Academy), Bucharest, 1964.
• [20] A.R. Meyer and M.J. Fischer, Economy of description by automata, grammars, and formal systems, Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971, 188–191.
• [21] F. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Trans. Comput., C-20 (1971), 1211–1214.
• [22] C. Nicaud, Average state complexity of operations on unary automata, MFCS’99, Springer, LNCS 1672 (1999), 231–240.
• [23] G. Pighizzini and J. Shallit, Unary language operations, state complexity and Jacobsthal’s function, International Journal of Foundations of Computer Science, 13, 1 (2002), 145–159.
• [24] M. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Dev., 3 (1959), 114–125.
• [25] A. Salomaa, On the Reducibility of Events Represented in Automata, Annales Academiae Scientiarum Fennicae, Series A, I. Mathematica 353, 1964.
• [26] A. Salomaa, Theorems on the Representation of events in Moore-Automata, Turun Yliopiston Julkaisuja Annales Universitatis Turkuensis, Series A, 69, 1964.
• [27] A. Salomaa, Theory of Automata, Pergamon Press (1969), Oxford.
• [28] A. Salomaa, D. Wood, and S. Yu, On the state complexity of reversals of regular languages, Theoretical Computer Science, 320 (2004), 293–313.
• [29] K. Salomaa and S. Yu, NFA to DFA transformation for finite languages over arbitrary alphabets, Journal of Automata, Languages and Combinatorics, 2, 3 (1997), 177–186.
• [30] J. Shallit, Private communication, 2003.
• [31] S. Yu, Regular languages, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer, 1998, 41–110.
• [32] S. Yu, State complexity of regular languages, Journal of Automata, Languages and Combinatorics, 6, 2 (2001), 221–234.
• [33] S. Yu and Q. Zhuang, On the state complexity of intersection of regular languages, ACM SIGACT News, 22, 3 (1991), 52–54.
• [34] S. Yu, Q. Zhuang, and K. Salomaa, On the state complexity of some basic operations on regular languages, Theoretical Computer Science, 125 (1994), 315–328.