Existential second-order logic over graphs
From MaRDI portal
Publication:5501192
DOI10.1145/972639.972646zbMath1316.68054WikidataQ59259689 ScholiaQ59259689MaRDI QIDQ5501192
Phokion G. Kolaitis, Thomas Schwentick, Georg Gottlob
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
68Q25: Analysis of algorithms and problem complexity
05C99: Graph theory
03C13: Model theory of finite structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q19: Descriptive complexity and finite models
Related Items
DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS, Existential second-order logic and modal logic with quantified accessibility relations, Model-checking hierarchical structures, 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, 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