TY - JOUR

T1 - Univariate equations over sets of natural numbers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2010/12/1

Y1 - 2010/12/1

N2 - It is shown that equations of the form φ(X) = ψ(X), in which the unknown X is a set of natural numbers and φ, ψ use the operations of union, intersection and addition of sets S + T = {m + n , m ∈ S, n ∈ T}, can simulate systems of equations φj(X1, ... , Xn) = φj(X1, ... , Xn) with 1 ≤ j ≤ ℓ, 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 φ(X) = ψ(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 Σ = {a}.

AB - It is shown that equations of the form φ(X) = ψ(X), in which the unknown X is a set of natural numbers and φ, ψ use the operations of union, intersection and addition of sets S + T = {m + n , m ∈ S, n ∈ T}, can simulate systems of equations φj(X1, ... , Xn) = φj(X1, ... , Xn) with 1 ≤ j ≤ ℓ, 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 φ(X) = ψ(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 Σ = {a}.

KW - Language equations

KW - unary alphabet

KW - univariate equations

UR - http://www.scopus.com/inward/record.url?scp=78650653996&partnerID=8YFLogxK

U2 - 10.3233/FI-2010-352

DO - 10.3233/FI-2010-352

M3 - Article

AN - SCOPUS:78650653996

VL - 104

SP - 329

EP - 348

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -