# Comparing Complexity Functions of a Language and Its Extendable Part

RAIRO - Theoretical Informatics and Applications (2008)

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

## Access Full Article

top## Abstract

top## How to cite

topShur, 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- 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.
- D.M. Cvetković, M. Doob and H. Sachs, Spectra of graphs. Theory and applications, 3rd edn. Johann Ambrosius Barth, Heidelberg (1995). Zbl0824.05046
- 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. Zbl1160.68407
- A. Ehrenfeucht and G. Rozenberg, A limit theorem for sets of subwords in deterministic TOL languages. Inform. Process. Lett.2 (1973) 70–73. Zbl0299.68044
- F.R. Gantmacher, Application of the theory of matrices. Interscience, New York (1959). Zbl0085.01001
- O. Ibarra and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers. Lect. Notes Comput. Sci.210 (1986) 171–179. Zbl0605.68080
- Y. Kobayashi, Repetition-free words. Theor. Comput. Sci.44 (1986) 175–197. Zbl0596.20058
- Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math.20 (1988) 221–232. Zbl0673.68046
- A. Lepistö, A characterization of 2+-free words over a binary alphabet. Turku Centre for Computer Science, TUCS Tech. Report 74 (1996).
- M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866. Zbl0019.33502
- A.M. Shur, Combinatorial complexity of rational languages. Discrete Anal. Oper. Res. 112 (2005) 78–99 (Russian). Zbl1249.68107
- A.M. Shur, On intermediate factorial languages. Turku Centre for Computer Science, TUCS Tech. Report 723 (2005). Zbl1187.68303

## Citations in EuDML Documents

top- Alexey V. Samsonov, Arseny M. Shur, On abelian repetition threshold
- Alexey V. Samsonov, Arseny M. Shur, On Abelian repetition threshold
- Arseny M. Shur, Irina A. Gorbunova, On the growth rates of complexity of threshold languages
- Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur, Binary patterns in binary cube-free words: Avoidability and growth

## NotesEmbed ?

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