Two-variable word equations

Lucian Ilie; Wojciech Plandowski

Displaying similar documents to “Two-variable word equations”

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $# W [P]$ , the parameterized analogue of $# P$ . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers

Ondřej Turek (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we will deal with the balance properties of the infinite binary words associated to -integers when is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $ϕ (A) = A^{p} B$ , $ϕ (B) = A^{q}$ for $p \in ℕ$ , $q \in ℕ$ , $p \geq q$ , where $β = \frac{p + \sqrt{p^{2} + 4 q}}{2}$ . We will prove that such word is -balanced with $t = 1 + [(p - 1) / (p + 1 - q)]$ . Finally, in the case that it is known [B. Adamczewski, (2002) 197–224] that the fixed point of the substitution $ϕ (A) = A^{p} B$ , $ϕ (B) = A^{q}$ is not -balanced for any . We exhibit an infinite sequence of pairs...

The Helping Hierarchy

Patrizio Cintioli, Riccardo Silvestri (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Schöning [14] introduced a notion of helping and suggested the study of the class $P_{help} (𝒞)$ of the languages that can be helped by oracles in a given class $𝒞$ . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some $ℓ$ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with $ℓ$ nested pebbles....

A note on Coinduction and Weak Bisimilarity for While Programs

J. J.M.M. Rutten (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics $𝒪$ for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model $𝒟$ . Next $𝒪 = 𝒟$ is proved by coinduction.