Hankel Matrices and Definability

Nadia Labai, M.Sc. Thesis Seminar

Wednesday, 14.1.2015, 16:30

Taub 601

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)$, 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. Lovasz and used to study real-valued
partition functions of graphs, where the role of concatenation is played by $k$-connections of $k$-graphs,
i.e., graphs with $v_1, \ldots, v_k$ distinguished vertices. The Hankel matrix $H(f, \sqcup_k)$ is
the infinite matrix where rows and columns are labeled by $k$-graphs and the entry
$H(f, \sqcup_k)_{G, G'}$ is given by $f(G \sqcup_k G')$.
We survey recent work on the use of Hankel matrices $H(f, \Box)$ for real-valued graph parameters $f$
and a binary operation $\Box$ on labeled graphs such as the disjoint union and various gluing
operations of pairs of labeled graphs. Special cases deal with real-valued word functions.
We consider graph parameters definable in Monadic Second Order Logic MSOL and show how MSOL-definability
can be replaced by the assumption that $H(f, \Box)$ has finite rank.