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.
Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2004)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.
K. Culik II, H. A. Maurer (1979)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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.
Milan Drášil (1989)
Archivum Mathematicum
Similarity: