# Hankel Matrices and Definability

דובר:
נאדיה לבאי, הרצאה סמינריונית למגיסטר
תאריך:
יום רביעי, 14.1.2015, 16:30
מקום:
טאוב 601
מנחה:
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.

בחזרה לאינדקס האירועים