Equivalence in finite-variable logics is complete for polynomial time
From MaRDI portal
Publication:1977423
DOI10.1007/s004939970004zbMath0987.03033OpenAlexW2173290940MaRDI QIDQ1977423
Publication date: 14 May 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004939970004
Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Related Items (6)
Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements ⋮ Graph isomorphism, color refinement, and compactness ⋮ On Tinhofer’s Linear Programming Approach to Isomorphism Testing ⋮ Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ Structural characterizations of the navigational expressiveness of relation algebras on a tree ⋮ On complexity of Ehrenfeucht-Fraïssé games
This page was built for publication: Equivalence in finite-variable logics is complete for polynomial time