Geodesic
When input-driven pushdown automata meet reversiblity
Kutrib, Martin1  ; Malcher, Andreas1 ; Wendlandt, Matthias1
1 Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 313-330

Voir la notice de l'article provenant de la source Numdam

We investigate subfamilies of context-free languages that share two important properties. The languages are accepted by input-driven pushdown automata as well as by a reversible pushdown automata. So, the languages are input driven and reversible at the same time. This intersection can be defined on the underlying language families or on the underlying machine classes. It turns out that the latter class is properly included in the former. The relationships between the language families obtained in this way and to reversible context-free languages as well as to input-driven languages are studied. In general, a hierarchical inclusion structure within the real-time deterministic context-free languages is obtained. Finally, the closure properties of these families under the standard operations are investigated and it turns out that all language families introduced are anti-AFLs.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016016
Classification : 68Q45, 68Q68
Keywords: Reversible computation, input-driven pushdown automata, formal languages, closure properties

Kutrib, Martin 1 ; Malcher, Andreas 1 ; Wendlandt, Matthias 1

1 Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. 
@article{ITA_2016__50_4_313_0,
     author = {Kutrib, Martin and Malcher, Andreas and Wendlandt, Matthias},
     title = {When input-driven pushdown automata meet reversiblity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {313--330},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4},
     year = {2016},
     doi = {10.1051/ita/2016016},
     mrnumber = {3614548},
     zbl = {1362.68149},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016016/}
}
TY  - JOUR
AU  - Kutrib, Martin
AU  - Malcher, Andreas
AU  - Wendlandt, Matthias
TI  - When input-driven pushdown automata meet reversiblity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 313
EP  - 330
VL  - 50
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016016/
DO  - 10.1051/ita/2016016
LA  - en
ID  - ITA_2016__50_4_313_0
ER  - 
%0 Journal Article
%A Kutrib, Martin
%A Malcher, Andreas
%A Wendlandt, Matthias
%T When input-driven pushdown automata meet reversiblity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 313-330
%V 50
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016016/
%R 10.1051/ita/2016016
%G en
%F ITA_2016__50_4_313_0
Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias. When input-driven pushdown automata meet reversiblity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 313-330. doi: 10.1051/ita/2016016

Cité par Sources :