Distance desert automata and the star height problem

Kirsten, Daniel

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3, pp. 455-509.

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in $2^{2^{𝒪\left(n\right)}}$ space whether the language accepted by an $n$-state non-deterministic automaton is of a star height less than a given integer $h$ (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound for the star height problem.

Classification : 20M35, 68Q17, 68Q70
Mots clés : recognizable languages, star height, distance automata

[1] S. Bala, Regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms, in STACS'04 Proceedings, edited by V. Diekert and M. Habib, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2996 (2004) 596-607. | Zbl

[2] J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979). | MR | Zbl

[3] R.S. Cohen, Star height of certain families of regular events. J. Comput. Syst. Sci. 4 (1970) 281-297. | Zbl

[4] K. Culik Ii and J. Kari, Image compression using weighted finite automata. Computer Graphics 17 (1993) 305-313.

[5] F. Dejean and M. Schützenberger, On a question of Eggan. Inform. Control 9 (1966) 23-25. | Zbl

[6] L.C. Eggan, Transition graphs and the star height of regular events. Michigan Math. J. 10 (1963) 385-397. | Zbl

[7] S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, New York (1974). | MR | Zbl

[8] G. Grahne and A. Thomo, Approximate reasoning in semi-structured databases, in 8th International Workshop on Knowledge Representation meets Databases (KRDB2001), edited by M. Lenzerini et al., CEUR Workshop Proceedings 45 (2001).

[9] P.A. Grillet, Semigroups: An Introduction to the Structure Theory, Marcel Dekker, Inc., New York. Monographs and Textbooks in Pure and Applied Mathematics 193 (1995). | MR | Zbl

[10] K. Hashiguchi, Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci. 24 (1982) 233-244. | Zbl

[11] K. Hashiguchi, Regular languages of star height one. Inform. Control 53 (1982) 199-210. | Zbl

[12] K. Hashiguchi, Representation theorems of regular languages. J. Comput. Syst. Sci. 27 (1983) 101-115. | Zbl

[13] K. Hashiguchi, Algorithms for determining relative star height and star height. Inform. Comput. 78 (1988) 124-169. | Zbl

[14] K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions. Theor. Comput. Sci. 72 (1990) 27-38. | Zbl

[15] K. Hashiguchi, New upper bounds to the limitedness of distance automata, in ICALP'96 Proceedings, edited by F. Meyer auf der Heide and B. Monien, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 1099 (1996) 324-335. | Zbl

[16] K. Hashiguchi, New upper bounds to the limitedness of distance automata. Theor. Comput. Sci. 233 (2000) 19-32. | Zbl

[17] K. Hashiguchi, Erratum to “New upper bounds to the limitedness of distance automata”. Theor. Comput. Sci. 290 (2003) 2183-2184. | Zbl

[18] K. Hashiguchi and N. Honda, Homomorphisms that preserve star height. Inform. Control 30 (1976) 247-266. | Zbl

[19] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory Languages, and Computation. Addison-Wesley, Reading (1979). | MR | Zbl

[20] F. Katritzke, Refinements of Data Compression using Weighted Finite Automata. Ph.D. Thesis, Universität Siegen (2001).

[21] D. Kirsten, A Burnside approach to the finite substitution problem. Theory Comput. Syst. (to appear). | MR | Zbl

[22] D. Kirsten, Desert automata and the finite substitution problem, in STACS'04 Proceedings, edited by V. Diekert and M. Habib, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2996 (2004). 305-316. | Zbl

[23] D. Kirsten, Distance desert automata and the star height one problem, in FoSSaCS'04 Proceedings, edited by I. Walukiewicz, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2987 (2004) 257-272. | Zbl

[24] D. Kirsten and J. Marcinkowski, Two techniques in the area of the star problem in trace monoids. Theor. Comput. Sci. 309 (2003) 381-412. | Zbl

[25] D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Internat. J. Algebra Comput. 4 (1994) 405-425. | Zbl

[26] G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons, New York (1979). | MR | Zbl

[27] H. Leung, An Algebraic Method for Solving Decision Problems in Finite Automata Theory. Ph.D. Thesis, Pennsylvania State University, Department of Computer Science (1987).

[28] H. Leung, On the topological structure of a finitely generated semigroup of matrices. Semigroup Forum 37 (1988) 273-287. | Zbl

[29] H. Leung, Limitedness theorem on finite automata with distance functions: An algebraic proof. Theor. Comput. Sci. 81 (1991) 137-145. | Zbl

[30] H. Leung, On some decision problems in finite automata, in Monoids and Semigroups with Applications, edited by J. Rhodes, World Scientific, Singapore (1991) 509-526. | Zbl

[31] H. Leung, On finite automata with limited nondeterminism. Acta Inform. 35 (1998) 595-624. | Zbl

[32] H. Leung, The topological approach to the limitedness problem on distance automata, in Idempotency, edited by J. Gunawardena, Cambridge University Press (1998) 88-111. | Zbl

[33] H. Leung and V. Podolskiy, The limitedness problem on distance automata: Hashiguchi's method revisited. Theor. Comput. Sci. 310 (2004) 147-158. | Zbl

[34] S. Lombardy, Approche structurelle de quelques problèmes de la théorie des automates. Ph.D. Thesis, École nationale supérieure des télécommunications, Paris (2001).

[35] S. Lombardy and J. Sakarovitch, On the star height of rational languages. A new proof for two old results, in Proc. of the 3rd Int. Conf. on Languages, Words and Combinatorics, Kyoto'00 edited by M. Ito, World Scientific (2000).

[36] S. Lombardy and J. Sakarovitch, Star height of reversible languages and universal automata, in LATIN'02 Proceedings, Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 2286 (2002) 76-89. | Zbl

[37] Y. Métivier and G. Richomme. New results on the star problem in trace monoids. Inform. Comput. 119 (1995) 240-251. | Zbl

[38] M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguistics 23 (1997) 269-311.

[39] R. Montalbano and A. Restivo, On the star height of rational languages. Internat. J. Algebra Comput. 4 (1994) 427-441. | Zbl

[40] D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B (1990) 1-57. | Zbl

[41] J.-É. Pin, Varieties of Formal Languages. North Oxford Academic Publishers Ltd (1986). | MR | Zbl

[42] J.-É. Pin, Rational and recognizable langages, in Lect. Appl. Math. Inform. edited by Ricciardi, Manchester University Press (1990) 62-106. | Zbl

[43] J.-É. Pin, Finite semigroups and recognizable languages: An introduction, in NATO Advanced Study Institute, Semigroups, Formal Languages and Groups, edited by J. Fountain, Kluwer Academic Publishers (1995) 1-32. | Zbl

[44] J.-É. Pin, Syntactic semigroups, in Handbook of Formal Languages, Vol. 1, Word, Language, Grammar, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin (1997) 679-746.

[45] J.-É. Pin, Tropical semirings, in Idempotency, edited by J. Gunawardena, Cambridge University Press (1998) 50-69. | Zbl

[46] I. Simon, Limited subsets of a free monoid, in Proc. of the 19th IEEE Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Long Beach, CA (1978) 143-150.

[47] I. Simon, Recognizable sets with multiplicities in the tropical semiring, in MFCS'88 Proceedings, edited by M.P. Chytil et al., Springer-Verlag, Berlin. Lect. Notes Comput. Sci. 324 (1988) 107-120. | Zbl

[48] I. Simon, The nondeterministic complexity of a finite automaton, in Mots - mélanges offerts à M.P. Schützenberger, edited by M. Lothaire, Hermes (1990) 384-400.

[49] I. Simon, On semigroups of matrices over the tropical semiring. RAIRO-Inf. Theor. Appl. 28 (1994) 277-294. | Numdam | Zbl

[50] A. Weber, Distance automata having large finite distance or finite ambiguity. Math. Syst. Theor. 26 (1993) 169-185. | Zbl

[51] A. Weber, Finite valued distance automata. Theor. Comput. Sci. 134 (1994) 225-251. | Zbl

[52] S. Yu, Regular Languages, in Handbook of Formal Languages, Vol. 1, Word, Language, Grammar, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin (1997) 41-110.