{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:19Z","timestamp":1761611299771,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609155"},{"type":"electronic","value":"9783540496755"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60915-6_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:03:30Z","timestamp":1330290210000},"page":"102-148","source":"Crossref","is-referenced-by-count":7,"title":["Decidability results in automata and process theory"],"prefix":"10.1007","author":[{"given":"Yoram","family":"Hirshfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Faron","family":"Moller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"4_CR1","unstructured":"P. Aczel. Non-well-founded Sets. CSLI Lecture Notes 14, Stanford University, 1988."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/174130.174141","volume":"40","author":"J.C.M. Baeten","year":"1993","unstructured":"J.C.M. Baeten, J.A. Bergstra and J.W. Klop. Decidability of bisimulation equivalence for processes generating context-free languages. Journal of the ACM 40, pp653\u2013682, 1993.","journal-title":"Journal of the ACM"},{"key":"4_CR3","first-page":"143","volume":"14","author":"Y. Bar-Hillel","year":"1961","unstructured":"Y. Bar-Hillel, M. Perles and E. Shamir. On formal properties of simple phrase structure grammars. Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14, pp143\u2013177, 1961.","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft, und Kommunikationsforschung"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(85)90088-X","volume":"37","author":"J.A. Bergstra","year":"1985","unstructured":"J.A. Bergstra and J.W. Klop. Algebra of Communicating Processes with Abstraction. Theoretical Computer Science 37, pp77\u2013121, 1985.","journal-title":"Theoretical Computer Science"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"G. Boudol. Notes on algebraic calculi of processes. In K. Apt (ed), Logics and Models of Concurrent Systems, NATO ASI Series f13, 1985.","DOI":"10.1007\/978-3-642-82453-1_9"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"J.C. Bradfield. Verifying Temporal Properties of Systems. Birkh\u00e4user, 1991.","DOI":"10.1007\/978-1-4684-6819-9"},{"key":"4_CR7","unstructured":"E. Brinksma. Information Processing Systems \u2014 Open Systems Interconnection \u2014 LOTOS \u2014 A formal description technique based upon the temporal ordering of observable behaviour. Draft International Standard ISO8807, 1988."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1145\/828.833","volume":"31","author":"S.D. Brookes","year":"1984","unstructured":"S.D. Brookes, C.A.R. Hoare and A.W. Roscoe. A theory of Communicating Sequential Processes. Journal of the ACM 31, pp560\u2013599, 1984.","journal-title":"Journal of the ACM"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"O. Burkart and B. Steffen. Model checking for context-free processes. In Proceedings of CONCUR 92, W.R. Cleaveland (ed), Lecture Notes in Computer Science 630, pp123\u2013137. Springer-Verlag, 1992.","DOI":"10.1007\/BFb0084787"},{"issue":"4","key":"4_CR10","first-page":"339","volume":"24","author":"D. Caucal","year":"1990","unstructured":"D. Caucal. Graphes canoniques des graphes alg\u00e9briques. Informatique Th\u00e9orique et Applications (RAIRO) 24(4), pp339\u2013352, 1990.","journal-title":"Informatique Th\u00e9orique et Applications (RAIRO)"},{"issue":"1","key":"4_CR11","first-page":"23","volume":"27","author":"D. Caucal","year":"1993","unstructured":"D. Caucal. A fast algorithm to decide on the equivalence of stateless DPDA. Informatique Th\u00e9orique et Applications (RAIRO) 27(1), pp23\u201348, 1993.","journal-title":"Informatique Th\u00e9orique et Applications (RAIRO)"},{"key":"4_CR12","unstructured":"S. Christensen. Decidability and Decomposition in Process Algebras. Ph.D. Thesis ECS-LFCS-93-278, Department of Computer Science, University of Edinburgh, 1993."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"S. Christensen. Distributed bisimilarity is decidable for a class of infinitestate processes. In Proceedings of CONCUR 92, W.R. Cleaveland (ed), Lecture Notes in Computer Science 630, pp148\u2013161. Springer-Verlag, 1992.","DOI":"10.1007\/BFb0084789"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"S. Christensen, Y. Hirshfeld and F. Moller. Decomposability, decidability and axiomatisability for bisimulation equivalence on basic parallel processes. In Proceedings of LICS93. IEEE Computer Society Press, 1993.","DOI":"10.1109\/LICS.1993.287569"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"S. Christensen, Y. Hirshfeld and F. Moller. Bisimulation equivalence is decidable for basic parallel processes. In Proceedings of CONCUR93, E. Best (ed), Lecture Notes in Computer Science 715, pp143\u2013157, Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57208-2_11"},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1093\/comjnl\/37.4.233","volume":"37","author":"S. Christensen","year":"1994","unstructured":"S. Christensen, Y. Hirshfeld and F. Moller. Decidable subsets of CCS. The Computer Journal 37(4), pp233\u2013242, 1994.","journal-title":"The Computer Journal"},{"key":"4_CR17","first-page":"156","volume":"51","author":"S. Christensen","year":"1993","unstructured":"S. Christensen and H. H\u00fcttel. Decidability issues for infinite-state processes \u2014 a survey. Bulletin of the EATCS 51, pp156\u2013166, October 1993.","journal-title":"Bulletin of the EATCS"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"S. Christensen, H. H\u00fcttel and C. Stirling. Bisimulation equivalence is decidable for all context-free processes. In Proceedings of CONCUR 92, W.R. Cleaveland (ed), Lecture Notes in Computer Science 630, pp138\u2013147. Springer-Verlag, 1992.","DOI":"10.1007\/BFb0084788"},{"key":"4_CR19","first-page":"245","volume":"52","author":"J. Esparza","year":"1994","unstructured":"J. Esparza and M. Nielsen. Decidability issues for Petri nets \u2014 a survey. Bulletin of the EATCS 52, pp245\u2013262, February 1994.","journal-title":"Bulletin of the EATCS"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(76)90074-8","volume":"1","author":"E.P. Friedman","year":"1976","unstructured":"E.P. Friedman. The inclusion problem for simple languages. Theoretical Computer Science 1, pp297\u2013316, 1976.","journal-title":"Theoretical Computer Science"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"R.J. van Glabbeek. The linear time-branching time spectrum. In Proceedings of CONCUR 90, J. Baeten, J.W. Klop (eds), Lecture Notes in Computer Science 458, pp278\u2013297. Springer-Verlag, 1990.","DOI":"10.1007\/BFb0039066"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(92)90142-I","volume":"42","author":"J.F. Groote","year":"1991","unstructured":"J.F. Groote. A short proof of the decidability of bisimulation for normed BPA processes. Information Processing Letters 42, pp167\u2013171, 1991.","journal-title":"Information Processing Letters"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"J.F. Groote and H. H\u00fcttel. Undecidable equivalences for basic process algebra. Information and Computation, 1994.","DOI":"10.1006\/inco.1994.1101"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"J.F. Groote and F. Moller. Verification of parallel systems via decomposition. In Proceedings of CONCUR 92, W.R. Cleaveland (ed), Lecture Notes in Computer Science 630, pp62\u201376. Springer-Verlag, 1992.","DOI":"10.1007\/BFb0084783"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld. Petri Nets and the Equivalence Problem. In Proceedings of CSL'93, K. Meinke (ed), Lecture Notes in Computer Science Springer-Verlag, 1994.","DOI":"10.1007\/BFb0049331"},{"key":"4_CR26","unstructured":"Y. Hirshfeld. Deciding equivalences in simple process algebras. In Proceedings of a 3-day Workshop on Bisimulation, Amsterdam, April, 1994."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld, M. Jerrum and F. Moller, A polynomial algorithm for deciding bisimilarity of normed context-free processes. Submitted to Theoretical Computer Science, 1994.","DOI":"10.1007\/978-3-540-48654-1_5"},{"key":"4_CR28","unstructured":"Y. Hirshfeld, M. Jerrum and F. Moller, A polynomial algorithm for deciding bisimulation equivalence of normed basic parallel processes. Submitted to Mathematical Structures in Computer Science, 1994."},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld and F. Moller. A fast algorithm for deciding bisimilarity of normed context-free processes. In Proceedings of CONCUR'94, J. Parrow (ed), Lecture Notes in Computer Science. Springer-Verlag, 1994.","DOI":"10.1007\/978-3-540-48654-1_5"},{"key":"4_CR30","unstructured":"M. Hennessy. Algebraic Theory of Processes. MIT Press, 1989."},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1145\/359576.359585","volume":"21","author":"C.A.R. Hoare","year":"1978","unstructured":"C.A.R. Hoare. Communicating Sequential Processes. Communications of the ACM 21, pp666\u2013677, 1978.","journal-title":"Communications of the ACM"},{"key":"4_CR32","unstructured":"C.A.R. Hoare. Communicating Sequential Processes. Prentice-Hall, 1988."},{"key":"4_CR33","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979."},{"key":"4_CR34","unstructured":"H. H\u00fcttel. Decidability, Behavioural Equivalences and Infinite Transition Graphs. Ph.D. Thesis ECS-LFCS-91-191, Department of Computer Science, University of Edinburgh, 1991."},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"H. H\u00fcttel. Undecidable equivalences for basic parallel processes. In Proceedings of FSTTCS'93, 1993.","DOI":"10.1007\/3-540-57887-0_110"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"H. H\u00fcttel and C. Stirling. Actions speak louder than words: proving bisimilarity for context-free processes. In Proceedings of LICS'91, IEEE Computer Society Press, pp376\u2013386, 1991.","DOI":"10.1109\/LICS.1991.151661"},{"key":"4_CR37","volume-title":"Technical report UTDCS-31-90","author":"D.T. Huynh","year":"1990","unstructured":"D.T. Huynh and L. Tian. On deciding readiness and failure equivalences for processes. Technical report UTDCS-31-90, Department of Computer Science, University of Texas at Dallas, September 1990."},{"key":"4_CR38","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)00078-6","volume":"123","author":"D.T. Huynh","year":"1994","unstructured":"D.T. Huynh and L. Tian. Deciding bisimilarity of normed context-free processes is in \u2211 2 P . Theoretical Computer Science 123, pp183\u2013197, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR39","first-page":"51","volume":"28","author":"D.T. Huynh","year":"1994","unstructured":"D.T. Huynh and L. Tian. On deciding some equivalences for concurrent processes. Informatique Th\u00e9orique et Applications (RAIRO) 28(1), pp51\u201371, 1994.","journal-title":"Informatique Th\u00e9orique et Applications (RAIRO)"},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"P. Jan\u010dar. Decidability questions for bisimilarity of Petri nets and some related problems. In Proceedings of STACS'94, P. Enjalbert, E.W. Mayr and K.W. Wagner (eds), Lecture Notes in Computer Science 775, pp581\u2013592, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-57785-8_173"},{"key":"4_CR41","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0890-5401(90)90025-D","volume":"86","author":"P.C. Kanellakis","year":"1990","unstructured":"P.C. Kanellakis and S.A. Smolka. CCS expressions, finite-state processes and three problems of equivalence. Information and Computation (86), pp43\u201368, 1990.","journal-title":"Information and Computation"},{"key":"4_CR42","first-page":"3","volume-title":"Automata Studies","author":"S.C. Kleene","year":"1956","unstructured":"S.C. Kleene. Representation of events in nerve nets and finite automata. In Automata Studies, pp3\u201342, Princeton University Press, Princeton, 1956"},{"key":"4_CR43","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J.H. Morris, and V.R. Pratt, Fast pattern matching in strings, SIAM Journal on Computing 6, pp323\u2013350, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR44","doi-asserted-by":"crossref","unstructured":"A. Korenjak and J. Hopcroft. Simple deterministic languages. In Proceedings of 7th IEEE Switching and Automata Theory conference. pp36\u201346, 1966.","DOI":"10.1109\/SWAT.1966.22"},{"key":"4_CR45","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","volume":"5","author":"W.S. McCullock","year":"1943","unstructured":"W.S. McCullock and W. Pitts A logical calculus of the ideas immanent in nervous activity. Bull Math Biophysics 5, pp115\u2013133, 1943.","journal-title":"Bull Math Biophysics"},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"R. Milner. Processes: a mathematical model of computing agents. In Proceedings of Logic Colloquium'73, Rose and Shepherdson (eds), pp157\u2013174, North Holland, 1973.","DOI":"10.1016\/S0049-237X(08)71948-7"},{"key":"4_CR47","doi-asserted-by":"crossref","unstructured":"R. Milner. A Calculus of Communicating Systems. Lecture Notes in Computer Science 92, Springer-Verlag, 1980.","DOI":"10.1007\/3-540-10235-3"},{"key":"4_CR48","unstructured":"R. Milner. Communication and Concurrency. Prentice-Hall, 1989."},{"key":"4_CR49","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/0304-3975(93)90176-T","volume":"107","author":"R. Milner","year":"1993","unstructured":"R. Milner and F. Moller. Unique decomposition of processes. Theoretical Computer Science 107, pp357\u2013363, 1993.","journal-title":"Theoretical Computer Science"},{"key":"4_CR50","first-page":"129","volume-title":"Automata Studies","author":"E.F. Moore","year":"1956","unstructured":"E.F. Moore. Gedanken experiments on sequential machines. In Automata Studies, pp129\u2013153, Princeton University Press, Princeton, 1956"},{"key":"4_CR51","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. Muller","year":"1985","unstructured":"D. Muller and P. Schupp. The theory of ends, pushdown automata and second order logic. Theoretical Computer Science 37, pp51\u201375, 1985.","journal-title":"Theoretical Computer Science"},{"key":"4_CR52","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing 16, pp937\u2013989, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR53","doi-asserted-by":"crossref","unstructured":"D.M.R. Park. Concurrency and Automata on Infinite Sequences. Lecture Notes in Computer Science 104, pp168\u2013183, Springer Verlag, 1981.","DOI":"10.1007\/BFb0017309"},{"key":"4_CR54","doi-asserted-by":"crossref","unstructured":"W. Reisig. Petri Nets: An Introduction. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985.","DOI":"10.1007\/978-3-642-69968-9"},{"key":"4_CR55","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"L.J. Stockmeyer. The polynomial time hierarchy. Theoretical Computer Science 3, pp1\u201322, 1977.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Logics for Concurrency"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60915-6_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:40Z","timestamp":1742598640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60915-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609155","9783540496755"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/3-540-60915-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}