Advertisement
Published in:
2014 | OriginalPaper | Chapter
Degrees of Reversibility for DFA and DPDA
Authors : Martin Kutrib, Thomas Worsch
Published in: Reversible Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.