10 citations · 44 across the 41 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.LO2012
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Given two structures and distinguishable in $\fo k$ (first-order logic with variables), let denote the minimum alternation depth of a $\fo k$ formula disting…
cs.CC2012
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are e…