Abstract
We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and nondeterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56, Article 16 (2009)
von Braunmühl, B., Verbeek, R.: Input-driven Languages are Recognized in logn Space. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol. 158, pp. 40–51. Springer, Heidelberg (1983)
Chervet, P., Walukiewicz, I.: Minimizing Variants of Visibly Pushdown Automata. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 135–146. Springer, Heidelberg (2007)
Chomsky, N.: Formal Properties of Grammars. In: Handbook of Mathematic Psychology, vol. 2, pp. 323–418. Wiley & Sons (1962)
Crespi Reghizzi, S., Mandrioli, D.: Operator Precedence and the Visibly Pushdown Property. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 214–226. Springer, Heidelberg (2010)
Dymond, P.W.: Input-driven languages are in logn depth. Inform. Process. Lett. 26, 247–250 (1988)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman (1979)
Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975)
Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14, 389–418 (1967)
Han, Y.S., Salomaa, K.: Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. 410, 2961–2971 (2009)
Hunt, H.: On the complexity of finite, pushdown and stack automata. Math. Systems Theory 10, 33–52 (1976)
Kutrib, M., Malcher, A.: Reversible Pushdown Automata. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 368–379. Springer, Heidelberg (2010)
Lange, K.J.: A note on the P-completeness of deterministic one-way stack languages. J. Univ. Comput. Sci. 16, 795–799 (2010)
Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and its Applications. Springer (1993)
Mehlhorn, K.: Pebbling Mountain Ranges and Its Application of DCFL-recongnition. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 422–435. Springer, Heidelberg (1980)
Okhotin, A., Salomaa, K.: State Complexity of Operations on Input-Driven Pushdown Automata. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 485–496. Springer, Heidelberg (2011)
Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci. 410, 3290–3302 (2009)
Salomaa, A.: Formal Languages. ACM Monograph Series. Academic Press (1973)
Shamir, E., Beeri, C.: Checking Stacks and Context-free Programmed Grammars Accept P-complete Languages. In: Loeckx, J. (ed.) ICALP 1974. LNCS, vol. 14, pp. 27–33. Springer, Heidelberg (1974)
Sudborough, I.H.: On the tape complexity of deterministic context-free languages. J. ACM 25, 405–414 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Bensch, S., Holzer, M., Kutrib, M., Malcher, A. (2012). Input-Driven Stack Automata. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds) Theoretical Computer Science. TCS 2012. Lecture Notes in Computer Science, vol 7604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33475-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-33475-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33474-0
Online ISBN: 978-3-642-33475-7
eBook Packages: Computer ScienceComputer Science (R0)