Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Equations X + A = B and (X + X) + C = (X − X) + D over Sets of Natural Numbers
verfasst von : Tommi Lehtinen
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It has recently been shown, that hyper-arithmetical sets can be represented as the unique solutions of language equations over sets of natural numbers with operations of addition, subtraction and union. It is shown that the same expressive power, under a certain encoding, can be achieved by systems of just two equations,
X
+
A
=
B
and (
X
+
X
) +
C
= (
X
−
X
) +
D
, without using union. It follows that the problems concerning the solutions of systems of the general form are as hard as the same problems restricted to these systems with two equations, it is known that the question for solution existence is
$\Sigma^1_1$
complete.