{"id":"arxiv/2609.08843","url":"https://arxiv.org/abs/2609.08843","tags":["cs.FL","math.CO"],"score":0,"title":"Graph-based automata","domain":"cs.FL","source":"arxiv","authors":["Cyril Pujol"],"reviews":0,"subject":"cs.FL","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}