Arseny M. Shur (2009)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
Vladimir Baltić (2012)
The Yugoslav Journal of Operations Research
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.
Antoine Meyer (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...
Jaroslav Král (1967)
Kybernetika
Similarity:
Marcella Anselmo, Dora Giammarresi, Maria Madonia, Antonio Restivo (2006)
RAIRO - Theoretical Informatics and Applications
Similarity:
We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure...