Existential second-order logic over graphs: charting the tractability frontier
DOI10.1145/972639.972646zbMATH Open1316.68054DBLPjournals/jacm/GottlobKS04OpenAlexW2055288944WikidataQ59259689 ScholiaQ59259689MaRDI QIDQ5501192FDOQ5501192
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
Recommendations
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)
Cited In (12)
- 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
- Existential Graphs as a Basis for Structural Reasoning
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)
