10.45 a.m. Logics with Matrix Rank Operators Anuj Dawar Cambridge University, UK. 23-12-09 Abstract I will look at recent work studying extensions of first-order logic and fixed-point logic with operators for computing the rank of matrices. It is shown that these can define the various polynomial-time problems that are not definable in fixed-point logic with counting. I will look at games for characterising expressibility in this logic and conclude with a number of open problems.
|