Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 3, page 647-655
  • ISSN: 0988-3754

Abstract

top
Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

How to cite

top

Shur, Arseny M.. "Comparing Complexity Functions of a Language and Its Extendable Part." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 647-655. <http://eudml.org/doc/250371>.

@article{Shur2008,
abstract = { Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly. },
author = {Shur, Arseny M.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {combinatorial complexity},
language = {eng},
month = {6},
number = {3},
pages = {647-655},
publisher = {EDP Sciences},
title = {Comparing Complexity Functions of a Language and Its Extendable Part},
url = {http://eudml.org/doc/250371},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Shur, Arseny M.
TI - Comparing Complexity Functions of a Language and Its Extendable Part
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/6//
PB - EDP Sciences
VL - 42
IS - 3
SP - 647
EP - 655
AB - Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.
LA - eng
KW - combinatorial complexity
UR - http://eudml.org/doc/250371
ER -

References

top
  1. C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of formal languages1, edited by G. Rosenberg, A. Salomaa. Springer, Berlin (1997) 329–438.  
  2. D.M. Cvetković, M. Doob and H. Sachs, Spectra of graphs. Theory and applications, 3rd edn. Johann Ambrosius Barth, Heidelberg (1995).  
  3. F. D'Alessandro, B. Intrigila and S. Varricchio, On the structure of counting function of sparse context-free languages. Theor. Comput. Sci.356 (2006) 104–117.  
  4. A. Ehrenfeucht and G. Rozenberg, A limit theorem for sets of subwords in deterministic TOL languages. Inform. Process. Lett.2 (1973) 70–73.  
  5. F.R. Gantmacher, Application of the theory of matrices. Interscience, New York (1959).  
  6. O. Ibarra and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers. Lect. Notes Comput. Sci.210 (1986) 171–179.  
  7. Y. Kobayashi, Repetition-free words. Theor. Comput. Sci.44 (1986) 175–197.  
  8. Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math.20 (1988) 221–232.  
  9. A. Lepistö, A characterization of 2+-free words over a binary alphabet. Turku Centre for Computer Science, TUCS Tech. Report 74 (1996).  
  10. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  
  11. A.M. Shur, Combinatorial complexity of rational languages. Discrete Anal. Oper. Res. 112 (2005) 78–99 (Russian).  
  12. A.M. Shur, On intermediate factorial languages. Turku Centre for Computer Science, TUCS Tech. Report 723 (2005).  

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.