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

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

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

(12)

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

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)