In automata theory, a Hankel matrix $H(f,\circ)$ is an infinite matrix where the rows and columns are labeled with words $w$ over a fixed alphabet $\Sigma$, and the entry $H(f,\circ)_{u,v}$ is given by $f(u \circ v)$ for words $u$ and $v$, where $f$ is a real-valued word function and $\circ$ denotes concatenation. A classical result of G.W. Carlyle and A. Paz (1971) in automata theory characterizes real-valued word functions f recognizable by weighted automata as the functions for which the Hankel matrix has finite rank .

Hankel matrices for graph parameters were introduced by L. Lovász (2007) and used to characterize real-valued partition functions of graphs .

 
We study the use of Hankel matrices $H(f,\Box)$ for graph parameters f and various binary operations $\Box$ on labeled graphs .

We consider meta-theorems connecting the definability of graph parameters to their computational complexity on certain graph classes, such as Courcelle’s theorem, stating that definable graph properties are computable in linear time over graph classes of bounded tree-width, and generalizations thereof, and show how to eliminate logic from these theorems by replacing the definability assumption with a finiteness assumption on the rank of the Hankel matrices involved .

As a special case, we also consider word functions and show that word functions are definable in Monadic Second Order Logic (MSOL) if and only if their Hankel matrices for concatenation have finite rank .