2015 | OriginalPaper | Chapter
Hankel Matrices: From Words to Graphs (Extended Abstract)
Authors : Johann A. Makowsky, Nadia Labai
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We survey recent work on the use of Hankel matrices
$$H(f, \Box )$$
for real-valued graph parameters
$$f$$
and a binary sum-like operation
$$\Box $$
on labeled graphs such as the disjoint union and various gluing operations of pairs of laeled graphs. Special cases deal with real-valued word functions. We start with graph parameters definable in Monadic Second Order Logic
$$\mathrm {MSOL}$$
and show how
$$\mathrm {MSOL}$$
-definability can be replaced by the assumption that
$$H(f, \Box )$$
has finite rank. In contrast to
$$\mathrm {MSOL}$$
-definable graph parameters, there are uncountably many graph parameters
$$f$$
with Hankel matrices of finite rank. We also discuss how real-valued graph parameters can be replaced by graph parameters with values in commutative semirings.