Distance desert automata and the star height problem
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3 , p. 455-509
doi : 10.1051/ita:2005027
URL stable : http://www.numdam.org/item?id=ITA_2005__39_3_455_0

Classification:  20M35,  68Q17,  68Q70
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.

### Bibliographie

[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 1122.68462

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

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

[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 0209.02903

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

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

[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 1350793 | Zbl 0830.20079

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

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

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

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

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

[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 1046.68568

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

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

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

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

[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 2189557 | Zbl 1102.68498

[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 1122.68467

[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 1126.68455

[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 1106.68371

[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 0834.68058

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

[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 0646.20056

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

[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 0796.20062

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

[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 0898.68049

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

[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 1059.68065

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

[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 0823.68050

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

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

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

[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 0872.20053

[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 0909.16028

[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 0656.68086

[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 0888.68086

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

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

[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.