Input-driven pushdown automata (IDPDA) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that popping from the empty pushdown does not block the computation but continues it with empty pushdown. Here, we consider IDPDAs that have a more balanced behavior concerning pushing and popping. Digging input-driven pushdown automata (DIDPDA) are basically IDPDAs that, when forced to pop from the empty pushdown, dig a hole of the shape of the popped symbol in the bottom of the pushdown. Popping further symbols from a pushdown having a hole at the bottom deepens the current hole furthermore. The hole can only be filled up by pushing symbols previously popped. We study the impact of the new behavior of DIDPDAs on their power and compare their capacities with the capacities of ordinary IDPDAs and tinput-driven pushdown automata which are basically IDPDAs whose input may be preprocessed by length-preserving finite state transducers. It turns out that the capabilities are incomparable. We address the determinization of DIDPDAs and their descriptional complexity, closure properties, and decidability questions.
Keywords: Input-driven pushdown automata, empty pushdown behavior, computational capacity, determinization, descriptional complexity, closure properties, decidability problems
@article{ITA_2021__55_1_A8_0,
author = {Kutrib, Martin and Malcher, Andreas},
editor = {Holzer, Markus and Sempere, Jos\'e M.},
title = {Digging {Input-Driven} {Pushdown} {Automata}},
journal = {RAIRO. Theoretical Informatics and Applications},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ita/2021006},
mrnumber = {4289538},
zbl = {1508.68197},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita/2021006/}
}
TY - JOUR AU - Kutrib, Martin AU - Malcher, Andreas ED - Holzer, Markus ED - Sempere, José M. TI - Digging Input-Driven Pushdown Automata JO - RAIRO. Theoretical Informatics and Applications PY - 2021 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita/2021006/ DO - 10.1051/ita/2021006 LA - en ID - ITA_2021__55_1_A8_0 ER -
%0 Journal Article %A Kutrib, Martin %A Malcher, Andreas %E Holzer, Markus %E Sempere, José M. %T Digging Input-Driven Pushdown Automata %J RAIRO. Theoretical Informatics and Applications %D 2021 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita/2021006/ %R 10.1051/ita/2021006 %G en %F ITA_2021__55_1_A8_0
Kutrib, Martin; Malcher, Andreas. Digging Input-Driven Pushdown Automata. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 6. doi: 10.1051/ita/2021006
[1] and , Visibly pushdown languages, in Symposium on Theory of Computing (STOC 2004). ACM (2004) 202–211. | MR | Zbl | DOI
[2] and , Adding nesting structure to words. J. ACM 56 (2009). | MR | Zbl | DOI
[3] , , and Input-driven stack automata. In Theoretical Computer Science (TCS 2012), volume 7604 of LNCS. Springer (2012) 28–42. | MR | Zbl | DOI
[4] , and , Ordered multi-stack visibly pushdown automata. Theoret. Comput. Sci. 656 (2016) 1–26. | MR | Zbl | DOI
[5] and , Minimizing variants of visibly pushdown automata. In Mathematical Foundations of Computer Science (MFCS 2007), volume 4708 of LNCS. Springer (2007) 135–146. | MR | Zbl | DOI
[6] and , Operator precedence and the visibly pushdown property. J. Comput. System Sci. 78 (2012) 1837–1867. | MR | Zbl | DOI
[7] , Input-driven languages are in log n depth. Inform. Process. Lett. 26 (1988) 247–250. | MR | DOI
[8] , and , On reducing the number of states in a PDA. Math. Syst. Theory 15 (1982) 315–321. | MR | Zbl | DOI
[9] , and , On reducing the number of stack symbols in a PDA. Math. Syst. Theory 26 (1993) 313–326. | MR | Zbl | DOI
[10] and , Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl
[11] and , Digging input-driven pushdown automata. In Eleventh Workshop on Non-Classical Models of Automata and Applications, NCMA 2019, Valencia, Spain, July 2-3, 2019. Österreichische Computer Gesellschaft (2019) 109–124. | MR | Zbl
[12] , , , and , Deterministic input-driven queue automata: finite turns, decidability, and closure properties. Theoret. Comput. Sci. 578 (2015) 58–71. | MR | Zbl | DOI
[13] , and , Tinput-driven pushdown, counter, and stack automata. Fund. Inf . 155 (2017) 59–88. | MR | Zbl
[14] , and , A robust class of context-sensitive languages. In Logic in Computer Science (LICS 2007). IEEE Computer Society (2007) 161–170. | DOI
[15] , and , On multi-stack visibly pushdown languages. Preprint (2013). http://eprints.soton.ac.uk/id/eprint/351914. | MR | Zbl
[16] , and , Scope-bounded pushdown languages. Int. J. Found. Comput. Sci. 27 (2016) 215–234. | MR | Zbl | DOI
[17] , P-hardness of the emptiness problem for visibly pushdown languages. Inform. Process. Lett. 111 (2011) 338–341. | MR | Zbl | DOI
[18] and , The tree width of auxiliary storage. In Principles of Programming Languages, (POPL 2011). ACM (2011) 283–294. | Zbl
[19] and , Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012) 1555–1578. | MR | Zbl | DOI
[20] , Pebbling moutain ranges and its application of DCFL-recognition. In International Colloquium on Automata, Languages and Programming (ICALP 1980). Volume 85 of LNCS. Springer (1980) 422–435. | MR | Zbl | DOI
[21] and , Finite-state acceptors with translucent letters. In International Workshop on AI Methods for Interdisciplinary Research in Language and Biology (ICAART 2011). INSTICC, SciTePress (2011) 3–13.
[22] and , Complexity of input-driven pushdown automata. SIGACT News 45 (2014) 47–67. | MR | DOI
[23] , Formal Languages. Academic Press (1973). | MR | Zbl
[24] and , Input-driven languages are recognized in log n space. In Topics in the Theory of Computation. Volume 102 of Mathematics Studies. North-Holland, Amsterdam (1985) 1–19. | MR | Zbl
Cité par Sources :
