Boosting reversible pushdown machines by preprocessing
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Boosting reversible pushdown machines by preprocessing. / Axelsen, Holger Bock; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias.
Reversible Computation: 8th International Conference, RC 2016, Bologna, Italy, July 7-8, 2016, Proceedings. ed. / Simon Devitt; Ivan Lanese. Springer, 2016. p. 89-104 (Lecture notes in computer science, Vol. 9720).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Boosting reversible pushdown machines by preprocessing
AU - Axelsen, Holger Bock
AU - Kutrib, Martin
AU - Malcher, Andreas
AU - Wendlandt, Matthias
N1 - Conference code: 8
PY - 2016
Y1 - 2016
N2 - It is well known that reversible finite automata do not accept all regular languages and that reversible pushdown automata do not accept all deterministic context-free languages. It is of significant interest both from a practical and theoretical point of view to close these gaps. We here extend these reversible models by a preprocessing unit which is basically a reversible injective and length-preserving sequential transducer. It turns out that preprocessing the input using such weak devices increases the computational power of reversible deterministic finite automata to the acceptance of all regular languages, whereas for reversible pushdown automata the accepted family of languages lies strictly in between the reversible deterministic context-free languages and the real-time deterministic context-free languages. Moreover, it is shown that the computational power of both types of machines is not changed by allowing the preprocessing sequential transducer to work irreversibly. Finally, we examine the closure properties of the family of languages accepted by such machines.
AB - It is well known that reversible finite automata do not accept all regular languages and that reversible pushdown automata do not accept all deterministic context-free languages. It is of significant interest both from a practical and theoretical point of view to close these gaps. We here extend these reversible models by a preprocessing unit which is basically a reversible injective and length-preserving sequential transducer. It turns out that preprocessing the input using such weak devices increases the computational power of reversible deterministic finite automata to the acceptance of all regular languages, whereas for reversible pushdown automata the accepted family of languages lies strictly in between the reversible deterministic context-free languages and the real-time deterministic context-free languages. Moreover, it is shown that the computational power of both types of machines is not changed by allowing the preprocessing sequential transducer to work irreversibly. Finally, we examine the closure properties of the family of languages accepted by such machines.
UR - http://www.scopus.com/inward/record.url?scp=84978873791&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-40578-0_6
DO - 10.1007/978-3-319-40578-0_6
M3 - Article in proceedings
AN - SCOPUS:84978873791
SN - 978-3-319-40577-3
T3 - Lecture notes in computer science
SP - 89
EP - 104
BT - Reversible Computation
A2 - Devitt, Simon
A2 - Lanese, Ivan
PB - Springer
Y2 - 7 July 2016 through 8 July 2016
ER -
ID: 172139778