{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:40:26Z","timestamp":1725795626966},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_20","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"232-243","source":"Crossref","is-referenced-by-count":1,"title":["Bisimulation Equivalence of First-Order Grammars"],"prefix":"10.1007","author":[{"given":"Petr","family":"Jan\u010dar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/174130.174141","volume":"40","author":"J. Baeten","year":"1993","unstructured":"Baeten, J., Bergstra, J., Klop, J.: Decidability of bisimulation equivalence for processes generating context-free languages. J. ACM\u00a040(3), 653\u2013682 (1993)","journal-title":"J. ACM"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Benedikt, M., G\u00f6ller, S., Kiefer, S., Murawski, A.S.: Bisimilarity of pushdown automata is nonelementary. In: Proc. LICS 2013, pp. 488\u2013498. IEEE Computer Society Press (2013)","DOI":"10.1109\/LICS.2013.55"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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 bisimulation 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":"20_CR4","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Recursive applicative program schemes. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 459\u2013492. Elsevier, MIT Press (1990)","DOI":"10.1016\/B978-0-444-88074-1.50014-7"},{"key":"20_CR5","unstructured":"Czerwi\u0144ski, W., Lasota, S.: Fast equivalence-checking for normed context-free processes. In: Proc. FSTTCS 2010. LIPIcs, vol.\u00a08. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2010)"},{"key":"20_CR6","unstructured":"Fu, Y., Yin, Q.: Dividing line between decidable PDA\u2019s and undecidable ones. CoRR abs\/1404.7015 (2014)"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y. Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci.\u00a0158, 143\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P., Srba, J.: Undecidability of bisimilarity by Defender\u2019s forcing. J. ACM\u00a055(1) (2008)","DOI":"10.1145\/1326554.1326559"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P.: Decidability of DPDA language equivalence via first-order grammars. In: Proc. LICS 2012, pp. 415\u2013424. IEEE Computer Society (2012)","DOI":"10.1109\/LICS.2012.51"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P.: Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof). Logical Methods in Computer Science\u00a09(1) (2013)","DOI":"10.2168\/LMCS-9(1:10)2013"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P.: Equivalences of pushdown systems are hard. In: Muscholl, A. (ed.) FOSSACS 2014. LNCS, vol.\u00a08412, pp. 1\u201328. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-642-54830-7_1"},{"issue":"4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.ipl.2012.12.004","volume":"113","author":"S. Kiefer","year":"2013","unstructured":"Kiefer, S.: BPA bisimilarity is EXPTIME-hard. Inf. Proc. Letters\u00a0113(4), 101\u2013106 (2013)","journal-title":"Inf. Proc. Letters"},{"key":"20_CR13","unstructured":"Schmitz, S.: Complexity hierarchies beyond elementary. CoRR abs\/1312.5686 (2013)"},{"issue":"1\u20132","key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2001","unstructured":"S\u00e9nizergues, G.: L(A)=L(B)? Decidability results from complete formal systems. Theor. Comput. Sci.\u00a0251(1\u20132), 1\u2013166 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"S\u00e9nizergues, G.: The bisimulation problem for equational graphs of finite out-degree. SIAM J.Comput.\u00a034(5), 1025\u20131106 (2005), presented at FOCS 1998","DOI":"10.1137\/S0097539700377256"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Srba, J.: Roadmap of infinite results. In: Current Trends In Theoretical Computer Science, The Challenge of the New Century, vol.\u00a02, pp. 337\u2013350. World Scientific Publishing Co. (2004), http:\/\/users-cs.au.dk\/srba\/roadmap\/","DOI":"10.1142\/9789812562494_0054"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/3-540-45465-9_70","volume-title":"Automata, Languages and Programming","author":"C. Stirling","year":"2002","unstructured":"Stirling, C.: Deciding DPDA equivalence is primitive recursive. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 821\u2013832. Springer, Heidelberg (2002)"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Stirling, C.: Decidability of bisimulation equivalence for pushdown processes (2000), available at the author\u2019s web-page","DOI":"10.1145\/333623.333624"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Yin, Q., Fu, Y., He, C., Huang, M., Tao, X.: Branching bisimilarity checking for PRS. CoRR abs\/1402.0050 (2014), Accepted to ICALP 2014","DOI":"10.1007\/978-3-662-43951-7_31"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T17:45:26Z","timestamp":1649353526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}