The Taub Faculty of Computer Science Events and Talks

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.