Abstract
In this paper we define higher order multi-stack pushdown systems. We show that parity games over bounded phase higher order multi-stack pushdown systems are effectively solvable and winning strategy in these games can be effectively synthesized.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
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
Seth, A.: Games on Higher Order Multi-Stack Pushdown Systems, full version, http://www.cse.iitk.ac.in/users/seth/RP09/fullversion
Seth, A.: Games on Multi-Stack Pushdown Systems. In: Artemov, S., Nerode, A. (eds.) LFCS 2009. LNCS, vol. 5407, pp. 395–408. Springer, Heidelberg (2008)
Carayol, A., Hague, M., Meyer, A., Ong, C.-H.L., Serre, O.: Winning Regions of Higher-Order Pushdown Games. In: Proc: LICS 2008, pp. 193–204. IEEE Computer Society, Los Alamitos (2008)
Hague, M., Murawski, A.S., Luke Ong, C.-H., Serre, O.: Collapsible Pushdown Automata and Recursion Schemes. In: Proc: LICS 2008, pp. 452–461. IEEE Computer Society, Los Alamitos (2008)
Madhusudan, P., Parlato, G., La Torre, S.: A Robust Class of Context-Sensitive Languages. In: Proc: LICS 2007, pp. 161–170. IEEE Computer Society, Los Alamitos (2007)
Madhusudan, P., Parlato, G., La Torre, S.: Context-Bounded Analysis of Concurrent Queue Systems. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 299–314. Springer, Heidelberg (2008)
Qadeer, S., Rehof, J.: Context-bounded model checking of concurrent software. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol. 3440, pp. 93–107. Springer, Heidelberg (2005)
Knapik, T., Niwinski, D., Urzyczyn, P., Walukiewicz, I.: Unsafe Grammars and Panic Automata. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1450–1461. Springer, Heidelberg (2005)
Bouajjani, A., Meyer, A.: Symbolic reachability analysis of higher-order context-free processes. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol. 3328, pp. 135–147. Springer, Heidelberg (2004)
Cachat, T.: Higher order pushdown automata, the caucal hierarchy of graphs and parity games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 556–569. Springer, Heidelberg (2003)
Cachat, T.: Uniform solution of parity games on prefix-recognizable graphs. In: Proc. Infinity. ENTCS, vol. 68(6) (2002)
Walukiewicz, I.: Pushdown processes: games and model checking. Information and computation 164, 234–263 (2001)
Jurdziński, M.: Small Progress Measures for Solving Parity Games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290–301. Springer, Heidelberg (2000)
Thomas, W.: Languages, automata and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. III, pp. 389–455. Springer, New York (1997)
Engelfriet, J.: Iterated pushdown automata and complexity classes. In: STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 365–373. ACM Press, New York (1983)
Damm, W., Goerdt, A.: An automata-theoretical characterization of the OI-hierarchy. Information and Control 71(1-2), 1–32 (1986)
Maslov, A.N.: Multilevel stack automata. Problems of Information Transmission 15, 1170–1174 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seth, A. (2009). Games on Higher Order Multi-stack Pushdown Systems. In: Bournez, O., Potapov, I. (eds) Reachability Problems. RP 2009. Lecture Notes in Computer Science, vol 5797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04420-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-04420-5_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04419-9
Online ISBN: 978-3-642-04420-5
eBook Packages: Computer ScienceComputer Science (R0)