Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Hankel Matrices and Definability
event speaker icon
Nadia Labai (M.Sc. Thesis Seminar)
event date icon
Wednesday, 14.01.2015, 16:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. J. A. Makowsky
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.