DAG Automata - Variants, Languages and Properties
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
We study final-state automata that work on directed acyclic graphs (DAGs). We consider ordered and unordered DAGs and show that they can be simulated by each other. Then we show that deterministic DAG automata are weaker then nondeterministic automata. Some properties of recognizable DAG languages are presented and the decidability of the finiteness problem is shown. Finally we compare tree and DAG automata and show that the path language of a DAG language is regular by proving that the tree unfolding of a DAG language preserves recognizability.
Place, publisher, year, edition, pages
, UMNAD, 1016
Engineering and Technology
IdentifiersURN: urn:nbn:se:umu:diva-105612OAI: oai:DiVA.org:umu-105612DiVA: diva2:827036
Master's Programme in Computing Science