An optimal lower bound on the number of variables for graph identification

1992/12/01 by Jin‐Yi Cai, Jin-Yi Cai, Martin F�rer +1 · 10 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #semigroups and automata theory

paper · doi:10.1007/bf01305232

crossref issued 1992/12/01 · crossref published 1992/12/01 · crossref published-print 1992/12/01 · openalex publication_date 1992/12/01 · crossref created 2005/03/25 · crossref deposited 2024/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25 · crossref indexed 2026/08/04

Citations

• Languages that Capture Complexity Classes
• Number of quantifiers is better than number of tape cells

Cited by

• Schemes for deterministic polynomial factoring
• Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Capturing Polynomial Time on Interval Graphs
• The first order definability of graphs with separators via the Ehrenfeucht game
• On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
• Symmetric Proofs in the Ideal Proof System
• Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
• Graph Kernels Exploiting Weisfeiler-Lehman Graph Isomorphism Test Extensions
• Logic of graphs [wikipedia]