Displaying similar documents to “A Hierarchy of Automatic ω-Words having a Decidable MSO Theory”

Theories of orders on the set of words

Dietrich Kuske (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of...

Drunken man infinite words complexity

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.


Traces of term-automatic graphs

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...

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

On the growth rates of complexity of threshold languages

Arseny M. Shur, Irina A. Gorbunova (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Threshold languages, which are the (/(–1))-free languages over -letter alphabets with ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over letters tends to a constant α ^ ≈ 1 . 242 as tends to infinity.

Comparing Complexity Functions of a Language and Its Extendable Part

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.