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

DOI10.1145/972639.972646MaRDI QIDQ5501192zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick

Publication date 1 August 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/972639.972646

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Graph theory (05C99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Existential second-order logic over graphs: a complete complexity-theoretic classification
• Existential second-order logic over strings
• scientific article; zbMATH DE number 1254648
• scientific article; zbMATH DE number 17544
• The closure of monadic NP

Cited in

(14)

• Existential monadic second order logic on random rooted trees
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Closure properties of locally finite \(\omega\)-languages
• On the parameterized complexity of graph modification to first-order logic properties
• Existential second-order logic and modal logic with quantified accessibility relations
• Existential second-order logic over graphs: a complete complexity-theoretic classification
• Learning Tree Languages
• Second-Order Logic over Finite Structures – Report on a Research Programme
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Model-checking hierarchical structures
• Dichotomy result for independence-friendly prefixes of generalized quantifiers
• Existential Graphs as a Basis for Structural Reasoning
• Existential second-order logic over graphs: parameterized complexity
• On the descriptive complexity of vertex deletion problems

This page was built for publication: Existential second-order logic over graphs: charting the tractability frontier

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