Blass, Andreas

Fixed-point logic with counting ★★

Author(s): Blass

Question Can either of the following be expressed in fixed-point logic plus counting:

Given a graph, does it have a perfect matching, i.e., a set $M$ of edges such that every vertex is incident to exactly one edge from $M$ ?
Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?

Posted by dberwanger
updated May 18th, 2012