{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:41Z","timestamp":1725662861652},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540084426"},{"type":"electronic","value":"9783540370840"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08442-8_111","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:28:26Z","timestamp":1330187306000},"page":"423-434","source":"Crossref","is-referenced-by-count":0,"title":["The equivalences problems for binary EOL-Systems are decidable"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpi\u0144ski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"48_CR1","first-page":"463","volume":"7","author":"M. Blattner","year":"1972","unstructured":"Blattner, M. (1972; 1973), The unsolvability of the equality problem for sentential forms of context-free grammars, Notices Amer. Math. Soc., Abstract 72T-C15, p. A-325, and J. Comput. System Sci. 7, 463\u2013468.","journal-title":"Notices Amer. Math. Soc., Abstract 72T-C15, p. A-325, and J. Comput. System Sci."},{"key":"48_CR2","first-page":"1","volume-title":"On a decision method in restricted second order arithmetic","author":"J. R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R. (1960), On a decision method in restricted second order arithmetic, Proc. Internat. Congr. Logic, Method. and Philos. Sci., Stanford Univ. Press, Stanford, California, 1962, pp. 1\u201311."},{"key":"48_CR3","first-page":"834","volume":"5","author":"J. R. B\u00fcchi","year":"1958","unstructured":"B\u00fcchi, J.R. and Elgot, C.C. (1958), Decision problems of weak second-order arithmetics and finite automata. Part I, Abstract 553-112, Notices Amer. Math. Soc. 5, 834.","journal-title":"Notices Amer. Math. Soc."},{"key":"48_CR4","first-page":"819","volume":"12","author":"J. E. Doner","year":"1965","unstructured":"Doner, J.E. (1965), Decidability of the weak second-order theory of two successors, Notices Amer. Math. Soc. 12, 819.","journal-title":"Notices Amer. Math. Soc."},{"key":"48_CR5","volume-title":"Developmental systems and Languages","author":"G. T. Herman","year":"1975","unstructured":"Herman, G.T. and Rozenberg, G. (1975), Developmental systems and Languages, North-Holland, Amsterdam."},{"key":"48_CR6","first-page":"441","volume":"21","author":"M. Karpi\u0144ski","year":"1973","unstructured":"Karpi\u0144ski, M. (1973, 1974), Free structure tree automata I\u2013IV, Bull. Acad. Polon. Sci., S\u00e9r. Sci. Math. Astronom. Phys. 21, 441\u2013446, 447\u2013450, 567\u2013572, 22, 87\u201391.","journal-title":"Bull. Acad. Polon. Sci., S\u00e9r. Sci. Math. Astronom. Phys."},{"key":"48_CR7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.2307\/2040034","volume":"53","author":"M. Karpi\u0144ski","year":"1975","unstructured":"Karpi\u0144ski, M. (1975), Almost deterministic \u03c9-automata with existential output condition, Proc. Amer. Math. Soc. 53, 449\u2013452.","journal-title":"Proc. Amer. Math. Soc."},{"key":"48_CR8","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0022-5193(68)90079-9","volume":"18","author":"A. Lindenmayer","year":"1968","unstructured":"Lindenmayer, A. (1968), Mathematical models for cellular interaction in development, Part I, and II, J. Theoret. Biol. 18, 280\u2013315.","journal-title":"J. Theoret. Biol."},{"key":"48_CR9","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/BF02798680","volume":"8","author":"M. Magidor","year":"1970","unstructured":"Magidor, M. and Moran, G. (1970), Probablistic tree automata and context-free languages, Israel J. Math. 8, 340\u2013348.","journal-title":"Israel J. Math."},{"key":"48_CR10","series-title":"Tech. Rept.","volume-title":"Finite automata over finite trees","author":"M. Magidor","year":"1969","unstructured":"Magidor, M. and Moran, G. (1969), Finite automata over finite trees, Tech. Rept. 30, Hebrew University, Jerusalem, Israel."},{"key":"48_CR11","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R. (1967), Parenthesis grammars, J. Assoc. Comp. Mach. 14, 490\u2013500.","journal-title":"J. Assoc. Comp. Mach."},{"key":"48_CR12","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/S0019-9958(74)90857-2","volume":"25","author":"M. Nielsen","year":"1974","unstructured":"Nielsen, M. (1974), On the decidability of some equivalence problems for DOL-systems, Information and Control 25, 166\u2013193.","journal-title":"Information and Control"},{"key":"48_CR13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/S0022-0000(68)80037-6","volume":"2","author":"M. C. Paul","year":"1968","unstructured":"Paul, M.C., and Unger, S.H. (1968), Structural equivalence of context-free grammars, J. Comput. System Sci. 2, 427\u2013463.","journal-title":"J. Comput. System Sci."},{"key":"48_CR14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. O. Rabin","year":"1959","unstructured":"Rabin, M.O. and Scott, D. (1959), Finite automata and their decision problems, IBM J. Res. Develop. 3, 114\u2013125, reprinted in Sequential machines, selected papers, edited by E.F. Moore, Addison-Wesley, Reading, Mass., 1964.","journal-title":"IBM J. Res. Develop."},{"key":"48_CR15","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1090\/psapm\/019\/0239886","volume":"19","author":"M. O. Rabin","year":"1968","unstructured":"Rabin, M.O. (1968), Mathematical theory of automata, proc. Sympos. Appl. Math. Vol. 19, Amer. Math. Soc., Providence, R.I., 1968, pp. 153\u2013175.","journal-title":"proc. Sympos. Appl. Math."},{"key":"48_CR16","first-page":"1","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"Rabin, M.O. (1969), Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141, 1\u201335.","journal-title":"Trans. Amer. Math. Soc."},{"key":"48_CR17","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(72)90018-X","volume":"1","author":"G. Rozenberg","year":"1972","unstructured":"Rozenberg, G. (1972 a), Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL-systems, Information Process. Lett. 1, 233.","journal-title":"Information Process. Lett."},{"key":"48_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(72)90039-7","volume":"1","author":"G. Rozenberg","year":"1972","unstructured":"Rozenberg, G. (1972 b), The equivalence problem for deterministic TOL-systems is undecidable, Inform. Process. Lett. 1, 201.","journal-title":"Inform. Process. Lett."},{"volume-title":"L Systems, Lecture Notes in Computer Science, Vol. 15","year":"1974","key":"48_CR19","unstructured":"Rozenberg, G. and Salomaa, A. eds. (1974), L Systems, Lecture Notes in Computer Science, Vol. 15, Springer-Verlag, Berlin."},{"key":"48_CR20","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/BF00571462","volume":"2","author":"A. Salomaa","year":"1972","unstructured":"Salomaa, A. (1972 a), On sentential forms of context-free grammars, Acta Informatika 2, 40.","journal-title":"Acta Informatika"},{"key":"48_CR21","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"Salomaa, A. (1973 b), Formal Languages, Academic Press, New York."},{"key":"48_CR22","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","volume":"1","author":"J. W. Thatcher","year":"1967","unstructured":"Thatcher, J.W. (1967), Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, J. Comput. System Sci. 1, 317\u2013322.","journal-title":"J. Comput. System Sci."},{"key":"48_CR23","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"Thatcher, J.W. and Wright, J.B. (1968), Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory 2, 57\u201381.","journal-title":"Mathematical Systems Theory"},{"key":"48_CR24","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S0022-0000(70)80017-4","volume":"4","author":"J. W. Thatcher","year":"1970","unstructured":"Thatcher, J.W. (1970), Generalized2 sequential machines, J. Comput. System Sci. 4, 339\u2013367.","journal-title":"J. Comput. System Sci."},{"key":"48_CR25","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/1385-7258(73)90011-5","volume":"35","author":"P. Vit\u00e1nyi","year":"1973","unstructured":"Vit\u00e1nyi, P. (1973), Structure of growth in Lindenmayer systems, Indagationes Mathematicae 35, 247\u2013253.","journal-title":"Indagationes Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08442-8_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:52:23Z","timestamp":1619556743000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08442-8_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540084426","9783540370840"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-08442-8_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}