Displaying similar documents to “Characteristic formulae for timed automata”

Two-way automaton computations

Jean-Camille Birget (1990)

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

Similarity:

Formal language properties of hybrid systems with strong resets

Thomas Brihaye, Véronique Bruyère, Elaine Render (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study hybrid systems with strong resets from the perspective of formal language theory. We define a notion of hybrid regular expression and prove a Kleene-like theorem for hybrid systems. We also prove the closure of these systems under determinisation and complementation. Finally, we prove that the reachability problem is undecidable for synchronized products of hybrid systems.

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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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....