Capturing complexity classes by fragments of second-order logic
type: Item
instance of: scholarly article
title: Capturing complexity classes by fragments of second-order logic
zbMATH Open document ID: 0780.68040
DOI: 10.1016/0304-3975(92)90149-A
author: Erich Grädel
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B15
zbMATH DE Number: 64582
zbMATH Keywords: expressive power
zbMATH Keywords: fragments of second-order logic
zbMATH Keywords: second-order Horn logic
zbMATH Keywords: second-order Krom logic
zbMATH Keywords: existential fragments
zbMATH Keywords: logspace
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Henkin quantifiers and complete problems
cites work: Structure and complexity of relational queries
cites work: Horn clause queries and generalizations
cites work: Q3775538
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: Q4058132
cites work: Fixed-point extensions of first-order logic
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3830533
cites work: Expressibility and Parallel Complexity
cites work: Unification as a complexity measure for logic programming
cites work: Complete problems for deterministic polynomial time
cites work: New problems complete for nondeterministic log space
cites work: The expressive power of stratified logic programs
cites work: The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
cites work: Descriptive characterizations of computational complexity
cites work: Symmetric space-bounded computation
cites work: The polynomial-time hierarchy
cites work: The method of forced enumeration for nondeterministic automata
description: scientific article; zbMATH DE number 64582