{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:10:53Z","timestamp":1725491453163},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540732075"},{"type":"electronic","value":"9783540732082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73208-2_3","type":"book-chapter","created":{"date-parts":[[2007,9,12]],"date-time":"2007-09-12T03:58:11Z","timestamp":1189569491000},"page":"23-27","source":"Crossref","is-referenced-by-count":18,"title":["What Do We Know About Language Equations?"],"prefix":"10.1007","author":[{"given":"Michal","family":"Kunc","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0049320","volume-title":"Computer Science Logic","author":"A. Aiken","year":"1994","unstructured":"Aiken, A., Kozen, D., Vardi, M., Wimmers, E.: The complexity of set constraints. In: Meinke, K., B\u00f6rger, E., Gurevich, Y. (eds.) CSL 1993. LNCS, vol.\u00a0832, pp. 1\u201317. Springer, Heidelberg (1994)"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(85)90066-0","volume":"41","author":"M.H. Albert","year":"1985","unstructured":"Albert, M.H., Lawrence, J.: A proof of Ehrenfeucht\u2019s conjecture. Theoret. Comput. Sci.\u00a041(1), 121\u2013123 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-45653-8_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"F. Baader","year":"2001","unstructured":"Baader, F., K\u00fcsters, R.: Unification in a description logic with transitive closure of roles. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol.\u00a02250, pp. 217\u2013232. Springer, Heidelberg (2001)"},{"issue":"3","key":"3_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1006\/jsco.2000.0426","volume":"31","author":"F. Baader","year":"2001","unstructured":"Baader, F., Narendran, P.: Unification of concept terms in description logics. J.\u00a0Symbolic Comput.\u00a031(3), 277\u2013305 (2001)","journal-title":"J.\u00a0Symbolic Comput."},{"doi-asserted-by":"crossref","unstructured":"Baader, F., Okhotin, A.: Complexity of language equations with one-sided concatenation and all Boolean operations. In: Proc. UNIF 2006, pp. 59\u201373 (2006)","key":"3_CR5","DOI":"10.25368\/2022.154"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00224-005-1262-y","volume":"39","author":"S. Bala","year":"2006","unstructured":"Bala, S.: Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms. Theory Comput. Syst.\u00a039(1), 137\u2013163 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"3_CR7","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1051\/ita:2001130","volume":"35","author":"J. Cassaigne","year":"2001","unstructured":"Cassaigne, J., Karhum\u00e4ki, J., Ma\u0148uch, J.: On conjugacy of languages. Theor. Inform. Appl.\u00a035(6), 535\u2013550 (2001)","journal-title":"Theor. Inform. Appl."},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BFb0052372","volume-title":"Rewriting Techniques and Applications","author":"W. Charatonik","year":"1998","unstructured":"Charatonik, W., Podelski, A.: Co-definite set constraints. In: Nipkow, T. (ed.) Rewriting Techniques and Applications. LNCS, vol.\u00a01379, pp. 211\u2013225. Springer, Heidelberg (1998)"},{"key":"3_CR9","volume-title":"Regular Algebra and Finite Machines","author":"J.H. Conway","year":"1971","unstructured":"Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)"},{"issue":"2\u20133","key":"3_CR10","doi-asserted-by":"publisher","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\u2019s conjecture. Discrete Math.\u00a043(2\u20133), 139\u2013153 (1983)","journal-title":"Discrete Math."},{"key":"3_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59849-4","volume-title":"Finiteness and Regularity in Semigroups and Formal Languages","author":"A. Luca de","year":"1999","unstructured":"de Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Springer, Heidelberg (1999)"},{"issue":"2\u20133","key":"3_CR12","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.tcs.2005.07.013","volume":"345","author":"M. Domaratzki","year":"2005","unstructured":"Domaratzki, M., Salomaa, K.: Decidability of trajectory-based equations. Theoret. Comput. Sci.\u00a0345(2\u20133), 304\u2013330 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(82)90124-4","volume":"27","author":"A. Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theoret. Comput. Sci.\u00a027(3), 311\u2013332 (1983)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"3_CR14","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S. Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL . J. ACM\u00a09(3), 350\u2013371 (1962)","journal-title":"J. ACM"},{"issue":"3","key":"3_CR15","first-page":"321","volume":"40","author":"V.S. Guba","year":"1986","unstructured":"Guba, V.S.: Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. Mat. Zametki\u00a040(3), 321\u2013324 (1986)","journal-title":"Mat. Zametki"},{"unstructured":"Jeandel, E., Ollinger, N.: Playing with Conway\u2019s problem. Technical report ccsd-00013788, Laboratoire d\u2019Informatique Fondamentale de Marseille (2005), available at http:\/\/hal.archives-ouvertes.fr\/hal-00013788","key":"3_CR16"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","first-page":"23","volume-title":"DLT 2007","author":"A. Je\u017c","year":"2007","unstructured":"Je\u017c, A.: Conjunctive grammars can generate non-regular unary languages. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 23\u201327. Springer, Heidelberg (2007)"},{"issue":"2","key":"3_CR18","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.tcs.2005.03.037","volume":"340","author":"J. Karhum\u00e4ki","year":"2005","unstructured":"Karhum\u00e4ki, J., Latteux, M., Petre, I.: Commutation with codes. Theoret. Comput. Sci.\u00a0340(2), 322\u2013333 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR19","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00224-004-1191-1","volume":"38","author":"J. Karhum\u00e4ki","year":"2005","unstructured":"Karhum\u00e4ki, J., Latteux, M., Petre, I.: Commutation with ternary sets of words. Theory Comput. Syst.\u00a038(2), 161\u2013169 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"3_CR20","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1142\/S0129054103001960","volume":"14","author":"J. Karhum\u00e4ki","year":"2003","unstructured":"Karhum\u00e4ki, J., Lisovik, L.P.: The equivalence problem of finite substitutions on ab * c, with applications. Internat. J. Found. Comput. Sci.\u00a014(4), 699\u2013710 (2003)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1142\/9789812562494_0060","volume-title":"Current Trends in Theoretical Computer Science, The Challenge of the New Century","author":"J. Karhum\u00e4ki","year":"2004","unstructured":"Karhum\u00e4ki, J., Petre, I.: Two problems on commutation of languages. In: Current Trends in Theoretical Computer Science, The Challenge of the New Century, vol.\u00a02, pp. 477\u2013494. World Scientific, Singapore (2004)"},{"issue":"1\u20132","key":"3_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(94)90230-5","volume":"132","author":"L. Kari","year":"1994","unstructured":"Kari, L.: On language equations with invertible operations. Theoret. Comput. Sci.\u00a0132(1\u20132), 129\u2013150 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR23","first-page":"173","volume":"83","author":"L. Kari","year":"2004","unstructured":"Kari, L., Sos\u00edk, P.: On language equations with deletion. Bull. EATCS\u00a083, 173\u2013180 (2004)","journal-title":"Bull. EATCS"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"210","DOI":"10.2307\/1993287","volume":"95","author":"J.B. Kruskal","year":"1960","unstructured":"Kruskal, J.B.: Well-quasi-ordering, the tree theorem, and Vazsonyi\u2019s conjecture. Trans. Amer. Math. Soc.\u00a095(2), 210\u2013225 (1960)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2\u20133","key":"3_CR25","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.tcs.2005.09.018","volume":"348","author":"M. Kunc","year":"2005","unstructured":"Kunc, M.: Regular solutions of language inequalities and well quasi-orders. Theoret. Comput. Sci.\u00a0348(2\u20133), 277\u2013293 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR26","first-page":"81","volume":"85","author":"M. Kunc","year":"2005","unstructured":"Kunc, M.: Simple language equations. Bull. EATCS\u00a085, 81\u2013102 (2005)","journal-title":"Bull. EATCS"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/11505877_29","volume-title":"Developments in Language Theory","author":"M. Kunc","year":"2005","unstructured":"Kunc, M.: On language inequalities XK\u2009\u2286\u2009LX. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol.\u00a03572, pp. 327\u2013337. Springer, Heidelberg (2005)"},{"unstructured":"Kunc, M.: Largest solutions of left-linear language inequalities. In: Proc. AFL 2005, University of Szeged, pp. 178\u2013186 (2005), Also available at http:\/\/www.math.muni.cz\/~kunc\/math\/left_linear.ps","key":"3_CR28"},{"issue":"4","key":"3_CR29","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-006-1321-z","volume":"40","author":"M. Kunc","year":"2007","unstructured":"Kunc, M.: The power of commuting with finite sets of words. Theory Comput. Syst.\u00a040(4), 521\u2013551 (2007)","journal-title":"Theory Comput. Syst."},{"unstructured":"Kunc, M.: The simplest language where equivalence of finite substitutions is undecidable. Preprint available at http:\/\/www.math.muni.cz\/~kunc\/math\/finite_substitutions.pdf .","key":"3_CR30"},{"key":"3_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-2156-2","volume-title":"Language Equations","author":"E.L. Leiss","year":"1999","unstructured":"Leiss, E.L.: Language Equations. Springer, Heidelberg (1999)"},{"issue":"3","key":"3_CR32","first-page":"299","volume":"357","author":"L.P. Lisovik","year":"1997","unstructured":"Lisovik, L.P.: The equivalence problem for finite substitutions on regular languages. Dokl. Akad. Nauk\u00a0357(3), 299\u2013301 (1997)","journal-title":"Dokl. Akad. Nauk"},{"unstructured":"Ly, O.: A constructive solution of the language inequation X A\u2009\u2286\u2009B X, Preprint available at http:\/\/www.labri.fr\/perso\/ly\/publications\/LanguageEquation.pdf .","key":"3_CR33"},{"issue":"2","key":"3_CR34","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Mat. Sb.\u00a0103(2), 147\u2013236 (1977)","journal-title":"Mat. Sb."},{"issue":"2","key":"3_CR35","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1051\/ita:2006014","volume":"40","author":"P. Massazza","year":"2006","unstructured":"Massazza, P., Salmela, P.: On the simplest centralizer of a language. Theor. Inform. Appl.\u00a040(2), 295\u2013301 (2006)","journal-title":"Theor. Inform. Appl."},{"issue":"4","key":"3_CR36","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. J. Autom. Lang. Comb.\u00a06(4), 519\u2013535 (2001)","journal-title":"J. Autom. Lang. Comb."},{"issue":"5","key":"3_CR37","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1023\/A:1020213411126","volume":"28","author":"A. Okhotin","year":"2002","unstructured":"Okhotin, A.: Conjunctive grammars and systems of language equations. Program. Comput. Software\u00a028(5), 243\u2013249 (2002)","journal-title":"Program. Comput. Software"},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ic.2004.03.006","volume":"194","author":"A. Okhotin","year":"2004","unstructured":"Okhotin, A.: Boolean grammars. Inform. and Comput.\u00a0194(1), 19\u201348 (2004)","journal-title":"Inform. and Comput."},{"issue":"1","key":"3_CR39","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1051\/ita:2004004","volume":"38","author":"A. Okhotin","year":"2004","unstructured":"Okhotin, A.: On the equivalence of linear conjunctive grammars and trellis automata. Theor. Inform. Appl.\u00a038(1), 69\u201388 (2004)","journal-title":"Theor. Inform. Appl."},{"issue":"5","key":"3_CR40","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1142\/S012905410500342X","volume":"16","author":"A. Okhotin","year":"2005","unstructured":"Okhotin, A.: A characterization of the arithmetical hierarchy by language equations. Internat. J. Found. Comput. Sci.\u00a016(5), 985\u2013998 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"issue":"3","key":"3_CR41","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.tcs.2005.07.038","volume":"349","author":"A. Okhotin","year":"2005","unstructured":"Okhotin, A.: Unresolved systems of language equations: Expressive power and decision problems. Theoret. Comput. Sci.\u00a0349(3), 283\u2013308 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1007\/11549345_61","volume-title":"Mathematical Foundations of Computer Science 2005","author":"A. Okhotin","year":"2005","unstructured":"Okhotin, A.: Strict language inequalities and their decision problems. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 708\u2013719. Springer, Heidelberg (2005)"},{"issue":"4","key":"3_CR43","first-page":"563","volume":"74","author":"A. Okhotin","year":"2006","unstructured":"Okhotin, A.: Computational universality in one-variable language equations. Fund. Inform.\u00a074(4), 563\u2013578 (2006)","journal-title":"Fund. Inform."},{"key":"3_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/11753728_30","volume-title":"Computer Science \u2013 Theory and Applications","author":"A. Okhotin","year":"2006","unstructured":"Okhotin, A.: Language equations with symmetric difference. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 292\u2013303. Springer, Heidelberg (2006)"},{"unstructured":"Okhotin, A.: Nine open problems for conjunctive and Boolean grammars. Bull. EATCS 91 (to appear, 2007)","key":"3_CR45"},{"key":"3_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-45061-0_21","volume-title":"Automata, Languages and Programming","author":"A. Okhotin","year":"2003","unstructured":"Okhotin, A.: Decision problems for language equations. Submitted for publication. Preliminary version. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 239\u2013251. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","unstructured":"Okhotin, A., Yakimova, O.: Language equations with complementation: Decision problems. Theoret. Comput. Sci. (to appear)","key":"3_CR47","DOI":"10.1016\/j.tcs.2007.01.016"},{"issue":"4","key":"3_CR48","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0214066","volume":"14","author":"R. Parikh","year":"1985","unstructured":"Parikh, R., Chandra, A., Halpern, J., Meyer, A.: Equations between regular terms and an application to process logic. SIAM J. Comput.\u00a014(4), 935\u2013942 (1985)","journal-title":"SIAM J. Comput."},{"key":"3_CR49","first-page":"467","volume-title":"Proc. STOC\u201906","author":"W. Plandowski","year":"2006","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Proc. STOC\u201906, pp. 467\u2013476. ACM, New York (2006)"},{"key":"3_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc.\u00a0141, 1\u201335 (1969)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"4","key":"3_CR51","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1051\/ita\/1989230404251","volume":"23","author":"B. Ratoandromanana","year":"1989","unstructured":"Ratoandromanana, B.: Codes et motifs. RAIRO Inform. Th\u00e9or. Appl.\u00a023(4), 425\u2013444 (1989)","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"volume-title":"Handbook of Formal Languages","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer, Heidelberg (1997)","key":"3_CR52"},{"issue":"5","key":"3_CR53","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(78)90001-7","volume":"7","author":"K. Ruohonen","year":"1978","unstructured":"Ruohonen, K.: A note on language equations involving morphisms. Inform. Process. Lett.\u00a07(5), 209\u2013212 (1978)","journal-title":"Inform. Process. Lett."},{"key":"3_CR54","volume-title":"Elements of Automata Theory","author":"J. Sakarovitch","year":"2007","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2007)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73208-2_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T23:51:48Z","timestamp":1684021908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73208-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540732075","9783540732082"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73208-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}