Sébastien Ferenczi, Pascal Hubert (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
Sébastien Ferenczi, Pascal Hubert (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
(1988)
Banach Center Publications
Similarity:
Liang Yu (2011)
Fundamenta Mathematicae
Similarity:
We study the descriptive set theoretical complexity of various randomness notions.
Marion Le Gonidec (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to (log ) when goes to infinity.
L'ubomíra Balková, Zuzana Masáková (2009)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We study the palindromic complexity of infinite words , the fixed points of the substitution over a binary alphabet, , , with , which are canonically associated with quadratic non-simple Parry numbers .
Galina Jirásková (2006)
RAIRO - Theoretical Informatics and Applications
Similarity:
The paper treats the question whether there always exists a minimal nondeterministic finite automaton of states whose equivalent minimal deterministic finite automaton has states for any integers and with . Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of and . However, in order to give an...
Markus Lohrey, Holger Petersen (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Kreinovich, V., Finkelstein, A.M. (2004)
Zapiski Nauchnykh Seminarov POMI
Similarity:
Goertzel, Ben (1992)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Klaus Thomsen (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.
Arseny M. Shur (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.