Graphs with Automatic Presentations over a Unary Alphabet
Bakhadyr Khoussainov, Sasha Rubin · Universitätsbibliothek Gießen · 2001
A relational structure is automatic if its domain and atomic relations are recognized by finite automata (FA). In this paper, a finite automaton recognizable $n$-ary relation is one accepted by a synchronous n-tape finite automaton. A structure is automatically presentable if it is isomorphic to an automatic structure. We focus on the class of automatic graphs whose domains are unary strings. The main result characterizes the isomorphism types of these graphs using a graph-theoretic construction called an unwinding.