Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Degrees of Reversibility for DFA and DPDA
verfasst von : Martin Kutrib, Thomas Worsch
Erschienen in: Reversible Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The notion of
k
-reversibility is generalized to pushdown automata. A pushdown automaton is said to be (
k
,
l
)-reversible if its predecessor configurations can uniquely be computed by a pushdown automaton with input lookahead of size
k
and stack lookahead of size
l
. It turns out that there are problems which can be solved by (
k
+ 1,1)-reversible pushdown automata, but not by (
k
,
l
)-reversible pushdown automata. So, infinite hierarchies dependent on the degree of reversibility are shown. On the other hand, any reversible pushdown automaton of degree (
k
,
l
+ 1) can be simulated by a reversible pushdown automaton of degree (
k
,1). So, there are no hierarchies induced by the size of the stack lookahead. These results complement the situation for finite automata which is also discussed and presented in our setting.