# Distance desert automata and the star height problem

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 39, Issue: 3, page 455-509
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKirsten, Daniel. "Distance desert automata and the star height problem." RAIRO - Theoretical Informatics and Applications 39.3 (2010): 455-509. <http://eudml.org/doc/92776>.

@article{Kirsten2010,

abstract = {
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 22O(n) 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.
},

author = {Kirsten, Daniel},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Recognizable languages; star height; distance automata.; recognizable languages; star heights; distance automata; desert automata; hierarchies; decidability; star height problem; free monoids},

language = {eng},

month = {3},

number = {3},

pages = {455-509},

publisher = {EDP Sciences},

title = {Distance desert automata and the star height problem},

url = {http://eudml.org/doc/92776},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Kirsten, Daniel

TI - Distance desert automata and the star height problem

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 3

SP - 455

EP - 509

AB -
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 22O(n) 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.

LA - eng

KW - Recognizable languages; star height; distance automata.; recognizable languages; star heights; distance automata; desert automata; hierarchies; decidability; star height problem; free monoids

UR - http://eudml.org/doc/92776

ER -

## References

top- 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.
- J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979).
- R.S. Cohen, Star height of certain families of regular events. J. Comput. Syst. Sci.4 (1970) 281–297.
- K. Culik II and J. Kari, Image compression using weighted finite automata. Computer Graphics17 (1993) 305–313.
- F. Dejean and M. Schützenberger, On a question of Eggan. Inform. Control9 (1966) 23–25.
- L.C. Eggan, Transition graphs and the star height of regular events. Michigan Math. J.10 (1963) 385–397.
- S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, New York (1974).
- 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 Proceedings45 (2001).
- P.A. Grillet, Semigroups: An Introduction to the Structure Theory, Marcel Dekker, Inc., New York. Monographs and Textbooks in Pure and Applied Mathematics193 (1995).
- K. Hashiguchi, Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci.24 (1982) 233–244.
- K. Hashiguchi, Regular languages of star height one. Inform. Control53 (1982) 199–210.
- K. Hashiguchi, Representation theorems of regular languages. J. Comput. Syst. Sci.27 (1983) 101–115.
- K. Hashiguchi, Algorithms for determining relative star height and star height. Inform. Comput.78 (1988) 124–169.
- K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions. Theor. Comput. Sci.72 (1990) 27–38.
- 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.
- K. Hashiguchi, New upper bounds to the limitedness of distance automata. Theor. Comput. Sci.233 (2000) 19–32.
- K. Hashiguchi, Erratum to “New upper bounds to the limitedness of distance automata”. Theor. Comput. Sci.290 (2003) 2183–2184.
- K. Hashiguchi and N. Honda, Homomorphisms that preserve star height. Inform. Control30 (1976) 247–266.
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory Languages, and Computation. Addison-Wesley, Reading (1979).
- F. Katritzke, Refinements of Data Compression using Weighted Finite Automata. Ph.D. Thesis, Universität Siegen (2001).
- D. Kirsten, A Burnside approach to the finite substitution problem. Theory Comput. Syst. (to appear).
- 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.
- 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.
- D. Kirsten and J. Marcinkowski, Two techniques in the area of the star problem in trace monoids. Theor. Comput. Sci.309 (2003) 381–412.
- D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Internat. J. Algebra Comput.4 (1994) 405–425.
- G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons, New York (1979).
- H. Leung, An Algebraic Method for Solving Decision Problems in Finite Automata Theory. Ph.D. Thesis, Pennsylvania State University, Department of Computer Science (1987).
- H. Leung, On the topological structure of a finitely generated semigroup of matrices. Semigroup Forum37 (1988) 273–287.
- H. Leung, Limitedness theorem on finite automata with distance functions: An algebraic proof. Theor. Comput. Sci.81 (1991) 137–145.
- 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.
- H. Leung, On finite automata with limited nondeterminism. Acta Inform.35 (1998) 595–624.
- H. Leung, The topological approach to the limitedness problem on distance automata, in Idempotency, edited by J. Gunawardena, Cambridge University Press (1998) 88–111.
- H. Leung and V. Podolskiy, The limitedness problem on distance automata: Hashiguchi's method revisited. Theor. Comput. Sci.310 (2004) 147–158.
- 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).
- 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).
- 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.
- Y. Métivier and G. Richomme. New results on the star problem in trace monoids. Inform. Comput.119 (1995) 240–251.
- M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguistics23 (1997) 269–311.
- R. Montalbano and A. Restivo, On the star height of rational languages. Internat. J. Algebra Comput.4 (1994) 427–441.
- D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B (1990) 1–57.
- J.-É. Pin, Varieties of Formal Languages. North Oxford Academic Publishers Ltd (1986).
- J.-É. Pin, Rational and recognizable langages, in Lect. Appl. Math. Inform. edited by Ricciardi, Manchester University Press (1990) 62–106.
- 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.
- 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.
- J.-É. Pin, Tropical semirings, in Idempotency, edited by J. Gunawardena, Cambridge University Press (1998) 50–69.
- 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.
- 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.
- 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.
- I. Simon, On semigroups of matrices over the tropical semiring. RAIRO-Inf. Theor. Appl.28 (1994) 277–294.
- A. Weber, Distance automata having large finite distance or finite ambiguity. Math. Syst. Theor.26 (1993) 169–185.
- A. Weber, Finite valued distance automata. Theor. Comput. Sci.134 (1994) 225–251.
- 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.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.