Finite State Automata accepting Directed Acyclic Graphs

Analogously to regular string and tree languages, regular languages of directed acyclic graphs (DAGs) have been defined in literature. Although called regular, those DAG-languages are way more powerful and, consequently, standard problems have a higher complexity than in the string case. Top-down as well as bottom-up deterministic DAG languages are subclasses of the regular DAG languages. We refine this hierarchy by providing a weaker subclass of the deterministic DAG languages. For a DAG grammar generating a language in this new DAG language class, or, equivalently, a DAG-automaton recognizing it, a classical deterministic finite state automaton (DFAs) can be constructed. As the main result, we provide a characterization of this class. The motivation behind this is the transfer of techniques for regular string languages to graphs. Trivially, our restricted DAG language class is closed under union and intersection, and permits the application of minimization and hyper-minimization algorithms known for DFAs. The alternative notion of regularity coins at the existence of a DFA for recognizing a DAG language.