Existential second-order logic over graphs

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

Mathematics Subject Classification ID

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