Displaying similar documents to “On the expressive power of the shuffle operator matched with intersection by regular sets”

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

Some problems in automata theory which depend on the models of set theory

Olivier Finkel (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L ( 𝒜 ) accepted by a Büchi 1-counter automaton 𝒜 . We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 such that the cardinality of the complement L ( 𝒜 ) - of the ω-language...

On-line finite automata for addition in some numeration systems

Christiane Frougny (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base and addition in base is given. Results on addition in base β = b m , where is a relative integer, follow. We also show that addition in base the golden ratio is computable...

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

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton 𝒜 has the following characteristic properties. It has the same graph as 𝒜 . Each accepting path has the same label as in 𝒜 . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix...