Complexity classes and theories of finite models

DOI10.1007/BF01786976MaRDI QIDQ3942945zbMATH OpenOpenAlexFDO

Authors James 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 spectrumlanguage of additionmonadic existential second-order sentencenondeterministic Turing machinetime complexity of a language

Mathematics Subject Classification ID

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

Cites work

• A hierarchy for nondeterministic time complexity
• Almost sure theories
• An application of games to the completeness problem for formalized theories
• Classes of Predictably Computable Functions
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Decision Problems of Finite Automata Design and Related Arithmetics
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• Monadic generalized spectra
• On sets of relations definable by addition
• The complexity of theorem-proving procedures
• The polynomial-time hierarchy
• Turing machines and the spectra of first-order formulas
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(27)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3942945)