Equivalence in finite-variable logics is complete for polynomial time

DOI10.1007/s004939970004zbMath0987.03033OpenAlexW2173290940MaRDI QIDQ1977423

Martin Grohe

Publication date: 14 May 2000

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004939970004

zbMATH Keywords

first-order logicisomorphismcomplexity of equivalence checking

Mathematics Subject Classification ID

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