We formulate a formal syntax of approximate formulas for the logic with counting
quantifiers, \mathcal{SOLP}, studied by us in \cite{aaco06}, where we showed the
following facts:
(i) In the presence of a built--in (linear) order, \mathcal{SOLP} can
describe {\bf NP}--complete problems and fragments of it capture classes like
{\bf P} ... more >>>

Two graphs with adjacency matrices \mathbf{A} and \mathbf{B} are isomorphic if there exists a permutation matrix \mathbf{P} for which the identity \mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B} holds. Multiplying through by \mathbf{P} and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>>