{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T20:35:58Z","timestamp":1794342958540,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540454588","type":"print"},{"value":"9783540454595","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11874683_6","type":"book-chapter","created":{"date-parts":[[2006,9,27]],"date-time":"2006-09-27T09:47:26Z","timestamp":1159350446000},"page":"89-103","source":"Crossref","is-referenced-by-count":8,"title":["Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"Srba","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-44693-1_4","volume-title":"STACS 2001","author":"L. Aceto","year":"2001","unstructured":"Aceto, L., Fokkink, W., Ing\u00f3lfsd\u00f3ttir, A.: 2-nested simulation is not finitely equationally axiomatizable. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 39\u201350. Springer, Heidelberg (2001)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-540-24730-2_35","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"R. Alur","year":"2004","unstructured":"Alur, R., Etessami, K., Madhusudan, P.: A temporal logic of nested calls and returns. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS, vol.\u00a02988, pp. 467\u2013481. Springer, Heidelberg (2004)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1007\/11523468_89","volume-title":"Automata, Languages and Programming","author":"R. Alur","year":"2005","unstructured":"Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1102\u20131114. Springer, Heidelberg (2005)"},{"key":"6_CR4","first-page":"202","volume-title":"Proc. of STOC 2004","author":"R. Alur","year":"2004","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proc. of STOC 2004, pp. 202\u2013211. ACM Press, New York (2004)"},{"issue":"6A","key":"6_CR5","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/BF03180566","volume":"4","author":"J. Balcazar","year":"1992","unstructured":"Balcazar, J., Gabarro, J., Santha, M.: Deciding bisimilarity is P-complete. Formal Aspects of Computing\u00a04(6A), 638\u2013648 (1992)","journal-title":"Formal Aspects of Computing"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/11672142_34","volume-title":"STACS 2006","author":"V. B\u00e1r\u00e1ny","year":"2006","unstructured":"B\u00e1r\u00e1ny, V., L\u00f6ding, C., Serre, O.: Regularity problems for visibly pushdown languages. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 420\u2013431. Springer, Heidelberg (2006)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/3-540-63141-0_10","volume-title":"CONCUR\u201997: Concurrency Theory","author":"A. Bouajjani","year":"1997","unstructured":"Bouajjani, A., Esparza, J., Maler, O.: Reachability analysis of pushdown automata: Application to model-checking. In: Mazurkiewicz, A., Winkowski, J. (eds.) CONCUR 1997. LNCS, vol.\u00a01243, pp. 135\u2013150. Springer, Heidelberg (1997)"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/3-540-60246-1_148","volume-title":"Mathematical Foundations of Computer Science 1995","author":"O. Burkart","year":"1995","unstructured":"Burkart, O., Caucal, D., Steffen, B.: An elementary decision procedure for arbitrary context-free processes. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969, pp. 423\u2013433. Springer, Heidelberg (1995)"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-61604-7_59","volume-title":"CONCUR \u201996: Concurrency Theory","author":"O. Burkart","year":"1996","unstructured":"Burkart, O., Caucal, D., Steffen, B.: Bisimulation collapse and the process taxonomy. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol.\u00a01119, pp. 247\u2013262. Springer, Heidelberg (1996)"},{"issue":"2","key":"6_CR10","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1006\/inco.1994.1101","volume":"115","author":"J.F. Groote","year":"1994","unstructured":"Groote, J.F., H\u00fcttel, H.: Undecidable equivalences for basic process algebra. Information and Computation\u00a0115(2), 353\u2013371 (1994)","journal-title":"Information and Computation"},{"key":"6_CR11","first-page":"88","volume-title":"Proc. of DLT 1995","author":"M. Holzer","year":"1996","unstructured":"Holzer, M.: On emptiness and counting for alternating finite automata. In: Proc. of DLT 1995, pp. 88\u201397. World Scientific, Singapore (1996)"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1999.2813","volume":"158","author":"P. Jan\u010dar","year":"2000","unstructured":"Jan\u010dar, P.: Decidability of bisimilarity for one-counter processes. Information and Computation\u00a0158(1), 1\u201317 (2000)","journal-title":"Information and Computation"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0890-5401(03)00171-8","volume":"188","author":"P. Jan\u010dar","year":"2004","unstructured":"Jan\u010dar, P., Ku\u010dera, A., Moller, F., Sawa, Z.: DP lower bounds for equivalence-checking and model-checking of one-counter automata. Information and Computation\u00a0188(1), 1\u201319 (2004)","journal-title":"Information and Computation"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-47849-3_28","volume-title":"SOFSEM\u201999: Theory and Practice of Informatics","author":"P. Jan\u010dar","year":"1999","unstructured":"Jan\u010dar, P., Moller, F., Sawa, Z.: Simulation problems for one-counter machines. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol.\u00a01725, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"6_CR15","first-page":"507","volume-title":"Proc. of TCS 2004","author":"P. Jan\u010dar","year":"2004","unstructured":"Jan\u010dar, P., Srba, J.: Highly undecidable questions for process algebras. In: Proc. of TCS 2004, pp. 507\u2013520. Kluwer Academic Publishers, Dordrecht (2004)"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional \u03bc-calculus. Theoretical Computer Science\u00a027, 333\u2013354 (1983)","journal-title":"Theoretical Computer Science"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-45687-2_36","volume-title":"Mathematical Foundations of Computer Science 2002","author":"A. Ku\u010dera","year":"2002","unstructured":"Ku\u010dera, A., Mayr, R.: On the complexity of semantic equivalences for pushdown automata and BPA. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 433\u2013445. Springer, Heidelberg (2002)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-540-31982-5_13","volume-title":"Foundations of Software Science and Computational Structures","author":"A. Murawski","year":"2005","unstructured":"Murawski, A., Walukiewicz, I.: Third-order idealized algol with iteration is decidable. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol.\u00a03441, pp. 202\u2013218. Springer, Heidelberg (2005)"},{"issue":"6","key":"6_CR19","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM Journal of Computing\u00a016(6), 973\u2013989 (1987)","journal-title":"SIAM Journal of Computing"},{"key":"6_CR20","unstructured":"Pitcher, C.: Visibly pushdown expression effects for XML stream processing. In: Proc. of PLAN-X, pp. 5\u201319 (2005)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-45627-9_29","volume-title":"SOFSEM 2001: Theory and Practice of Informatics","author":"Z. Sawa","year":"2001","unstructured":"Sawa, Z., Jan\u010dar, P.: P-hardness of equivalence testing on finite-state processes. In: Pacholski, L., Ru\u017ei\u010dka, P. (eds.) SOFSEM 2001. LNCS, vol.\u00a02234, pp. 326\u2013345. Springer, Heidelberg (2001)"},{"key":"6_CR22","first-page":"120","volume-title":"Proc. of FOCS 1998","author":"G. S\u00e9nizergues","year":"1998","unstructured":"S\u00e9nizergues, G.: Decidability of bisimulation equivalence for equational graphs of finite out-degree. In: Proc. of FOCS 1998, pp. 120\u2013129. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/11690634_23","volume-title":"Foundations of Software Science and Computation Structures","author":"O. Serre","year":"2006","unstructured":"Serre, O.: Parity games played on transition graphs of one-counter processes. In: Aceto, L., Ing\u00f3lfsd\u00f3ttir, A. (eds.) FOSSACS 2006. LNCS, vol.\u00a03921, pp. 337\u2013351. Springer, Heidelberg (2006)"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1007\/3-540-45465-9_61","volume-title":"Automata, Languages and Programming","author":"J. Srba","year":"2002","unstructured":"Srba, J.: Strong bisimilarity and regularity of basic process algebra is PSPACE-hard. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 716\u2013727. Springer, Heidelberg (2002)"},{"issue":"2","key":"6_CR25","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown processes: Games and model-checking. Information and Computation\u00a0164(2), 234\u2013263 (2001)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11874683_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:24:47Z","timestamp":1619493887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11874683_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540454588","9783540454595"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11874683_6","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11874683","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}