8 citations · 8 across the 2 of their papers we have counts for
Showing cs.LOShow all
3 papers · 1 filter
cs.LO2013
Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
Matthew Anderson, Anuj Dawar, Bjarki Holm
We establish the expressibility in fixed-point logic with counting (FPC) of a number of natural polynomial-time problems. In particular, we show that the size of a maximum matching…
cs.LO2012
Pebble games with algebraic rules
Anuj Dawar, Bjarki Holm
We define a general framework of partition games for formulating two-player pebble games over finite structures. We show that one particular such game, which we call the invertible…
cs.LO2012★ 8 cited
Definability of linear equation systems over groups and rings
Anuj Dawar, Eryk Kopczynski, Bjarki Holm +2
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the s…