Capturing Complexity Classes by Fragments of Second-Order Logic

No abstract is available for this paper.

• Publication year

  1991

• Venue

  Theoretical Computer Science

• Publication date

  1991-06-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(92)90149-A
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An optimal lower bound on the number of variables for graph identification

  1992cited by this paper
• Generic Computation and its complexity

  1991cited by this paper
• The Expressive Power of Stratified Programs

  1991cited by this paper
• The Expressive Power of Second Order Horn Logic

  1991cited by this paper
• Describing Graphs: A First-Order Approach to Graph Canonization

  1990cited by this paper
• Descriptive Characterizations of Computational Complexity

  1989cited by this paper
• Descriptive and Computational Complexity

  1989cited by this paper
• Expressibility and Parallel Complexity

  1989cited by this paper
• Nondeterministic space is closed under complementation

  1988cited by this paper
• Two applications of complementation via inductive counting

  1988cited by this paper
• Languages that Capture Complexity Classes

  1987cited by this paper
• Expressibility as a Complexity Measure: Results and Directions

  1987cited by this paper
• Skolem Normal Forms Concerning the Least Fixpoint

  1987cited by this paper
• Unification as a Complexity Measure for Logic Programming

  1987cited by this paper
• Henkin quantifiers and complete problems

  1986cited by this paper
• Horn Clauses Queries and Generalizations

  1985cited by this paper
• Fixed-point extensions of first-order logic

  1985cited by this paper
• Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae

  1984cited by this paper
• Relational queries computable in polynomial time (Extended Abstract)

  1982cited by this paper
• Symmetric Space-Bounded Computation

  1982cited by this paper
• Number of Quantifiers is Better Than Number of Tape Cells

  1981cited by this paper
• Upper and lower bounds for first order expressibility

  1980cited by this paper
• Structure and complexity of relational queries

  1980cited by this paper
• A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas

  1979cited by this paper
• The Polynomial-Time Hierarchy

  1976cited by this paper
• The circuit value problem is log space complete for P

  1975cited by this paper
• Complete problems for deterministic polynomial time

  1974cited by this paper
• Generalized first-order spectra, and polynomial. time recognizable sets

  1974cited by this paper
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary

  1967cited by this paper

• The Power of Negation in Higher-Order Datalog

  2025cites this paper
• Logical Characterizations of Weighted Complexity Classes

  2024cites this paper
• A Decidable Temporal DL-Lite Logic with Undecidable First-Order and Datalog-rewritability of Ontology-Mediated Atomic Queries (Extended Abstract)

  2023cites this paper
• Promise Algebra: An Algebraic Model of Non-Deterministic Computations

  2023cites this paper
• The Complexity and Expressive Power of Second-Order Extended Logic

  2022cites this paper
• Modular SAT-based techniques for reasoning tasks in team semantics

  2022cites this paper
• Capturing the polynomial hierarchy by second-order revised Krom logic

  2022cites this paper
• Towards Capturing PTIME with no Counting Construct (but with a Choice Operator)

  2021cites this paper
• Conjunctive Grammars, Cellular Automata and Logic

  2021cites this paper
• Complexity of Infinite-Domain Constraint Satisfaction

  2021cites this paper
• Inductive definitions in logic versus programs of real-time cellular automata

  2020cites this paper
• Descriptive complexity for minimal time of cellular automata

  2019cites this paper
• Proof complexity of systems of (non-deterministic) decision trees and branching programs

  2019cites this paper
• The Expressive Power of Higher-Order Datalog

  2019influential citation
• A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time

  2019cites this paper
• 1 8 O ct 2 01 9 Proof complexity of systems of ( non-deterministic ) decision trees and branching programs

  2019cites this paper
• Universal first-order logic is superfluous in the second level of the polynomial-time hierarchy

  2019cites this paper
• Descriptive Complexity for counting complexity classes

  2017cites this paper
• Definability by Horn Formulas and Linear Time on Cellular Automata

  2017cites this paper
• A logical approach to locality in pictures languages

  2016cites this paper
• Expressivity and Complexity of Dependence Logic

  2016cites this paper
• Existential Fixed-Point Logic as a Fragment of Second-Order Logic

  2015cites this paper
• Tractability Frontier of Data Complexity in Team Semantics

  2015cites this paper
• Universal First-Order Logic is Superfluous for NL, P, NP and coNP

  2014cites this paper
• More on Descriptive Complexity of Second-Order HORN Logics

  2014cites this paper
• Theoretical Computer Science

  2014cites this paper
• Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic

  2014cites this paper
• Arithmetic and Modularity in Declarative Languages for Knowledge Representation

  2013cites this paper
• Complexity and expressive power of second‐order extended Horn logic

  2013cites this paper
• Applications of finite model theory : optimisation problems, hybrid modal logics and games

  2013cites this paper
• On constraint satisfaction problems below P

  2013cites this paper
• Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap

  2013cites this paper
• A uniform approach to the complexity and analysis of succinct systems

  2012cites this paper
• A Fragment of Dependence Logic Capturing Polynomial Time

  2012influential citation
• Expressing versus Proving: Relating Forms of Complexity in Logic

  2012cites this paper
• On the complexity of fragments of second-order logic

  2011cites this paper
• Hierarchies in Dependence Logic

  2011cites this paper
• Model-based transformations for quantified boolean formulas

  2010cites this paper
• Coherence and complexity in fragments of dependence logic

  2010cites this paper
• On the Complexity of Model Expansion

  2010cites this paper
• Frameworks for Logically Classifying Polynomial-Time Optimisation Problems

  2010influential citation
• Algorithmic Model Theory Ss 2010

  2010cites this paper
• Power of Non-uniformity in Proof Complexity

  2009cites this paper
• A rendezvous of logic, complexity, and algebra

  2009cites this paper
• Approximate formulae for a logic that capture classes of computational complexity

  2008cites this paper
• Bounded reverse mathematics

  2008cites this paper
• Many Facets of Complexity in Logic

  2008cites this paper
• On the Expressiveness of Essence SFU Computing Science Technical Report TR 2007-19

  2008cites this paper
• Expressive power and abstraction in Essence

  2008cites this paper
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog

  2008cites this paper
• Model Expansion and the Expressiveness of FO ( ID ) and Other Logics

  2008influential citation
• Quantified constraint satisfaction and the polynomially generated powers property

  2008influential citation
• Bounded reverse mathematics

  2008cites this paper
• Expressing vs . proving : relating forms of complexity in logic

  2008cites this paper
• Rewriting Conjunctive Queries over Description Logic Knowledge Bases

  2008cites this paper
• On Canonical Forms of Complete Problems via First-order Projections

  2007cites this paper
• Foundations of Rule-Based Query Answering

  2007cites this paper
• Symmetric Datalog and Constraint Satisfaction Problems in Logspace

  2007cites this paper
• Grounding for Model Expansion in k-Guarded Formulas with Inductive Definitions

  2007cites this paper
• On the Expressive Power of Essence

  2007cites this paper
• Syntactic approximations to computational complexity classes

  2007cites this paper
• Model Expansion as a Framework for Modelling and Solving Search Problems

  2007cites this paper
• Finite Model Theory and Descriptive Complexity

  2007cites this paper
• The Complexity of Constraint Satisfaction Problems and Symmetric Datalog

  2007cites this paper
• Logic Column 17: A Rendezvous of Logic, Complexity, and Algebra

  2006cites this paper
• Complexity of Expanding a Finite Structure and Related Tasks

  2006cites this paper
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets

  2006cites this paper
• A rendezvous of logic, complexity, and algebra

  2006influential citation
• On a syntactic approximation to logics that capture complexity classes

  2006cites this paper
• Counting Proportions of Sets: Expressive Power with Almost Order

  2006cites this paper
• Closure Properties of Weak Systems of Bounded Arithmetic

  2005influential citation
• Invariance properties of RAMS and linear time

  2005cites this paper
• Linear datalog and bounded path duality of relational structures

  2005influential citation
• Constraint Programming with Unrestricted Quantification

  2005cites this paper
• A Framework for Representing and Solving NP Search Problems

  2005cites this paper
• Feasible Proofs of Matrix Properties with Csanky's Algorithm

  2005cites this paper
• An Attempt to Automate NP -Hardness Reductions via SO ∃ Logic

  2004cites this paper
• The Minimal Logically-Defined NP-Complete Problem

  2004cites this paper
• A second-order theory for NL

  2004cites this paper
• Arithmetical definability and computational complexity

  2004cites this paper
• Fixed Point Logics and Complexity Classes

  2004cites this paper
• Elements of Finite Model Theory

  2004cites this paper
• Solving Order Constraints in Logarithmic Space

  2003cites this paper
• A second-order system for polytime reasoning based on Grädel's theorem

  2003cites this paper
• Declarative constraint modelling and specification-level reasoning

  2003cites this paper
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

  2002cites this paper
• Constraint Satisfaction Problems in Non-deterministic Logarithmic Space

  2002cites this paper
• Substructural Verification and Computational Feasibility

  2002cites this paper
• Fixed-point logics, descriptive complexity, and random satisfiability

  2002cites this paper
• UNA PRESENTACION UNIFORME DE LA TEORIA DESCRIPTIVA DE LA COMPLEJIDAD COMPUTACIONAL

  2002cites this paper
• Capture Complexity by Partition

  2001cites this paper
• Contributions à la théorie des modèles finis et à la complexité descriptive. (Contributions to finite model theory and descriptive complexity)

  2001cites this paper
• A second-order system for polytime reasoning using Gradel's theorem

  2001cites this paper
• Existential second-order logic over graphs: charting the tractability frontier

  2000cites this paper
• 2000 Annual Meeting of the Association for Symbolic Logic

  2000cites this paper
• Generalized Quantifiers and Computation

  2000influential citation
• On the complexity of single-rule datalog queries

  1999influential citation
• Descriptive Complexity

  1999cites this paper
• A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

  1999cites this paper
• Spectral Problems and Descriptive Complexity Theory

  1998cites this paper