{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:52Z","timestamp":1751429452987,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p> It is shown that equations of the form \ufffd(X) = \u03c8(X), in which the unknown X is a set of natural numbers and \ufffd, \u03c8 use the operations of union, intersection and addition of sets S + T = {m + n |, m \u2208 S, n \u2208 T}, can simulate systems of equations \ufffd<jats:sub>j<\/jats:sub>(X<jats:sub>1<\/jats:sub>, \u2026, X<jats:sub>n<\/jats:sub>) = \ufffd<jats:sub>j<\/jats:sub>(X<jats:sub>1<\/jats:sub>, \u2026, X<jats:sub>n<\/jats:sub>) with 1 \u2264 j \u2264 \u2113, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions of equations \ufffd(X) = \u03c8(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet \u03a3 = {a}. <\/jats:p>","DOI":"10.3233\/fi-2010-352","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T04:21:48Z","timestamp":1575346908000},"page":"329-348","source":"Crossref","is-referenced-by-count":0,"title":["Univariate Equations Over Sets of Natural Numbers"],"prefix":"10.1177","volume":"104","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, 50\u2013383 Wroc\u0142aw, Poland. aje@cs.uni.wroc.pl"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Turku, Turku FIN20014, Finland"},{"name":"Academy of Finland, alexander.okhotin@utu.fi"}]}],"member":"179","published-online":{"date-parts":[[2010,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-352","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:51:19Z","timestamp":1751367079000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2010-352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,1]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.3233\/FI-2010-352"],"URL":"https:\/\/doi.org\/10.3233\/fi-2010-352","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2010,1,1]]}}}