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
topHow 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).
- 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.
- A. Ehrenfeucht and G. Rozenberg, A limit theorem for sets of subwords in deterministic TOL languages. Inform. Process. Lett.2 (1973) 70–73.
- F.R. Gantmacher, Application of the theory of matrices. Interscience, New York (1959).
- O. Ibarra and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers. Lect. Notes Comput. Sci.210 (1986) 171–179.
- Y. Kobayashi, Repetition-free words. Theor. Comput. Sci.44 (1986) 175–197.
- Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math.20 (1988) 221–232.
- 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.
- A.M. Shur, Combinatorial complexity of rational languages. Discrete Anal. Oper. Res. 112 (2005) 78–99 (Russian).
- A.M. Shur, On intermediate factorial languages. Turku Centre for Computer Science, TUCS Tech. Report 723 (2005).
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 ?
topYou 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.