umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2015.
Series
UMNAD, 1016
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:umu:diva-105612OAI: oai:DiVA.org:umu-105612DiVA: diva2:827036
Educational program
Master's Programme in Computing Science
Supervisors
Examiners
Available from: 2015-06-26 Created: 2015-06-26 Last updated: 2015-06-26Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 71 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

urn-nbn

Altmetric score

urn-nbn
Total: 187 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf