Complexity classes and theories of finite models

DOI10.1007/BF01786976zbMath0484.03020OpenAlexW2004663163MaRDI QIDQ3942945

James F. Lynch

Publication date: 1982

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01786976

zbMATH Keywords

finite spectrumnondeterministic Turing machinelanguage of additionmonadic existential second-order sentencetime complexity of a language

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Turing machines and related notions (03D10)

Related Items (26)

Universal quantifiers and time complexity of random access machines ⋮ Arithmetical definability and computational complexity ⋮ First-order spectra with one binary predicate ⋮ An algebra and a logic for \(NC^ 1\) ⋮ The polynomial and linear time hierarchies in V⁰ ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On winning Ehrenfeucht games and monadic NP ⋮ Arity and alternation in second-order logic ⋮ Circumscribing DATALOG: expressive power and complexity ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ A descriptive complexity approach to the linear hierarchy. ⋮ Model-checking hierarchical structures ⋮ First-order spectra with one variable ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Arithmetizing uniform \(NC\) ⋮ Formulas, regular languages and Boolean circuits ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ First-order expressibility of languages with neutral letters or: The Crane Beach conjecture ⋮ On Horn spectra ⋮ Linear time and the power of one first-order universal quantifier ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Unnamed Item ⋮ Investigation of binary spectra by explicit polynomial transformations of graphs ⋮ Lower bound results on lengths of second-order formulas ⋮ Complete problems in the first-order predicate calculus ⋮ On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• The polynomial-time hierarchy
• A hierarchy for nondeterministic time complexity
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• An application of games to the completeness problem for formalized theories
• Weak Second‐Order Arithmetic and Finite Automata
• Classes of Predictably Computable Functions
• Decision Problems of Finite Automata Design and Related Arithmetics
• Almost sure theories
• Monadic generalized spectra
• On sets of relations definable by addition
• Turing machines and the spectra of first-order formulas
• The complexity of theorem-proving procedures

This page was built for publication: Complexity classes and theories of finite models