When input-driven pushdown automata meet reversiblity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 4, pp. 313-330.

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
Mots clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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, Tome 50 (2016) no. 4, pp. 313-330. doi : 10.1051/ita/2016016. http://archive.numdam.org/articles/10.1051/ita/2016016/

R. Alur and P. Madhusudan, Visibly pushdown languages. In Symposium on Theory of Computing, STOC ACM (2004) 202–211. | MR | Zbl

R. Alur and P. Madhusudan, Adding nesting structure to words. J. ACM 56 (2009) 16. | DOI | MR | Zbl

H.B. Axelsen, Reversible multi-head finite automata characterize reversible logarithmic space. In Language and Automata Theory and Applications (LATA 2012). Vol. 7183 of Lect. Notes Comput. Sci. Springer (2012) 95–105. | MR

H.B. Axelsen and R. Glück, A simple and efficient universal reversible Turing machine. In Language and Automata Theory and Applications (LATA 2011). Vol. 6638 of Lect. Notes Comput. Sci. Springer (2011) 117–128.

C.H. Bennett, Logical reversibility of computation. IBM J. Res. Dev. 17 (1973) 525–532. | DOI | MR | Zbl

S. Bensch, M. Holzer, M. Kutrib and A. Malcher, Input-driven stack automata. In Theoretical Computer Science (TCS 2012). Vol. 7604 of Lect. Notes Comput. Sci. Springer (2012) 28–42. | MR

P. Chervet and I. Walukiewicz, Minimizing variants of visibly pushdown automata. In Mathematical Foundations of Computer Science (MFCS 2007). Vol. 4708 of Lect. Notes Comput. Sci. Springer (2007) 135–146. | MR | Zbl

S. Crespi-Reghizzi and D. Mandrioli, Operator precedence and the visibly pushdown property. J. Comput. System Sci. 78 (2012) 1837–1867. | DOI | MR | Zbl

Y.-S. Han and K. Salomaa, Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. 410 (2009) 2961–2971. | DOI | MR | Zbl

M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley (1978). | MR | Zbl

J. Kari, Reversible cellular automata. In Developments in Language Theory (DLT 2005). Vol. 3572 of Lect. Notes Comput. Sci. Springer (2005) 57–68. | MR | Zbl

M. Kutrib, Aspects of reversibility for classical automata. In Computing with New Resources. Vol. 8808 of Lect. Notes Comput. Sci. Springer (2014) 83–98. | MR

M. Kutrib and A. Malcher. When Church-Rosser becomes context free. Int. J. Found. Comput. Sci. 18 (2007) 1293–1302. | DOI | MR | Zbl

M. Kutrib and A. Malcher, Fast reversible language recognition using cellular automata. Inform. Comput. 206 (2008) 1142–1151. | DOI | MR | Zbl

M. Kutrib and A. Malcher, Real-time reversible iterative arrays. Theoret. Comput. Sci. 411 (2010) 812–822. | DOI | MR | Zbl

M. Kutrib and A. Malcher, Reversible pushdown automata. J. Comput. System Sci. 78 (2012) 1814–1827. | DOI | MR | Zbl

M. Kutrib and A. Malcher, One-way reversible multi-head finite automata. In Reversible Computation (RC 2012). Vol. 7581 of Lect. Notes Comput. Sci. Springer (2013) 14–28. | MR

M. Kutrib and A. Malcher, Real-time reversible one-way cellular automata. In Cellular Automata and Discrete Complex Systems (AUTOMATA 2014). Vol. 8996 of Lect. Notes Comput. Sci. Springer (2015) 56–69. | MR

M. Kutrib, A. Malcher, C. Mereghetti, B. Palano and M. Wendlandt, Input-driven queue automata: Finite turns, decidability, and closure properties. Theoret. Comput. Sci. 578 (2015) 58–71. | DOI | MR | Zbl

M. Kutrib, A. Malcher and M. Wendlandt, Reversible queue automata. In Non-Classical Models of Automata and Applications (NCMA 2014). Vol. 304 of books@ocg.at. Austrian Computer Society (2014) 163–178.

M. Kutrib, A. Malcher and M. Wendlandt, Tinput-driven pushdown automata. In Machines, Computations, and Universality (MCU 2015). Vol. 9288 of Lect. Notes Comput. Sci. Springer (2015) 94–112. | MR

S. La Torre, P. Madhusudan and G. Parlato, A robust class of context-sensitive languages. In Logic in Computer Science (LICS 2007). IEEE Computer Society (2007) 161–170.

R. Landauer, Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5 (1961) 183–191. | DOI | MR | Zbl

K.-J. Lange, P. Mckenzie and A. Tapp, Reversible space equals deterministic space. J. Comput. System Sci. 60 (2000) 354–367. | DOI | MR | Zbl

P. Madhusudan and G. Parlato, The tree width of auxiliary storage. In Principles of Programming Languages (POPL 2011). ACM (2011) 283–294. | Zbl

K. Mehlhorn, Pebbling moutain ranges and its application of DCFL-recognition. In International Colloquium on Automata, Languages and Programming (ICALP 1980). Vol. 85 of Lect. Notes Comput. Sci. Springer (1980) 422–435. | MR | Zbl

K. Morita, Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148 (1995) 157–163. | DOI | MR | Zbl

K. Morita, Reversible computing and cellular automata – a survey. Theoret. Comput. Sci. 395 (2008) 101–131. | DOI | MR | Zbl

K. Morita, Two-way reversible multi-head finite automata. Fund. Inform. 110 (2011) 241–254. | MR | Zbl

A. Okhotin and K. Salomaa, State complexity of operations on input-driven pushdown automata. In Mathematical Foundations of Computer Science (MFCS 2011). Vol. 6907 of Lect. Notes Comput. Sci. Springer (2011) 485–496. | MR

X. Piao and K. Salomaa, Operational state complexity of nested word automata. Theoret. Comput. Sci. 410 (2009) 3290–3302. | DOI | MR | Zbl

B. von Braunmühl and R. Verbeek, Input-driven languages are recognized in logn space. In Topics in the Theory of Computation. Vol. 102 of Mathematics Studies. North-Holland (1985) 1–19. | MR

Cité par Sources :