Graph-based automata reveal new links between automata and graph theory
Graph-based automata
Formal Languages and Automata Theory
Summary
This paper looks at a special kind of computational model called graph-based automata, which are built from graphs with colored or directed edges. The authors connect these models to familiar ideas in automata theory, but also extend them to trees. They find unique minimal graphs that represent these languages and show how these automata relate to reversible automata. New concepts like the remanent language of a graph help capture graph properties such as how many colors are needed to color it.
What this means in practice
- •For software engineers: Identify minimal graph structures to optimize pattern recognition in software models based on graph automata.
- •For network analysts: Use remanent language properties to better understand network structure and constraints like channel assignments reflected by chromatic numbers.
A theory result. No direct application yet.
Authors
Cyril Pujol
Abstract
We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.