{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T01:48:51Z","timestamp":1672624131952},"publisher-location":"Berlin, Heidelberg","reference-count":62,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540421214","type":"print"},{"value":"9783540451327","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45132-3_8","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T17:00:06Z","timestamp":1194973206000},"page":"133-152","source":"Crossref","is-referenced-by-count":6,"title":["The Equivalence Problem for Computational Models: Decidable and Undecidable Cases"],"prefix":"10.1007","author":[{"given":"Vladimir A.","family":"Zakharov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,5,9]]},"reference":[{"key":"8_CR1","unstructured":"K. Apt, From Logic Programming to Prolog, Prentice Hall, 1997."},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1145\/321765.321780","volume":"20","author":"E. Ashcroft","year":"1973","unstructured":"E. Ashcroft, Z. Manna, A. Pnueli, A Decidable properties of monadic functional schemes, J. ACM, vol 20 (1973), N 3, p.489\u2013499.","journal-title":"J. ACM"},{"key":"8_CR3","first-page":"245","volume":"15","author":"J.M. Barzdin","year":"1965","unstructured":"J.M. Barzdin, The complexity of recognition the symmetry by Turing machines. In Problemy Kibernetiky, 15, 1965, p.245\u2013248 (in Russian).","journal-title":"Problemy Kibernetiky"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/S0022-0000(73)80045-5","volume":"7","author":"M. Bird","year":"1973","unstructured":"M. Bird, The equivalence problem for deterministic two-tape automata, J. Comput. Syst. Sci., 7, 1973, p.218\u2013236.","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR5","series-title":"Tech. Report","first-page":"45","volume-title":"Abstract computing machines","author":"A.O. Buda","year":"1978","unstructured":"A.O. Buda, Abstract computing machines. Tech. Report, Comp. Center of the USSR Academy of Science, Novosibirsk, N 108, 1978, 45 p (in Russian).."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"D. Cozen, Automata and computability. Springer, 1997, 400 p.","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"8_CR7","first-page":"218","volume":"27","author":"K. Culik II","year":"1989","unstructured":"K. Culik II, J. Karhumaki, HDT0L matching of computations of multitape automata, Act. Inform., 27, 1989, p.218\u2013236.","journal-title":"Act. Inform."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0304-3975(90)90189-O","volume":"71","author":"K. Culik II","year":"1990","unstructured":"K. Culik II, New techniques for proving the decidability of equivalence problems. Theor. Comput. Sci., 71, 1990, p.29\u201345.","journal-title":"Theor. Comput. Sci."},{"key":"8_CR9","series-title":"Unpublished notes","volume-title":"A theory of programs","author":"J.W. Bakker De","year":"1969","unstructured":"J.W.De Bakker, D.A. Scott, A theory of programs. Unpublished notes, Vienna: IBM Seminar, 1969."},{"key":"8_CR10","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg, Automata, Languages, and Machines. vol A, Academic Press, New-York, 1974."},{"key":"8_CR11","first-page":"93","volume":"71","author":"A.P. Ershov","year":"1971","unstructured":"A.P. Ershov, Theory of program schemata. In Proc. of IFIP Congress 71, Ljubljana, 1971, p.93\u2013124.","journal-title":"Proc. of IFIP Congress"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"D. Harel, Dynamic logics. In Handbook of Philosophical Logics, Comput. Sci., D. Gabbay and F. Guenthner (eds.), 1984, p.497\u2013604.","DOI":"10.1007\/978-94-009-6259-0_10"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-3975(91)90356-7","volume":"78","author":"T. Harju","year":"1991","unstructured":"T. Harju, J. Karhumaki, The equivalence of multi-tape finite automata. Theoret. Comput. Sci., 78, 1991, p.347\u2013355.","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/3-540-60915-6_4","volume-title":"Decidable results in automata and process theory","author":"Y. Hirshfeld","year":"1996","unstructured":"Y. Hirshfeld, F. Moller, Decidable results in automata and process theory. LNCS, 1043, 1996, p.102\u2013148."},{"key":"8_CR15","volume-title":"A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson, A guide to the theory of NP-completeness, San-Francisco: W.H.Freeman & Company Publishers, 1979."},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0022-0000(73)80040-6","volume":"7","author":"S.J. Garland","year":"1973","unstructured":"S.J. Garland, D.C. Luckham, Program schemes, recursion schemes and formal languages, J. Comput. and Syst. Sci., 7, 1973, p.119\u2013160.","journal-title":"J. Comput. and Syst. Sci."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"V.M. Glushkov, A.A. Letichevskii, Theory of algorithms and discrete processors, In Advances in Information System Science, vol 1 (1969), N 1.","DOI":"10.1007\/978-1-4615-9050-7_1"},{"key":"8_CR18","unstructured":"A.B. Godlevsky, On some specific cases of halting problem and equivalence problem for automata. Cybernetics, 1973, N 4, p.90\u201397 (in Russian)."},{"key":"8_CR19","unstructured":"A.B. Godlevsky, On some special case of the functional equivalence problem for discrete transformers. Cybernetics, 1974, N 3, p.32\u201336 (in Russian)."},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T.V. Griffits","year":"1968","unstructured":"T.V. Griffits, The unsolvability of the equivalence problem for \u03bb-free nondeterministic generalized machines. J. ACM, 15, 1968, p.409\u2013413.","journal-title":"J. ACM"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0022-0000(72)80041-2","volume":"6","author":"V.E. Itkin","year":"1972","unstructured":"V.E. Itkin, Z. Zinogrodski, On program schemata equivalence. J. Comput. and Syst. Sci., 6, 1972, p.88\u2013101.","journal-title":"J. Comput. and Syst. Sci."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"V.E. Itkin, Logic-term equivalence of program schemata. Cybernetics, 1972, N 1, p.5\u201327 (in Russian)","DOI":"10.1007\/BF01069127"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(83)90077-4","volume":"26","author":"E. Kinber","year":"1983","unstructured":"E. Kinber, The inclusion problem for some classes of deterministic multitape automata. Theoret. Comput. Sci., 26, 1983, p.1\u201324.","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR24","unstructured":"A.A. Lapunov, Yu.I. Yanov, On logical program schemata, In Proc. Conf. Perspectives of the Soviet Mathematical Machinery, Moscow, March 12-17, 1956, Part III."},{"key":"8_CR25","unstructured":"A.A. Letichevsky, On the equivalence of automata with final states on the free monoids having right zero. Dokl. Akad. Nauk SSSR, 182, 1968, N 5 (in Russian)."},{"key":"8_CR26","first-page":"3","volume":"6","author":"A.A. Letichevsky","year":"1970","unstructured":"A.A. Letichevsky, On the equivalence of automata over semigroup, Theoretic Cybernetics, 6, 1970, p.3\u201371 (in Russian).","journal-title":"Theoretic Cybernetics"},{"issue":"2","key":"8_CR27","first-page":"14","volume":"II","author":"A.A. Letichevsky","year":"1970","unstructured":"A.A. Letichevsky, Functional equivalence of finite transformers. II. Cybernetics, 1970, N 2, p.14\u201328 (in Russian)","journal-title":"Cybernetics"},{"issue":"1","key":"8_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01070656","volume":"III","author":"A.A. Letichevsky","year":"1972","unstructured":"A.A. Letichevsky, Functional equivalence of finite transformers. III. Cybernetics, 1972, N 1, p.1\u20134 (in Russian)","journal-title":"Cybernetics"},{"key":"8_CR29","unstructured":"A.A. Letichevsky, Equivalence and optimization of programs. In Programming theory, Part 1, Novosibirsk, 1973, p. 166\u2013180 (in Russian)."},{"issue":"2","key":"8_CR30","first-page":"341","volume":"17","author":"A.A. Letichevsky","year":"1976","unstructured":"A.A. Letichevsky, L.B. Smikun, On a class of groups with solvable problem of automata equivalence, Sov. Math. Dokl., 17, 1976, N 2, p.341\u2013344.","journal-title":"Sov. Math. Dokl."},{"key":"8_CR31","unstructured":"H.R. Lewis, A new decidable problem with applications. In Proc 18th FOCS Conf., 1979, p.62\u201373."},{"key":"8_CR32","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D.C. Luckham","year":"1970","unstructured":"D.C. Luckham, D.M. Park, M.S. Paterson, On formalized computer programs, J. Comput. and Syst. Sci., 4, 1970, N 3, p.220\u2013249.","journal-title":"J. Comput. and Syst. Sci."},{"key":"8_CR33","series-title":"Lect Notes Comput Sci","first-page":"279","volume-title":"Trace theory","author":"A. Mazurkiewicz","year":"1987","unstructured":"A. Mazurkiewicz, Trace theory. LNCS, 255, 1987, p.279\u2013324."},{"key":"8_CR34","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0049-237X(08)72018-4","volume-title":"Computer Programming and Formal Systems","author":"J. McCarthy","year":"1963","unstructured":"J. McCarthy, A basis for a mathematical theory of computation. In Computer Programming and Formal Systems. Amsterdam: North-Holl. Publ. Co., 1963, p.33\u201370."},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"R. Milner, Processes: a mathematical model of computing agents. In Proc. of Logic Colloquium\u201973, 1973, p.157\u2013174.","DOI":"10.1016\/S0049-237X(08)71948-7"},{"key":"8_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1007\/3-540-07854-1_212","volume-title":"On divergence problem for program schemes","author":"V.A. Nepomniaschy","year":"1976","unstructured":"V.A. Nepomniaschy, On divergence problem for program schemes. LNCS, 45, 1976, p.442\u2013445."},{"key":"8_CR37","unstructured":"V.A. Nepomniaschy, On the emptiness problem for program schemes. Programming and Software Engineering, 1977, N 4, p.3\u201313 (in Russian)."},{"key":"8_CR38","doi-asserted-by":"crossref","unstructured":"A.G. Oettinger, Automatic syntactic analysis and pushdown store. In Proc. Symposia on Applied Math., 12, 1961.","DOI":"10.1090\/psapm\/012\/9975"},{"key":"8_CR39","first-page":"19","volume-title":"Machine Intelligence","author":"M.S. Paterson","year":"1968","unstructured":"M.S. Paterson, Programs schemata, Machine Intelligence, Edinburgh: Univ. Press, 3, 1968, p.19\u201331."},{"key":"8_CR40","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/942578.807074","volume":"7","author":"M.S. Paterson","year":"1972","unstructured":"M.S. Paterson, Decision problems in computational models, SIGPLAN Notices, 7, 1972, p.74\u201382.","journal-title":"SIGPLAN Notices"},{"key":"8_CR41","unstructured":"G.N. Petrosyan, On one basis of statements and predicates for which the emptiness problem is undecidable. Cybernetics, 1974, N 5, p.23\u201328 (in Russian)."},{"key":"8_CR42","unstructured":"R.I. Podlovchenko, On the decidability of the equivalence problem on a class of program schemata having monotonic and partially commutative statements. Programming and Software Engineering, 1990, N 5, p.3\u201312 (in Russian)."},{"key":"8_CR43","unstructured":"R.I. Podlovchenko, V.A. Zakharov, On the polynomial-time algorithm deciding the commutative equivalence of program schemata, Reports of the Russian Academy of Science, 362, 1998, N 6 (in Russian)."},{"key":"8_CR44","doi-asserted-by":"crossref","unstructured":"V.R. Pratt, Semantical considerations of Floyd-Hoare logic. In Proc. 17th IEEE Symp. Found. Comput. Sci., 1976, p.109\u2013121","DOI":"10.1109\/SFCS.1976.27"},{"issue":"2","key":"8_CR45","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"M.O. Rabin, D. Scott, Finite automata and their decision problems. IBM J. Res. Dev., 3, 1959, N 2, p.114\u2013125.","journal-title":"IBM J. Res. Dev."},{"key":"8_CR46","first-page":"25","volume":"bf 89","author":"H.G. Rice","year":"1953","unstructured":"H.G. Rice. Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc., bf 89, 1953, p. 25\u201359.","journal-title":"Trans. Amer. Math. Soc."},{"key":"8_CR47","unstructured":"H. Rogers, Theory of recursive functions and effective computability. McGraw-Hill, 1967."},{"key":"8_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321203.321204","volume":"11","author":"J.D. Rutledge","year":"1964","unstructured":"J.D. Rutledge, On Ianov\u2019s program schemata, J. ACM, 11, 1964, p.1\u20139.","journal-title":"J. ACM"},{"issue":"4","key":"8_CR49","first-page":"793","volume":"249","author":"V.K. Sabelfeld","year":"1979","unstructured":"V.K. Sabelfeld, Logic-term equivalence is checkable in polynomial time. Reports of the Soviet Academy of Science, 249, 1979, N 4, p.793\u2013796 (in Russian).","journal-title":"Reports of the Soviet Academy of Science"},{"key":"8_CR50","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(90)90201-R","volume":"71","author":"V.K. Sabelfeld","year":"1990","unstructured":"V.K. Sabelfeld, An algorithm deciding functional equivalence in a new class of program schemata, Theoret. Comput. Sci., 71, 1990, p.265\u2013279.","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR51","series-title":"Lect Notes Comput Sci","first-page":"271","volume-title":"The equivalence problem for deterministic pushdown automata is decidable","author":"G. Senizergues","year":"1997","unstructured":"G. Senizergues, The equivalence problem for deterministic pushdown automata is decidable, LNCS, 1256, 1997, p.271\u2013281."},{"key":"8_CR52","doi-asserted-by":"crossref","unstructured":"M.A. Taiclin,The equivalence of automata w.r.t. commutative semigroups, Algebra and Logic, 8, 1969, p.553\u2013600 (in Russian).","DOI":"10.1007\/BF02219786"},{"key":"8_CR53","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF01178385","volume":"32","author":"E. Tomita","year":"1995","unstructured":"E. Tomita, K. Seino, The extended equivalence problem for a class of non-real-time deterministic pushdown automata. Acta Informatica, 32, 1995, p.395\u2013413.","journal-title":"Acta Informatica"},{"key":"8_CR54","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/3-540-11157-3_27","volume-title":"What are the gains of the theory of algorithms: basic developments connected with the concept of algorithm and with its application in mathematics","author":"V.A. Uspensky","year":"1981","unstructured":"V.A. Uspensky, A.L. Semenov, What are the gains of the theory of algorithms: basic developments connected with the concept of algorithm and with its application in mathematics. LNCS, bf 122, 1981, p.100\u2013234."},{"key":"8_CR55","unstructured":"L.G. Valiant, Decision procedures for families of deterministic pushdown automata, Report N 7, Univ. of Warwick Computer Center, 1973."},{"key":"8_CR56","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","volume":"25","author":"L.G. Valiant","year":"1974","unstructured":"L.G. Valiant, The equivalence problem for deterministic finite-turn pushdown automata, Information and Control, 25, 1974, p.123\u2013133.","journal-title":"Information and Control"},{"key":"8_CR57","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/S0022-0000(75)80005-5","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"L.G. Valiant, M.S. Paterson, Deterministic one-counter automata, J. of Comput. And Syst. Sci., 10, 1975, p.340\u2013350.","journal-title":"J. of Comput. And Syst. Sci."},{"issue":"1","key":"8_CR58","first-page":"39","volume":"113","author":"J. Yanov","year":"1957","unstructured":"J. Yanov, To the equivalence and transformations of program schemata, Reports of the Soviet Academy of Science, 113, 1957, N 1, p.39\u201342 (in Russian).","journal-title":"Reports of the Soviet Academy of Science"},{"key":"8_CR59","series-title":"Lect Notes Comput Sci","first-page":"246","volume-title":"The efficient and unified approach to the decidability of the equivalence of propositional programs","author":"V.A. Zakharov","year":"1998","unstructured":"V.A. Zakharov, The efficient and unified approach to the decidability of the equivalence of propositional programs. In LNCS, 1443, 1998, p. 246\u2013258."},{"key":"8_CR60","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1023\/A:1009954232570","volume":"2","author":"V.A. Zakharov","year":"1999","unstructured":"V.A. Zakharov, On the decidability of the equivalence problem for orthogonal sequential programs, Grammars, 2, 1999, p.271\u2013281.","journal-title":"Grammars"},{"key":"8_CR61","unstructured":"V.A. Zakharov, On the uniform technique for designing decision procedures for the equivalence of propositional sequential programs. In Proc. of the 4th Int. Conf. on Discrete Models in Control System Theory, Krasnovidovo, 2000, p.25\u201329 (in Russian)."},{"key":"8_CR62","unstructured":"V.A. Zakharov, On the equivalence problem for sequential program schemata supplied with reset statements. In Proc. of the 4th Int. Conf. on Discrete Models in Control System Theory, Krasnovidovo, 2000, p.153\u2013154 (in Russian)."}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45132-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T10:10:14Z","timestamp":1556964614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45132-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540421214","9783540451327"],"references-count":62,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-45132-3_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"published":{"date-parts":[[2001]]}}}