Graph structures reveal new insights into automata and languages
Graph-based automata
Formal Languages and Automata Theory
Summary
The paper explores how graphs can be used to build automata, a kind of machine that reads sequences like paths in a network. The authors extend this idea from sequences (paths) to branching structures called trees and describe which languages or patterns these graph-based automata can recognize. They also find the simplest possible graphs that represent these languages and connect these ideas to reversible automata, a type of machine with back-and-forth behavior. Additionally, they study a special set of sequences related to all possible orientations of a graph that reflect key graph properties such as its coloring.
nondeterministic finite automataedge-colored graphsoriented graphstree languagesgraph homomorphismreversible automatachromatic numbergraph orientationlanguage recognitionautomata theory
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.