Rudimentary Languages and Second‐Order Logic

Mathematical Logic Quarterly 43 (3):419-426 (1997)
  Copy   BIBTEX

Abstract

The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,169

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Descriptive complexity theories.Joerg Flum - 2003 - Theoria 18 (1):47-58.
Dependence Logic with a Majority Quantifier.Arnaud Durand, Johannes Ebbing, Juha Kontinen & Heribert Vollmer - 2015 - Journal of Logic, Language and Information 24 (3):289-305.
Computational model theory: an overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
Topological complexity of locally finite ω-languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.
From finitary to infinitary second‐order logic.George Weaver & Irena Penev - 2005 - Mathematical Logic Quarterly 51 (5):499-506.
Graph structure and monadic second-order logic: a language-theoretic approach.B. Courcelle - 2012 - New York: Cambridge University Press. Edited by Joost Engelfriet.

Analytics

Added to PP
2013-10-31

Downloads
36 (#700,595)

6 months
7 (#614,157)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On subrecursive complexity of integration.Ivan Georgiev - 2020 - Annals of Pure and Applied Logic 171 (4):102777.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
Theory of Formal Systems.Raymond M. Smullyan - 1965 - Journal of Symbolic Logic 30 (1):88-90.
Concatenation as a basis for arithmetic.W. V. Quine - 1946 - Journal of Symbolic Logic 11 (4):105-114.
A spectrum hierarchy.Ronald Fagin - 1975 - Mathematical Logic Quarterly 21 (1):123-134.

Add more references