The complexity of first-order and monadic second-order logic revisited

Annals of Pure and Applied Logic 130 (1-3):3-31 (2004)
  Copy   BIBTEX


The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size of the input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees



    Upload a copy of this work     Papers currently archived: 84,152

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

Relations in monadic third-order logic.A. P. Hazen - 1997 - Journal of Philosophical Logic 26 (6):619-628.
Descriptive complexity theories.Joerg Flum - 2003 - Theoria 18 (1):47-58.
Querying linguistic treebanks with monadic second-order logic in linear time.Stephan Kepser - 2004 - Journal of Logic, Language and Information 13 (4):457-470.
Graph structure and monadic second-order logic: a language-theoretic approach.B. Courcelle - 2012 - New York: Cambridge University Press. Edited by Joost Engelfriet.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.
First- and second-order logic of mass terms.Peter Roeper - 2004 - Journal of Philosophical Logic 33 (3):261-297.


Added to PP

21 (#574,884)

6 months
1 (#511,323)

Historical graph of downloads
How can I increase my downloads?

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.
Model-theoretic methods in the study of elementary logic.William Hanf - 1965 - Journal of Symbolic Logic 34 (1):132--145.

Add more references