{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:52:19Z","timestamp":1757541139154},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1986,9,1]],"date-time":"1986-09-01T00:00:00Z","timestamp":525916800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1986,9]]},"DOI":"10.1007\/bf00288472","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T12:43:28Z","timestamp":1096893808000},"page":"597-605","source":"Crossref","is-referenced-by-count":8,"title":["Synchronizable deterministic pushdown automata and the decidability of their equivalence"],"prefix":"10.1007","volume":"23","author":[{"suffix":"II","given":"Karel","family":"Culik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF00288472_CR1","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/S0019-9958(82)80028-4","volume":"52","author":"J. Albert","year":"1982","unstructured":"Albert, J., Culik II, K., Karhum\u00e4ki, J.: Test sets for context-free languages and algebraic systems of equations. Inf. Control 52, 172\u2013186 (1982)","journal-title":"Inf. Control"},{"key":"BF00288472_CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90049-9","volume":"3","author":"C. Beeri","year":"1976","unstructured":"Beeri, C.: An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines, Theor. Comput. Sci. 3, 305\u2013320 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"BF00288472_CR3","series-title":"Lect. Notes Comput. Scie.","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/3-540-10843-2_32","volume-title":"Proc. 8th ICALP","author":"B. Courcelle","year":"1981","unstructured":"Courcelle, B.: An axiomatic approach to the Korenjak-Hopcroft algorithms, in Proc. 8th ICALP, Lect. Notes Comput. Scie. 115, pp. 393\u2013407. Berlin, Heidelberg, New York: Springer 1981"},{"key":"BF00288472_CR4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0012-365X(83)90152-8","volume":"43","author":"K. Culik II","year":"1983","unstructured":"Culik II, K., Karhum\u00e4ki, J.: Systems of equations over a free monoid and Ehrenfeucht's conjecture, Discrete Math. 43, 139\u2013153 (1983)","journal-title":"Discrete Math."},{"key":"BF00288472_CR5","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0022-0000(78)90002-8","volume":"17","author":"K. Culik II","year":"1978","unstructured":"Culik II, K., Salomaa, A.: On the decidability of morphic equivalence for languages. J. Comput. Syst. Sci. 17, 163\u2013175 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00288472_CR6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(79)90015-1","volume":"19","author":"E.P. Friedman","year":"1979","unstructured":"Friedman, E.P., Greibach, S.A.: Superdeterministic DPDA's: the method of accepting does affect decision problems. J. Comput. Syst. Sci. 19, 79\u2013117 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00288472_CR7","volume-title":"Introduction to formal language theor.","author":"M.A. Harrison","year":"1978","unstructured":"Harrison, M.A., Introduction to formal language theor. Reading, Mass.: Addison-Wesley 1978"},{"key":"BF00288472_CR8","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1137\/0201024","volume":"1","author":"M.A. Harrison","year":"1972","unstructured":"Harrison, M.A., Havel, I.M.: Real-time strict deterministic languages, SIAM J. Comput. 1, 333\u2013349 (1972)","journal-title":"SIAM J. Comput."},{"key":"BF00288472_CR9","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0304-3975(79)90024-0","volume":"9","author":"M.A. Harrison","year":"1979","unstructured":"Harrison, M.A., Havel, I.M., Yehudai, A.: On equivalence of grammars through transformation trees. Theor. Comput. Sci. 9, 173\u2013205 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"BF00288472_CR10","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0020-0190(81)90116-2","volume":"13","author":"O. Ibarra","year":"1981","unstructured":"Ibarra, O., Rosier, L.: On the decidability of equivalence for deterministic pushdown transducers. Inf. Process. Lett. 13, 89\u201393 (1981)","journal-title":"Inf. Process. Lett."},{"key":"BF00288472_CR11","unstructured":"Katayama, T., Tsuchiya, N., Enomoto, H.: On the decidability of equivalence for deterministic pushdown transducers, Trans. Inst. Elect. Commun. Eng. Japan 58-D, 760\u2013767 (1975)"},{"key":"BF00288472_CR12","doi-asserted-by":"crossref","unstructured":"Korenjak, A.J., Hopcroft, J.E., Simple deterministic languages, in Proc. IEEE 7th Annual Symposium on Switching and Automata Theory, 36\u201346, Berkeley, CA. 1966","DOI":"10.1109\/SWAT.1966.22"},{"key":"BF00288472_CR13","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0022-0000(79)90055-2","volume":"18","author":"M. Linna","year":"1979","unstructured":"Linna, M., Two decidability results for deterministic pushdown automata, J. Comput. Syst. Sic. 18, 92\u2013107(1979)","journal-title":"J. Comput. Syst. Sic."},{"key":"BF00288472_CR14","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(77)90016-0","volume":"4","author":"T. Olshansky","year":"1977","unstructured":"Olshansky, T., Pnueli, A.: A direct algorithm for checking equivalence of LL(k) grammars, Theor. Comput. Sci. 4, 321\u2013349 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"BF00288472_CR15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/S0019-9958(78)90139-0","volume":"38","author":"M. Oyamaguchi","year":"1978","unstructured":"Oyamaguchi, M., Honda, N.: The decidability of equivalence for deterministic stateless pushdown automata, Inf. Contr. 38, 367\u2013376 (1978)","journal-title":"Inf. Contr."},{"key":"BF00288472_CR16","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/S0019-9958(80)90887-6","volume":"45","author":"M. Oyamaguchi","year":"1980","unstructured":"Oyamaguchi, M., Honda, N., Inagaki, Y.: The equivalence problem for realtime strict deterministic languages, Inf. Control 45, 90\u2013115 (1980)","journal-title":"Inf. Control"},{"key":"BF00288472_CR17","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"D.J. Rosenkrantz","year":"1970","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Properties of deterministic top-down grammars, Inf. Control 17, 226\u2013256 (1970)","journal-title":"Inf. Control"},{"key":"BF00288472_CR18","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/S0022-0000(76)80049-9","volume":"13","author":"K. Taniguchi","year":"1976","unstructured":"Taniguchi, K., Kasami, T.: A result on the equivalence problem for deterministic pushdown automata, J. Comput. Syst. Sci. 13, 38\u201350 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00288472_CR19","doi-asserted-by":"crossref","unstructured":"Tomita, E.: A direct branching algorithm for checking equivalence of strict deterministics vs. LL(k) grammars. Theor. Comput. Sci. 23 (1983)","DOI":"10.1016\/0304-3975(83)90052-X"},{"key":"BF00288472_CR20","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0019-9958(82)80029-6","volume":"52","author":"E. Tomita","year":"1982","unstructured":"Tomita, E.: A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata. Inf. Control 52, 187\u2013238 (1982)","journal-title":"Inf. Control"},{"key":"BF00288472_CR21","volume-title":"Ph.D. Thesis","author":"L.G. Valiant","year":"1973","unstructured":"Valiant, L.G.: Decision procedures for families of deterministic pushdown automata, Ph.D. Thesis, Department of Computer Science, University of Warwick, Coventry, England 1973"},{"key":"BF00288472_CR22","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","volume":"25","author":"L.G. Valiant","year":"1974","unstructured":"Valiant, L.G.: The equivalence problem for deterministic finite-turn pushdown automata, Inf. Control 25, 123\u2013133 (1974)","journal-title":"Inf. Control"},{"key":"BF00288472_CR23","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/S0022-0000(75)80005-5","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: Paterson, M.S., Deterministic one-counter automata. J. Comput. Syst. Sci. 10, 340\u2013350 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00288472_CR24","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/BF01933412","volume":"13","author":"D. Wood","year":"1973","unstructured":"Wood, D.: Some remarks on the KH algorithm for s-grammars. BIT 13, 476\u2013489 (1973)","journal-title":"BIT"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288472.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00288472\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288472.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T19:07:21Z","timestamp":1581966441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00288472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,9]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1986,9]]}},"alternative-id":["BF00288472"],"URL":"https:\/\/doi.org\/10.1007\/bf00288472","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,9]]}}}