{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:16:52Z","timestamp":1774797412708,"version":"3.50.1"},"reference-count":74,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.3103\/s014641162107018x","type":"journal-article","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T09:15:43Z","timestamp":1643706943000},"page":"670-701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines"],"prefix":"10.3103","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3794-9565","authenticated-orcid":false,"given":"V. A.","family":"Zakharov","sequence":"first","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"key":"7396_CR1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0019-9958(67)80006-8","volume":"10","author":"A.L. Rosenberg","year":"1967","unstructured":"Rosenberg, A.L., A machine realization of the linear context-free languages, Inf. Control, 1967, vol. 10, no. 2, pp. 175\u2013188.","journal-title":"Inf. Control"},{"key":"7396_CR2","first-page":"269","volume":"23","author":"M. Mohri","year":"1997","unstructured":"Mohri, M., Finite-state transducers in language and speech processing, Comput. Linguist., 1997, vol. 23, no. 2, pp. 269\u2013311.","journal-title":"Comput. Linguist."},{"key":"7396_CR3","first-page":"012034","volume":"341","author":"A. Roche-Lima","year":"2012","unstructured":"Roche-Lima, A. and Thulasiram, R.K., Bioinformatics algorithm based on a parallel implementation of a machine learning approach using transducers, J. Phys.: Conf. Ser., 2012, vol. 341, no. 1, 012034.","journal-title":"J. Phys.: Conf. Ser."},{"key":"7396_CR4","doi-asserted-by":"crossref","unstructured":"Alur, R. and \u010cerny, P., Streaming transducers for algorithmic verification of single-pass list-processing programs, Proceedings of 38th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 2011, pp. 599\u2013610.","DOI":"10.1145\/1926385.1926454"},{"key":"7396_CR5","doi-asserted-by":"crossref","unstructured":"Thakkar, J., Kanade, R., and Alur, A., Transducer-based algorithmic verification of retransmission protocols over noisy channels, Proceedings of IFIP Joint International Conference on Formal Techniques for Distributed Systems, Springer, 2013, pp. 209\u2013224.","DOI":"10.1007\/978-3-642-38592-6_15"},{"key":"7396_CR6","doi-asserted-by":"crossref","unstructured":"Veanes, M., Hooimeijer, P., Livshits, B., et al., Symbolic finite state transducers: Algorithms and applications, Proceedings of the 39th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 2012, pp.\u00a0137\u2013150.","DOI":"10.1145\/2103656.2103674"},{"key":"7396_CR7","unstructured":"Kozlova, D.G. and Zakharov, V.A., On the model checking of sequential reactive systems, Proceedings of the 25th International Workshop on Concurrency, Specification and Programming, Rostock, 2016, p. 233."},{"key":"7396_CR8","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0304-3975(98)00115-7","volume":"234","author":"M. Mohri","year":"2000","unstructured":"Mohri, M., Minimization algorithms for sequential transducers, Theor. Comput. Sci., 2000, vol. 234, no. 2, pp.\u00a0177\u2013201.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR9","doi-asserted-by":"publisher","first-page":"689","DOI":"10.3103\/S0146411617070288","volume":"51","author":"V.A. Zakharov","year":"2017","unstructured":"Zakharov, V.A. and Jaylauova, S.R., On the minimization problem for sequential programs, Autom. Control Comput. Sci., 2017, vol. 51, no. 7, pp. 689\u2013700.","journal-title":"Autom. Control Comput. Sci."},{"key":"7396_CR10","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.tcs.2006.07.027","volume":"363","author":"H. Tamm","year":"2006","unstructured":"Tamm, H., Nyk\u00e4nen, M., and Ukkonen, E., On size reduction techniques for multitape automata, Theor. Comput. Sci., 2006, vol. 363, no. 2, pp. 234\u2013246.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR11","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D.C. Luckham","year":"1970","unstructured":"Luckham, D.C., Park, D.M., and Paterson, M.S., On formalized computer programs, J. Comput. Syst. Sci., 1970, vol. 4, no. 3, pp. 220\u2013249.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR12","doi-asserted-by":"crossref","unstructured":"Loukanova, R., Linear context free languages, International Colloquium on Theoretical Aspects of Computing, Springer, 2007, pp. 351\u2013365.","DOI":"10.1007\/978-3-540-75292-9_24"},{"key":"7396_CR13","doi-asserted-by":"publisher","first-page":"171","DOI":"10.5540\/tema.2011.012.03.0171","volume":"12","author":"B. Bedregal","year":"2011","unstructured":"Bedregal, B., \u03bb-ALN: Aut\u00f4matos lineares n\u00e3o-determin\u00edsticos com \u03bb-transi\u00e7\u00f5es, Tendencias Mat. Apl. Comput., 2011, vol. 12, no. 3, pp. 171\u2013182.","journal-title":"Tendencias Mat. Apl. Comput."},{"key":"7396_CR14","doi-asserted-by":"crossref","unstructured":"Jiraskova, G. and Klima, O., Deterministic biautomata and subclasses of deterministic linear languages, International Conference on Language and Automata Theory and Applications, Springer, 2019, pp. 315\u2013327.","DOI":"10.1007\/978-3-030-13435-8_23"},{"key":"7396_CR15","doi-asserted-by":"crossref","unstructured":"Holzer, M. and Jakobi, S., Nondeterministic biautomata and their descriptional complexity, International Workshop on Descriptional Complexity of Formal Systems, Springer, 2013, pp. 112\u2013123.","DOI":"10.1007\/978-3-642-39310-5_12"},{"key":"7396_CR16","first-page":"573","volume":"46","author":"O. Klima","year":"2012","unstructured":"Klima, O. and Polak, L., On biautomata*, RAIRO - Theor. \n               Inf. Appl., 2012, vol. 46, no. 4, pp. 573\u2013592.","journal-title":"Inf. Appl."},{"key":"7396_CR17","first-page":"113","volume":"136","author":"M. Holzer","year":"2015","unstructured":"Holzer, M. and Jakobi, S., Minimization and characterizations for biautomata, Fundam. Inf., 2015, vol. 136, nos. 1\u20132, pp. 113\u2013137.","journal-title":"Fundam. Inf."},{"key":"7396_CR18","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0022-0000(68)80006-6","volume":"2","author":"P.C. Fischer","year":"1968","unstructured":"Fischer, P.C. and Rosenberg, A.L., Multitape one-way nonwriting automata, J. Comput. Syst. Sci., 1968, vol. 2, no. 1, pp. 88\u2013101.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR19","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T. Griffiths","year":"1968","unstructured":"Griffiths, T., The unsolvability of the equivalence problem for \u039b-free nondeterministic generalized machines, J. ACM, 1968, vol. 15, no. 3, pp. 409\u2013413.","journal-title":"J. ACM"},{"key":"7396_CR20","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/0207042","volume":"7","author":"O. Ibarra","year":"1978","unstructured":"Ibarra, O., The unsolvability of the equivalence problem for \u03b5-free NGSM\u2019s with unary input (output) alphabet and applications, SIAM J. Comput., 1978, vol. 7, no. 4, pp. 524\u2013532.","journal-title":"SIAM J. Comput."},{"key":"7396_CR21","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/S0022-0000(77)80033-0","volume":"15","author":"M. Blattner","year":"1977","unstructured":"Blattner, M. and Head, T., Single-valued a-transducers, J. Comput. Syst. Sci., 1977, vol. 15, no. 3, pp. 310\u2013327.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR22","doi-asserted-by":"crossref","unstructured":"Schutzenberger, M.P., Sur les relations rationnelles, Proceedings of the Conference on Automata Theory and Formal Languages, 1975, pp. 209\u2013213.","DOI":"10.1007\/3-540-07407-4_22"},{"key":"7396_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0022-0000(79)90012-6","volume":"19","author":"M. Blattner","year":"1979","unstructured":"Blattner, M. and Head, T., The decidability of equivalence for deterministic finite transducers, J. Comput. Syst. Sci., 1979, vol. 19, no. 1, pp. 45\u201349.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"E.M. Gurari","year":"1983","unstructured":"Gurari, E.M. and Ibarra, O., A note on finite-valued and finitely ambiguous transducers, Math. Syst. Theory, 1983, vol. 16, no. 1, pp. 61\u201366.","journal-title":"Math. Syst. Theory"},{"key":"7396_CR25","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1007\/BF00264285","volume":"27","author":"A. Weber","year":"1990","unstructured":"Weber, A., On the valuedness of finite transducers, Acta Inf., 1990, vol. 27, no. 8, pp. 749\u2013780.","journal-title":"Acta Inf."},{"key":"7396_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(86)90134-9","volume":"47","author":"K. Culik","year":"1986","unstructured":"Culik, K. and Karhum\u00e4ki, J., The equivalence of finite valued transducers (on HDT0L languages) is decidable, Theor. Comput. Sci., 1986, vol. 47, pp. 71\u201384.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR27","doi-asserted-by":"crossref","unstructured":"Weber, A., A decomposition theorem for finite-valued transducers and an application to the equivalence problem, Proceedings of the 13th International Symposium on Mathematical Foundations of Computer Science, Springer, 1988, pp. 552\u2013562.","DOI":"10.1007\/BFb0017179"},{"key":"7396_CR28","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0222014","volume":"22","author":"A. Weber","year":"1993","unstructured":"Weber, A., Decomposing finite-valued transducers and deciding their equivalence, SIAM J. Comput., 1993, vol.\u00a022, no. 2, pp. 175\u2013202.","journal-title":"SIAM J. Comput."},{"key":"7396_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"M.-P. B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.-P., Carton, O., Prieur, C., and Sakarovitch, J., Squaring transducers: An efficient procedure for deciding functionality and sequentiality, Theor. Comput. Sci., 2003, vol. 292, no. 1, pp. 45\u201363.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR30","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J. and de Souza, R., On the decomposition of k-valued rational relations, Proceedings of the 25th\u00a0International Symposium on Mathematical Foundations of Computer Science, 2008, pp. 588\u2013600.","DOI":"10.1007\/978-3-540-85238-4_48"},{"key":"7396_CR31","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J. and de Souza, R., On the decidability of bounded valuedness for transducers, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, 2008, pp. 588\u2013600.","DOI":"10.1007\/978-3-540-85238-4_48"},{"key":"7396_CR32","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/s00224-009-9206-6","volume":"47","author":"J. Sakarovitch","year":"2010","unstructured":"Sakarovitch, J. and de Souza, R., Lexicographic decomposition of k-valued transducers, Theory Comput. Syst., 2010, vol. 47, no. 3, pp. 758\u2013785.","journal-title":"Theory Comput. Syst."},{"key":"7396_CR33","doi-asserted-by":"crossref","unstructured":"de Souza, R., On the decidability of the equivalence for k-valued transducers, Proceedings of the 12th International Conference on Developments in Language Theory, Springer, 2008, pp. 252\u2013263.","DOI":"10.1007\/978-3-540-85780-8_20"},{"key":"7396_CR34","doi-asserted-by":"crossref","unstructured":"Zakharov, V.A., Equivalence checking problem for finite state transducers over semigroups, Proceedings of the 6th International Conference on Algebraic Informatics, Springer, 2015, pp. 208\u2013221.","DOI":"10.1007\/978-3-319-23021-4_19"},{"key":"7396_CR35","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/BF01185566","volume":"29","author":"A. Weber","year":"1992","unstructured":"Weber, A., On the lengths of values in a finite transducer, Acta Inf., 1992, vol. 29, nos. 6\u20137, pp. 663\u2013687.","journal-title":"Acta Inf."},{"key":"7396_CR36","doi-asserted-by":"crossref","unstructured":"de Souza, R., On the decidability of the equivalence for a certain class of transducers, Proceedings of the 13th International Conference on Developments in Language Theory, Springer, 2009, pp. 478\u2013489.","DOI":"10.1007\/978-3-642-02737-6_39"},{"key":"7396_CR37","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/S0022-0000(73)80045-5","volume":"7","author":"M. Bird","year":"1973","unstructured":"Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. Syst. Sci., 1973, vol. 7, no. 2, pp. 218\u2013236.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR38","doi-asserted-by":"publisher","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, 1974, vol. 25, no. 2, pp. 123\u2013133.","journal-title":"Inf. Control"},{"key":"7396_CR39","doi-asserted-by":"publisher","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\u2019s decision procedure for equivalence of deterministic finite turn pushdown machines, Theor. Comput. Sci., 1976, vol. 3, no. 3, pp. 305\u2013320.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR40","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0211013","volume":"11","author":"E.P. Friedman","year":"1982","unstructured":"Friedman, E.P. and Greibach, S.A., A polynomial time algorithm for deciding the equivalence problem for 2\u2011tape deterministic finite state acceptors, SIAM J. Comput., 1982, vol. 11, no. 1, pp. 166\u2013183.","journal-title":"SIAM J. Comput."},{"key":"7396_CR41","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-3975(91)90356-7","volume":"78","author":"T. Harju","year":"1991","unstructured":"Harju, T. and Karhum\u00e4ki, J., The equivalence problem of multitape finite automata, Theor. Comput. Sci., 1991, vol. 78, no. 2, pp. 347\u2013355.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR42","doi-asserted-by":"crossref","unstructured":"Worrell, J., Revisiting the equivalence problem for finite multitape automata, Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, Springer, 2013, pp. 422\u2013433.","DOI":"10.1007\/978-3-642-39212-2_38"},{"key":"7396_CR43","unstructured":"Bedregal, B., Nondeterministic linear automata and a class of deterministic linear languages, Preliminary Proceedings LSFA, 2015, pp. 183\u2013196."},{"key":"7396_CR44","first-page":"143","volume":"14","author":"Y. Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., and Shamir, E., On formal properties of simple phrase structure grammars, Sprachtypol. \n               Universalienforsch., 1961, vol. 14, pp. 143\u2013172.","journal-title":"Universalienforsch."},{"key":"7396_CR45","doi-asserted-by":"crossref","unstructured":"Korenjak, A.J. and Hopcro, J.E., Simple deterministic languages, 7th Annual Symposium on Switching and Automata\u00a0Theory (SWAT 1966), IEEE, 1966, pp. 36\u201346.","DOI":"10.1109\/SWAT.1966.22"},{"key":"7396_CR46","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(76)90074-8","volume":"1","author":"E.P. Friedman","year":"1976","unstructured":"Friedman, E.P., The inclusion problem for simple languages, Theor. Comput. Sci., 1976, vol. 1, no. 4, pp. 297\u2013316.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR47","doi-asserted-by":"crossref","unstructured":"Caucal, D., A fast algorithm to decide on simple grammars equivalence, International Symposium on Optimal Algorithms, Springer, 1989, pp. 66\u201385.","DOI":"10.1007\/3-540-51859-2_8"},{"key":"7396_CR48","doi-asserted-by":"crossref","unstructured":"Bastien, C., Czyzowicz, J., Fraczak, W., and Rytter, W., Prime normal form and equivalence of simple grammars, International Conference on Implementation and Application of Automata, Springer, 2005, pp. 78\u201389.","DOI":"10.1007\/11605157_7"},{"key":"7396_CR49","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., and Moller, F., A polynomial algorithm for deciding bisimilarity of normed context-free processes, Theor. Comput. Sci., 1996, vol. 158, nos. 1\u20132, pp. 143\u2013159.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR50","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/S0022-0000(75)80005-5","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G. and Paterson, M.S., Deterministic one-counter automata, J. Comput. Syst. Sci., 1975, vol. 10, no.\u00a03, pp. 340\u2013350.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR51","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, S. and G\u00f6ller, S., Language equivalence of deterministic real-time one-counter automata is NL-complete, International Symposium on Mathematical Foundations of Computer Science, Springer, 2011, pp. 194\u2013205.","DOI":"10.1007\/978-3-642-22993-0_20"},{"key":"7396_CR52","doi-asserted-by":"crossref","unstructured":"S\u00e9nizergues, G., The equivalence problem for t-turn dpda is co-NP, Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, Springer, 2003, pp. 478\u2013489.","DOI":"10.1007\/3-540-45061-0_39"},{"key":"7396_CR53","doi-asserted-by":"publisher","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. Sci., 1979, vol. 18, no. 1, pp. 92\u2013107.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR54","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/BF01075213","volume":"25","author":"V.Y. Meytus","year":"1989","unstructured":"Meytus, V.Y., The equivalence problem for real-time strict deterministic pushdown automata, Cybernetics, 1989, vol. 25, no. 2, pp. 581\u2013594.","journal-title":"Cybernetics"},{"key":"7396_CR55","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1145\/28869.28881","volume":"34","author":"M. Oyamaguchi","year":"1987","unstructured":"Oyamaguchi, M., The equivalence problem for real-time DPDAs, J. ACM, 1987, vol. 34, no. 3, pp. 731\u2013760.","journal-title":"J. ACM"},{"key":"7396_CR56","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/BF01074776","volume":"22","author":"V.Y. Romanovskii","year":"1985","unstructured":"Romanovskii, V.Y., Equivalence problem for real-time deterministic pushdown automata, Cybernetics, 1985, vol. 22, no. 2, pp. 162\u2013175.","journal-title":"Cybernetics"},{"key":"7396_CR57","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"D.J. Rosenkrantz","year":"1970","unstructured":"Rosenkrantz, D.J. and Stearns, R.E., Properties of deterministic top-down grammars, Inf. Control, 1970, vol.\u00a017, no. 3, pp. 226\u2013256.","journal-title":"Inf. Control"},{"key":"7396_CR58","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0304-3975(84)90026-4","volume":"32","author":"E. Tomita","year":"1984","unstructured":"Tomita, E., An extended direct branching algorithm for checking equivalence of deterministic pushdown automata, Theor. Comput. Sci., 1984, vol. 32, nos. 1\u20132, pp. 87\u2013120.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR59","doi-asserted-by":"publisher","first-page":"1166","DOI":"10.1145\/322344.322357","volume":"29","author":"E. Ukkonen","year":"1982","unstructured":"Ukkonen, E., The equivalence problem for some non-real-time deterministic pushdown automata, J. ACM, 1982, vol. 29, no. 4, pp. 1166\u20131181.","journal-title":"J. ACM"},{"key":"7396_CR60","doi-asserted-by":"crossref","unstructured":"S\u00e9nizergues, G., The equivalence problem for deterministic pushdown automata is decidable, Proceedings of the 24th International Colloquium on Automata, Languages, and Programming, Springer, 1997, pp. 671\u2013681.","DOI":"10.1007\/3-540-63165-8_221"},{"key":"7396_CR61","doi-asserted-by":"crossref","unstructured":"Stirling, C., Deciding DPDA equivalence is primitive recursive, Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, Springer, 2002, pp. 821\u2013832.","DOI":"10.1007\/3-540-45465-9_70"},{"key":"7396_CR62","doi-asserted-by":"crossref","unstructured":"Madhavan, R., Mayer, M., Gulwani, S., and Kuncak, V., Automating grammar comparison, Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2015, pp. 183\u2013200.","DOI":"10.1145\/2814270.2814304"},{"key":"7396_CR63","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/s10559-010-9232-z","volume":"46","author":"V.A. Zakharov","year":"2010","unstructured":"Zakharov, V.A., Program equivalence checking by two-tape automata, Cybern. Syst. Anal., 2010, vol. 46, no. 4, pp. 554\u2013562.","journal-title":"Cybern. Syst. Anal."},{"key":"7396_CR64","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(77)90016-0","volume":"4","author":"T. Olshansky","year":"1977","unstructured":"Olshansky, T. and Pnueli, A., A direct algorithm for checking equivalence of LL(k) grammars, Theor. Comput. Sci., 1977, vol. 4, no. 3, pp. 321\u2013349.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR65","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(93)90232-I","volume":"108","author":"J. Karhum\u00e4ki","year":"1993","unstructured":"Karhum\u00e4ki, J., Equations over finite sets of words and equivalence problems in automata theory, Theor. Comput. Sci., 1993, vol. 108, no. 1, pp. 103\u2013118.","journal-title":"Theor. Comput. Sci."},{"key":"7396_CR66","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.jcss.2009.08.002","volume":"76","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A., Decision problems for language equations, J. Comput. Syst. Sci., 2010, vol. 76, nos. 3\u20134, pp. 251\u2013266.","journal-title":"J. Comput. Syst. Sci."},{"key":"7396_CR67","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcro","year":"2006","unstructured":"Hopcro, J.E., Motwani, R., and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006, 3rd ed."},{"key":"7396_CR68","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S., Automata, Languages, and Machines, Academic Press, 1974."},{"key":"7396_CR69","volume-title":"State complexity of prefix-free regular languages","author":"Y. Han","year":"2006","unstructured":"Han, Y., Salomaa, K., and Wood, D., State complexity of prefix-free regular languages, DCFS, 2006, pp. 165\u2013176."},{"key":"7396_CR70","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1145\/357162.357169","volume":"4","author":"A. Martelli","year":"1982","unstructured":"Martelli, A. and Montanari, U., An efficient unification algorithm, ACM Trans. Program. Lang. Syst., 1982, vol.\u00a04, no. 2, pp. 258\u2013282.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"7396_CR71","doi-asserted-by":"crossref","unstructured":"Arden, D., Delayed-logic and finite-state machines, Proceedings of 2-nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961), IEEE, 1961, pp. 133\u2013151.","DOI":"10.1109\/FOCS.1961.13"},{"key":"7396_CR72","volume-title":"A Linear Algorithm for Testing Equivalence of Finite Automata","author":"J.E. Hopcroft","year":"1971","unstructured":"Hopcroft, J.E., A Linear Algorithm for Testing Equivalence of Finite Automata, Def. Tech. Inf. Cent., 1971, vol.\u00a0114."},{"key":"7396_CR73","doi-asserted-by":"publisher","first-page":"523","DOI":"10.3103\/S0146411617070240","volume":"51","author":"V.A. Zakharov","year":"2017","unstructured":"Zakharov, V.A. and Temerbekova, G.G., On the minimization of finite state transducers over semigroups, Autom.\u00a0Control Comput. Sci., 2017, vol. 51, no. 7, pp. 523\u2013530.","journal-title":"Autom.\u00a0Control Comput. Sci."},{"key":"7396_CR74","doi-asserted-by":"crossref","unstructured":"Itkin, V.E., Logic-term equivalence of program schemes, Kibern. Sist. Anal., 1972, no. 1, pp. 5\u201327.","DOI":"10.1007\/BF01069127"}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S014641162107018X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S014641162107018X","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S014641162107018X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:01:05Z","timestamp":1773612065000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S014641162107018X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":74,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["7396"],"URL":"https:\/\/doi.org\/10.3103\/s014641162107018x","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"25 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The author declares that he has no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}