Change search
ReferencesLink to record
Permanent link

Direct link
DAG Automata - Variants, Languages and Properties
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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
National Category
Engineering and Technology
URN: urn:nbn:se:umu:diva-105612OAI: diva2:827036
Educational program
Master's Programme in Computing Science
Available from: 2015-06-26 Created: 2015-06-26 Last updated: 2015-06-26Bibliographically approved

Open Access in DiVA

fulltext(484 kB)48 downloads
File information
File name FULLTEXT01.pdfFile size 484 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 48 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 134 hits
ReferencesLink to record
Permanent link

Direct link