Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2010

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: unary alphabet

Sortuj według:

Ogranicz wyniki do:

Univariate Equations Over Sets of Natural Numbers

Jeż A., Okhotin A.

Fundamenta Informaticae

2010

Vol. 104, nr 4

329-348

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 φ(X1, . . . ,Xn) = φ(X1, . . . ,Xn) with 1 ≤ j ≤ l, 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 Σ = {α}.