3 citations · 5 across the 6 of their papers we have counts for
Showing math.LOShow all
3 papers · 1 filter
math.LO2004
Definitions with no quantifier alternation
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Let be the minimum quantifier depth of a first order sentence that defines a graph up to isomorphism. Let be the version of where we do not allow qua…
math.LO2004
Succinct Definitions in the First Order Theory of Graphs
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifi…
math.LO2003★ 1 cited
Descriptive Complexity of Finite Structures: Saving the Quantifier Rank
Oleg Pikhurko, Oleg Verbitsky
Given a relational structure M on n elements, let D(M) be the minimum quantifier rank of a first order formula identifying M up to isomorphism in the class of n-element structures.…