Special Issue: Descriptional Complexity of Formal Systems (DCFS '04)No Access

A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS

ALEXANDER OKHOTIN

School of Computing, Queen's University, Kingston, Ontario, Canada

https://doi.org/10.1142/S012905410500342XCited by:1 (Source: Crossref)

Abstract

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.

Keywords:

References

J. Autebert, J. Berstel and L. Boasson, Handbook of Formal Languages 1, eds. Rozenberg and Salomaa (Springer-Verlag, Berlin, 1997) pp. 111–174. Crossref, Google Scholar
B. S. Baker and R. V. Book, Journal of Computer and System Sciences 8, 315 (1974). Crossref, Web of Science, Google Scholar
N. Chomsky and M. P. Schützenberger, Computer Programming and Formal Systems, eds. Braffort and Hirschberg (North-Holland, Amsterdam, 1963) pp. 118–161. Crossref, Google Scholar
J. H. Conway , Regular Algebra and Finite Machines ( Chapman and Hall , London , 1971 ) . Google Scholar
K. Culik II, J. Gruska, A. Salomaa, "Systolic trellis automata", I and II, International Journal of Computer Mathematics, 15 (1984), 195–212, and 16 (1984), 3–22 . Google Scholar
S. Ginsburg and H. G. Rice, Journal of the ACM 9, 350 (1962). Crossref, Web of Science, Google Scholar
J. Gruska, Kybernetika 3, 22 (1967). Google Scholar
J. Gruska, Information and Control 14, 152 (1969). Crossref, Google Scholar
J. Hartmanis, Proceedings of Symposia in Applied Mathematics 19 (AMS, 1967) pp. 42–51. Google Scholar
O. H. Ibarra and S. M. Kim, Theoretical Computer Science 29, 123 (1984). Crossref, Web of Science, Google Scholar
N. Immerman, DSPACE[nk]=VAR[k + 1], Sixth IEEE Symposium on Structure in Complexity Theory (1991) pp. 334–340. Google Scholar
N. Immerman , Descriptive complexity ( Springer-Verlag , New York , 1998 ) . Google Scholar
N. Immerman, J. F. Buss and D. A. M. Barrington, Journal of Symbolic Logic 66, 1217 (2001). Crossref, Web of Science, Google Scholar
E. L. Leiss , Language equations ( Springer-Verlag , New York , 1999 ) . Crossref, Google Scholar
A. Okhotin, Journal of Automata, Languages and Combinatorics 6(4), 519 (2001). Google Scholar
A. Okhotin, Programming and Computer Software 28, 243 (2002). Crossref, Web of Science, Google Scholar
A. Okhotin, Decision problems for language equations with Boolean operations, LNCS 2719 pp. 239–251. Google Scholar
A. Okhotin, RAIRO Informatique Théorique et Applications 38, 69 (2004). Crossref, Web of Science, Google Scholar
A. Okhotin, Information and Computation 194, 19 (2004). Crossref, Web of Science, Google Scholar
A. Okhotin, Theoretical Computer Science 320(2–3), 419 (2004). Crossref, Web of Science, Google Scholar
A. Okhotin, On computational universality in language equations, Proceedings of MCU 2004, LNCS 3354 pp. 292–303. Google Scholar
H. Rogers Jr. , Theory of Recursive Functions and Effective Computability ( McGraw-Hill , 1967 ) . Google Scholar
W. C. Rounds, Computational Linguistics 14(4), 1 (1988). Google Scholar
A. Salomaa , Theory of Automata ( Pergamon Press , Oxford , 1969 ) . Google Scholar
S. Yu, Handbook of Formal Languages 1, eds. Rozenberg and Salomaa (Springer-Verlag, Berlin, 1997) pp. 41–110. Crossref, Google Scholar