Boosting reversible pushdown machines by preprocessing

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • Holger Bock Axelsen
  • Martin Kutrib
  • Andreas Malcher
  • Matthias Wendlandt

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.

OriginalsprogEngelsk
TitelReversible Computation : 8th International Conference, RC 2016, Bologna, Italy, July 7-8, 2016, Proceedings
RedaktørerSimon Devitt, Ivan Lanese
Antal sider16
ForlagSpringer
Publikationsdato2016
Sider89-104
ISBN (Trykt)978-3-319-40577-3
ISBN (Elektronisk)978-3-319-40578-0
DOI
StatusUdgivet - 2016
Begivenhed8th International Conference on Reversible Computation - Bologna, Italien
Varighed: 7 jul. 20168 jul. 2016
Konferencens nummer: 8

Konference

Konference8th International Conference on Reversible Computation
Nummer8
LandItalien
ByBologna
Periode07/07/201608/07/2016
NavnLecture notes in computer science
Vol/bind9720
ISSN0302-9743

ID: 172139778