Logical hierarchies in PTIME
From MaRDI portal
Publication:1817218
DOI10.1006/inco.1996.0070zbMath0864.68095OpenAlexW2152035036MaRDI QIDQ1817218
Publication date: 22 June 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1996.0070
Logic in artificial intelligence (68T27) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)
Related Items
Finite Variable Logics in Descriptive Complexity Theory, Limitations of Algebraic Approaches to Graph Isomorphism Testing, Generalized quantifiers and pebble games on finite structures, Counting quantifiers, successor relations, and logarithmic space, Directions in generalized quantifier theory, How to define a linear order on finite models, A double arity hierarchy theorem for transitive closure logic, CFI Construction and Balanced Graphs, Graphs Identified by Logics with Counting, Capturing complexity classes with Lindström quantifiers, Pebble games and cospectral graphs, Expressive power of SQL., Constructing Hard Examples for Graph Isomorphism, Epsilon-logic is more expressive than first-order logic over finite structures, On the expressive power of counting, Game-based notions of locality over finite models, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, On the Weisfeiler-Leman dimension of fractional packing, Unnamed Item, Notions of locality and their logical characterizations over finite models, On the expressive power of linear algebra on graphs, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, Definable Inapproximability: New Challenges for Duplicator, Affine systems of equations and counting infinitary logic, Relating Structure and Power: Comonadic Semantics for Computational Resources, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, The Weisfeiler-Leman algorithm and recognition of graph properties, Local properties of query languages, Arity hierarchies, Lower bounds for invariant queries in logics with counting., Counting modulo quantifiers on finite structures, Canonisation and Definability for Graphs of Bounded Rank Width, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs
