Distance desert automata and the star height problem

Daniel Kirsten

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • 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 2 2 𝒪 ( 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 - Informatique Théorique et Applications 39.3 (2005): 455-509. <http://eudml.org/doc/244714>.

@article{Kirsten2005,
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 $2^\{2^\{\{\mathcal \{O\}\}(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 - Informatique Théorique et Applications},
keywords = {recognizable languages; star height; distance automata; star heights; desert automata; hierarchies; decidability; star height problem; free monoids},
language = {eng},
number = {3},
pages = {455-509},
publisher = {EDP-Sciences},
title = {Distance desert automata and the star height problem},
url = {http://eudml.org/doc/244714},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Kirsten, Daniel
TI - Distance desert automata and the star height problem
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2005
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 $2^{2^{{\mathcal {O}}(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; star heights; desert automata; hierarchies; decidability; star height problem; free monoids
UR - http://eudml.org/doc/244714
ER -

References

top
  1. [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. Zbl1122.68462
  2. [2] J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979). Zbl0424.68040MR549481
  3. [3] R.S. Cohen, Star height of certain families of regular events. J. Comput. Syst. Sci. 4 (1970) 281–297. Zbl0245.94039
  4. [4] K. Culik II and J. Kari, Image compression using weighted finite automata. Computer Graphics 17 (1993) 305–313. 
  5. [5] F. Dejean and M. Schützenberger, On a question of Eggan. Inform. Control 9 (1966) 23–25. Zbl0209.02903
  6. [6] L.C. Eggan, Transition graphs and the star height of regular events. Michigan Math. J. 10 (1963) 385–397. Zbl0173.01504
  7. [7] S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, New York (1974). Zbl0317.94045MR530382
  8. [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). Zbl1110.68033
  9. [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). Zbl0830.20079MR1350793
  10. [10] K. Hashiguchi, Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci. 24 (1982) 233–244. Zbl0513.68051
  11. [11] K. Hashiguchi, Regular languages of star height one. Inform. Control 53 (1982) 199–210. Zbl0547.68072
  12. [12] K. Hashiguchi, Representation theorems of regular languages. J. Comput. Syst. Sci. 27 (1983) 101–115. Zbl0516.68063
  13. [13] K. Hashiguchi, Algorithms for determining relative star height and star height. Inform. Comput. 78 (1988) 124–169. Zbl0668.68081
  14. [14] K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions. Theor. Comput. Sci. 72 (1990) 27–38. Zbl0693.68031
  15. [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. Zbl1046.68568
  16. [16] K. Hashiguchi, New upper bounds to the limitedness of distance automata. Theor. Comput. Sci. 233 (2000) 19–32. Zbl0952.68082
  17. [17] K. Hashiguchi, Erratum to “New upper bounds to the limitedness of distance automata”. Theor. Comput. Sci. 290 (2003) 2183–2184. Zbl0952.68082
  18. [18] K. Hashiguchi and N. Honda, Homomorphisms that preserve star height. Inform. Control 30 (1976) 247–266. Zbl0325.94039
  19. [19] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory Languages, and Computation. Addison-Wesley, Reading (1979). Zbl0426.68001MR645539
  20. [20] F. Katritzke, Refinements of Data Compression using Weighted Finite Automata. Ph.D. Thesis, Universität Siegen (2001). 
  21. [21] D. Kirsten, A Burnside approach to the finite substitution problem. Theory Comput. Syst. (to appear). Zbl1102.68498MR2189557
  22. [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. Zbl1122.68467
  23. [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. Zbl1126.68455
  24. [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. Zbl1106.68371
  25. [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. Zbl0834.68058
  26. [26] G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons, New York (1979). Zbl0421.20025MR530552
  27. [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. [28] H. Leung, On the topological structure of a finitely generated semigroup of matrices. Semigroup Forum 37 (1988) 273–287. Zbl0646.20056
  29. [29] H. Leung, Limitedness theorem on finite automata with distance functions: An algebraic proof. Theor. Comput. Sci. 81 (1991) 137–145. Zbl0729.68049
  30. [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. Zbl0796.20062
  31. [31] H. Leung, On finite automata with limited nondeterminism. Acta Inform. 35 (1998) 595–624. Zbl0923.68090
  32. [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. Zbl0898.68049
  33. [33] H. Leung and V. Podolskiy, The limitedness problem on distance automata: Hashiguchi’s method revisited. Theor. Comput. Sci. 310 (2004) 147–158. Zbl1071.68045
  34. [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. [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. [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. Zbl1059.68065
  37. [37] Y. Métivier and G. Richomme. New results on the star problem in trace monoids. Inform. Comput. 119 (1995) 240–251. Zbl0832.68074
  38. [38] M. Mohri, Finite-state transducers in language and speech processing. Comput. Linguistics 23 (1997) 269–311. 
  39. [39] R. Montalbano and A. Restivo, On the star height of rational languages. Internat. J. Algebra Comput. 4 (1994) 427–441. Zbl0823.68050
  40. [40] D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B (1990) 1–57. Zbl0900.68312
  41. [41] J.-É. Pin, Varieties of Formal Languages. North Oxford Academic Publishers Ltd (1986). Zbl0655.68095MR912694
  42. [42] J.-É. Pin, Rational and recognizable langages, in Lect. Appl. Math. Inform. edited by Ricciardi, Manchester University Press (1990) 62–106. Zbl0753.68072
  43. [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. Zbl0872.20053
  44. [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. [45] J.-É. Pin, Tropical semirings, in Idempotency, edited by J. Gunawardena, Cambridge University Press (1998) 50–69. Zbl0909.16028
  46. [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. [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. Zbl0656.68086
  48. [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. [49] I. Simon, On semigroups of matrices over the tropical semiring. RAIRO-Inf. Theor. Appl. 28 (1994) 277–294. Zbl0888.68086
  50. [50] A. Weber, Distance automata having large finite distance or finite ambiguity. Math. Syst. Theor. 26 (1993) 169–185. Zbl0771.68088
  51. [51] A. Weber, Finite valued distance automata. Theor. Comput. Sci. 134 (1994) 225–251. Zbl0938.68709
  52. [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.