{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,8]],"date-time":"2022-05-08T17:25:00Z","timestamp":1652030700770},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,5]]},"abstract":"Classically, several properties and relations of words, such as \u201cbeing a power of the same word\u201d can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, \u201cthe primitiveness\u201d and \u201cthe equal length\u201d are such properties, as well as being \u201cany word over a proper subalphabet\u201d.<\/jats:p>","DOI":"10.1145\/337244.337255","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"483-505","source":"Crossref","is-referenced-by-count":28,"title":["The expressibility of languages and relations by word equations"],"prefix":"10.1145","volume":"47","author":[{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"first","affiliation":[{"name":"Turku Univ., Turku, Finland"}]},{"given":"Filippo","family":"Mignosi","sequence":"additional","affiliation":[{"name":"Univ. di Palermo, Palermo, Italy"}]},{"given":"Wojciech","family":"Plandowski","sequence":"additional","affiliation":[{"name":"Turku Univ., Turku, Finland"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"130","volume-title":"Proceedings of llth Annual Symposium on the Theory of Computing (STOC'79)","author":"ANGEVIN D.","year":"1979"},{"key":"e_1_2_1_2_1","unstructured":"BERSTEL J. AND PERRIN D. 1985. Theory of Codes. Academic Press Orlando Fla. BERSTEL J. AND PERRIN D. 1985. Theory of Codes. Academic Press Orlando Fla."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02017493","article-title":"\/87. Coding in the existential theory of concatenation","volume":"26","author":"BUJCHI R.","year":"1986","journal-title":"Arch. Math. Logik"},{"key":"e_1_2_1_4_1","unstructured":"BULITKO V.K. 1970. Equations and inequalities in a free group and a free semi-group. Tul. Gos. Ped. Inst. Ucen. Zap. Mat. Kafedr. Geometr. i Algebra 2 242-252 (in Russian). BULITKO V.K. 1970. Equations and inequalities in a free group and a free semi-group. Tul. Gos. Ped. Inst. Ucen. Zap. Mat. Kafedr. Geometr. i Algebra 2 242-252 (in Russian)."},{"key":"e_1_2_1_5_1","first-page":"329","volume-title":"Springer-Verlag","author":"CHOFFRUT C.","year":"1997"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0012-365X(83)90152-8","article-title":"Systems of equations and Ehrenfeucht's conjecture","volume":"43","author":"CULIK K.","year":"1983","journal-title":"Discr. Math."},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","first-page":"336","volume-title":"Proceedings of MFCS'94","author":"EYONO OBONO S."},{"key":"e_1_2_1_8_1","unstructured":"HARRISON M. A. 1978. Introduction to Formal Language Theory. Addison-Wesley Publishing Company Reading Mass. HARRISON M. A. 1978. Introduction to Formal Language Theory. Addison-Wesley Publishing Company Reading Mass."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1006"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","first-page":"98","volume-title":"ICALP'97","author":"KARHUMAKI J."},{"key":"e_1_2_1_11_1","unstructured":"KHMELEVSKI YU. I. 1971\/1976. Equations in free semigroups Trudy Mat. Inst. Steklov 107. (English translation: Proc. Steklov Inst. of Mathematics 107 (1971) American Mathematical Society Providence R.I. 1976.) KHMELEVSKI YU. I. 1971\/1976. Equations in free semigroups Trudy Mat. Inst. Steklov 107. (English translation: Proc. Steklov Inst. of Mathematics 107 (1971) American Mathematical Society Providence R.I. 1976.)"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234543"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"LENTIN A. 1972. Equations dans des Monoides Libres. Gouthiers-Villars Paris France. LENTIN A. 1972. Equations dans des Monoides Libres. Gouthiers-Villars Paris France.","DOI":"10.1515\/9783111544526"},{"key":"e_1_2_1_14_1","unstructured":"LOTHAIRE M. 1983. Combinatorics on Words. Addison-Wesley Reading Mass. LOTHAIRE M. 1983. Combinatorics on Words. Addison-Wesley Reading Mass."},{"issue":"145","key":"e_1_2_1_15_1","first-page":"147","article-title":"The problem of solvability of equations in a free semigroup","volume":"103","author":"MAKANIN G.S.","year":"1977","journal-title":"Mat. Sb."},{"key":"e_1_2_1_16_1","first-page":"354","article-title":"\/1971. Enumerable sets are diophantine","volume":"11","author":"MATIJASEVICH Y.","year":"1970","journal-title":"Soviet. Math. Doklady"},{"key":"e_1_2_1_17_1","unstructured":"ROZENBERG G. AND SALOMAA A. 1980. The Mathematical Theory of L Systems Academic Press Orlando Fla. ROZENBERG G. AND SALOMAA A. 1980. The Mathematical Theory of L Systems Academic Press Orlando Fla."},{"key":"e_1_2_1_18_1","first-page":"329","volume-title":"Lecture Notes in Computer Science","author":"SEIBERT S."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/337244.337255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,3]],"date-time":"2021-03-03T17:05:25Z","timestamp":1614791125000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/337244.337255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2000,5]]}},"alternative-id":["10.1145\/337244.337255"],"URL":"http:\/\/dx.doi.org\/10.1145\/337244.337255","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,5]]}}}