Technical Report MSC-2015-11

TR#:MSC-2015-11
Class:MSC
Title: Definability and Hankel Matrices
Authors: Nadia Labai
Supervisors: Johann A. Makowsky
PDFCurrently accessibly only within the Technion network
Abstract: 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 and colored 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2015/MSC/MSC-2015-11), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion
admin