Existential second-order logic over graphs: charting the tractability frontier

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Proceedings 41st Annual Symposium on Foundations of Computer Science

• Publication date

  2000-11-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2000.892334
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Second-Order Logic over Strings: Regular and Non-regular Fragments

  2001cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Existential second-order logic over strings

  1998influential reference
• The Classical Decision Problem

  1997influential reference
• Descriptive Complexity Theory

  1995cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993influential reference
• Bounded Tree-Width and LOGCFL

  1993cited by this paper
• Optimization, approximation, and complexity classes

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

  1991cited by this paper
• Capturing Complexity Classes by Fragments of Second-Order Logic

  1991cited by this paper
• The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

  1990influential reference
• On the presence of disjoint subgraphs of a specified type

  1988influential reference
• Nondeterministic space is closed under complementation

  1988cited by this paper
• Graph Minors. II. Algorithmic Aspects of Tree-Width

  1986cited by this paper
• Graph minors. III. Planar tree-width

  1984influential reference
• On the Structure of Polynomial Time Reducibility

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

  1974cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper
• Weak Second‐Order Arithmetic and Finite Automata

  1960cited by this paper

• Hereditary First-Order Logic: the Tractable Quantifier Prefix Classes

  2024influential citation
• On the Descriptive Complexity of Vertex Deletion Problems

  2024cites this paper
• Existential Second-Order Logic Over Graphs: Parameterized Complexity

  2023influential citation
• Parameterized Complexity of Elimination Distance to First-Order Logic Properties

  2022cites this paper
• Parameterized Complexity of Elimination Distance to First-Order Logic Properties

  2021cites this paper
• Existential monadic second order logic on random rooted trees

  2019cites this paper
• A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time

  2019cites this paper
• On the Parameterized Complexity of Graph Modification to First-Order Logic Properties

  2018cites this paper
• Second order logic on random rooted trees

  2017cites this paper
• Existential second-order logic and modal logic with quantified accessibility relations

  2016cites this paper
• A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes

  2016influential citation
• Complexity of syntactical tree fragments of Independence-Friendly logic

  2016cites this paper
• Learning Tree Languages

  2016cites this paper
• Topics in Grammatical Inference

  2016cites this paper
• Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification

  2014cites this paper
• DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS

  2014influential citation
• Applications of finite model theory : optimisation problems, hybrid modal logics and games

  2013cites this paper
• Structural Decomposition Methods and What They are Good For

  2011cites this paper
• Hierarchies in Dependence Logic

  2011cites this paper
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey

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

  2010cites this paper
• Statistical Second-Order Predicate: A Decision Model in Uncertain Dataset

  2009cites this paper
• Destructive Rule-Based Properties and First-Order Logic

  2009cites this paper
• Predicate-calculus-based logics for modeling and solving search problems

  2006influential citation
• Under Consideration for Publication in Theory and Practice of Logic Programming Combining Relational Algebra, Sql, Constraint Modelling, and Local Search *

  2006influential citation
• Combining relational algebra, SQL, constraint modelling, and local search*

  2006influential citation
• Model-checking hierarchical structures

  2005cites this paper
• Regular Vacuity

  2005cites this paper
• Finite model theory for partially ordered connectives

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

  2004cites this paper
• Closure properties of locally finite omega-languages

  2004cites this paper
• Elements of Finite Model Theory

  2004cites this paper
• Second-Order Logic over Finite Structures - Report on a Research Programme

  2004influential citation
• The Minimal Logically-Defined NP-Complete Problem

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

  2003cites this paper
• Combining Relational Algebra, SQL, and Constraint Programming

  2002cites this paper
• Knowledge compilation = query rewriting + view synthesis

  2002cites this paper