Distance desert automata and the star height problem

Daniel Kirsten

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Kirsten, 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
  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.  
  2. J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979).  
  3. R.S. Cohen, Star height of certain families of regular events. J. Comput. Syst. Sci.4 (1970) 281–297.  
  4. K. Culik II and J. Kari, Image compression using weighted finite automata. Computer Graphics17 (1993) 305–313.  
  5. F. Dejean and M. Schützenberger, On a question of Eggan. Inform. Control9 (1966) 23–25.  
  6. L.C. Eggan, Transition graphs and the star height of regular events. Michigan Math. J.10 (1963) 385–397.  
  7. S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, New York (1974).  
  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 Proceedings45 (2001).  
  9. P.A. Grillet, Semigroups: An Introduction to the Structure Theory, Marcel Dekker, Inc., New York. Monographs and Textbooks in Pure and Applied Mathematics193 (1995).  
  10. K. Hashiguchi, Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci.24 (1982) 233–244.  
  11. K. Hashiguchi, Regular languages of star height one. Inform. Control53 (1982) 199–210.  
  12. K. Hashiguchi, Representation theorems of regular languages. J. Comput. Syst. Sci.27 (1983) 101–115.  
  13. K. Hashiguchi, Algorithms for determining relative star height and star height. Inform. Comput.78 (1988) 124–169.  
  14. K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions. Theor. Comput. Sci.72 (1990) 27–38.  
  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.  
  16. K. Hashiguchi, New upper bounds to the limitedness of distance automata. Theor. Comput. Sci.233 (2000) 19–32.  
  17. K. Hashiguchi, Erratum to “New upper bounds to the limitedness of distance automata”. Theor. Comput. Sci.290 (2003) 2183–2184.  
  18. K. Hashiguchi and N. Honda, Homomorphisms that preserve star height. Inform. Control30 (1976) 247–266.  
  19. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory Languages, and Computation. Addison-Wesley, Reading (1979).  
  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).  
  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.  
  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.  
  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.  
  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.  
  26. G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons, New York (1979).  
  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 Forum37 (1988) 273–287.  
  29. H. Leung, Limitedness theorem on finite automata with distance functions: An algebraic proof. Theor. Comput. Sci.81 (1991) 137–145.  
  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.  
  31. H. Leung, On finite automata with limited nondeterminism. Acta Inform.35 (1998) 595–624.  
  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.  
  33. H. Leung and V. Podolskiy, The limitedness problem on distance automata: Hashiguchi's method revisited. Theor. Comput. Sci.310 (2004) 147–158.  
  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.  
  37. Y. Métivier and G. Richomme. New results on the star problem in trace monoids. Inform. Comput.119 (1995) 240–251.  
  38. M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguistics23 (1997) 269–311.  
  39. R. Montalbano and A. Restivo, On the star height of rational languages. Internat. J. Algebra Comput.4 (1994) 427–441.  
  40. D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B (1990) 1–57.  
  41. J.-É. Pin, Varieties of Formal Languages. North Oxford Academic Publishers Ltd (1986).  
  42. J.-É. Pin, Rational and recognizable langages, in Lect. Appl. Math. Inform. edited by Ricciardi, Manchester University Press (1990) 62–106.  
  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.  
  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.  
  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.  
  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.  
  50. A. Weber, Distance automata having large finite distance or finite ambiguity. Math. Syst. Theor.26 (1993) 169–185.  
  51. A. Weber, Finite valued distance automata. Theor. Comput. Sci.134 (1994) 225–251.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.