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.
Accepté le :
DOI : 10.1051/ita/2016016
Mots clés : Reversible computation, input-driven pushdown automata, formal languages, closure properties
@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://www.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://www.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://www.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://www.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
and , 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.
, 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
and , Operator precedence and the visibly pushdown property. J. Comput. System Sci. 78 (2012) 1837–1867. | DOI | MR | Zbl
and , 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
and . When Church-Rosser becomes context free. Int. J. Found. Comput. Sci. 18 (2007) 1293–1302. | DOI | MR | Zbl
and , Fast reversible language recognition using cellular automata. Inform. Comput. 206 (2008) 1142–1151. | DOI | MR | Zbl
and , Real-time reversible iterative arrays. Theoret. Comput. Sci. 411 (2010) 812–822. | DOI | MR | Zbl
and , 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
, , , and , 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.
, Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5 (1961) 183–191. | DOI | MR | Zbl
, and , 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
, Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148 (1995) 157–163. | DOI | MR | Zbl
, Reversible computing and cellular automata – a survey. Theoret. Comput. Sci. 395 (2008) 101–131. | DOI | MR | Zbl
, 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
and , 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 space. In Topics in the Theory of Computation. Vol. 102 of Mathematics Studies. North-Holland (1985) 1–19. | MR
Cité par Sources :
