{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:54Z","timestamp":1725488574105},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_20","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"193-203","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Decidable Cases of Commutation Problem for Languages"],"prefix":"10.1007","author":[{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Plandowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"20_CR1","unstructured":"C. Choffrut, J. Karhumaki, N. Ollinger, The commutation of finite sets: a challenging problem, TUCS Technical Report 303, http:\/\/www.tucs.fi\/ , 1999."},{"key":"20_CR2","unstructured":"J. H. Conway, Regular algebra and finite machines, Chapman Hall, 1971."},{"key":"20_CR3","unstructured":"M. Crochemore, W. Rytter, Text algorithms, Oxford University Press, 1994"},{"key":"20_CR4","unstructured":"V. Diekert, Makanin\u2019s algorithm, in Lothaire II, to appear."},{"key":"20_CR5","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/S0022-0000(76)80034-7","volume":"12","author":"A. Ehrenfeucht","year":"1976","unstructured":"A. Ehrenfeucht, P. Zeiger, Complexity measures for expressions, J. Comput. System Sci. 12, 134\u2013146, 1976.","journal-title":"J. Comput. System Sci."},{"key":"20_CR6","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, San Francisco: H.Freeman, 1978."},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"T. Harju, O. Ibarra, J. Karhum\u00e4ki, A. Salomaa, Decision questions concerning semilinearity, morphisms and commutation of languages, TUCS Technical Report 376, http:\/\/www.tucs.fi\/ , 2000.","DOI":"10.1007\/3-540-48224-5_48"},{"key":"20_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BFb0055777","volume-title":"Computing \u03b5-free NFA from regular expressions in O(nlog2n) time","author":"C. Hagenach","year":"1998","unstructured":"C. Hagenach, A. Muscholl, Computing \u03b5-free NFA from regular expressions in O(nlog2 n) time, LNCS 1450, 277\u2013285, 1998."},{"key":"20_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BFb0023448","volume-title":"Translating regular expressions into small \u03b5-free nondeterministic finite automata","author":"J. Hromkovic","year":"1997","unstructured":"J. Hromkovic, S. Seibert, T. Wilke, Translating regular expressions into small \u03b5-free nondeterministic finite automata, LNCS 1200, 55\u201366, 1997."},{"key":"20_CR10","unstructured":"J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979."},{"key":"20_CR11","series-title":"Lect Notes Comput Sci","volume-title":"Proc. MCU 2001","author":"J. Karhum\u00e4ki","year":"2001","unstructured":"J. Karhum\u00e4ki, Combinatorial and computational problems on finite sets of words, Proc. MCU 2001, LNCS, to appear."},{"key":"20_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/3-540-45022-X_45","volume-title":"Proc. ICALP 2000","author":"J. Karhum\u00e4ki","year":"2000","unstructured":"J. Karhum\u00e4ki, I. Petre, On the centralizer of a finite set, Proc. ICALP 2000, LNCS 1853, 536\u2013514, 2000."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"E. Leiss, Language equations, Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-2156-2"},{"key":"20_CR14","unstructured":"M. Lothaire, Combinatorics on words, Addison-Wesley, 1983."},{"issue":"2","key":"20_CR15","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"G.S. Makanin, The problem of solvability of equations in a free semigroup, Mat. Sb. 103(2), 147\u2013236, in russian; english translation in: Math. USSR Sbornik, 32, 129\u2013198, 1977.","journal-title":"Mat. Sb."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"W. Plandowski, Satisfiability of word equations with constants is in PSPACE, Proc. FOCS 1999, 1999.","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1051\/ita\/1989230404251","volume":"23","author":"B. Ratoandramanana","year":"1989","unstructured":"B. Ratoandramanana, Codes et motifs, RAIRO Theor. Informat. 23, 425\u2013444, 1989.","journal-title":"RAIRO Theor. Informat."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"S. Yu, Regular languages, in G. Rozengerg, A. Salomaa (eds.), Handbook of Formal Languages, Springer, 41\u2013110, 1997.","DOI":"10.1007\/978-3-642-59136-5_2"}],"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-44669-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:12:55Z","timestamp":1556748775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}