TY - JOUR

T1 - A characterization of the arithmetical hierarchy by language equations

AU - Okhotin, Alexander

PY - 2005/10/1

Y1 - 2005/10/1

N2 - Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic, In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.

AB - Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic, In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.

KW - Arithmetical hierarchy

KW - Decision problem

KW - Descriptional complexity

KW - Descriptive complexity

KW - Language equations

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

U2 - 10.1142/S012905410500342X

DO - 10.1142/S012905410500342X

M3 - Article

AN - SCOPUS:33746228538

VL - 16

SP - 985

EP - 998

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 5

ER -