Finite automata on unranked and unordered DAGs
- We introduce linear expressions for unrestricted dags (directed acyclic graphs) and finite deterministic and nondeterministic automata operating on them. Those dag automata are a conservative extension of the Tu,u-automata of Courcelle on unranked, unordered trees and forests. Several examples of dag languages acceptable and not acceptable by dag automata and some closure properties are given.
| Author: | Lutz Priese |
|---|---|
| URN: | urn:nbn:de:kola-1311 |
| Series (Volume no.): | Arbeitsberichte, FB Informatik (2007,22) |
| Document Type: | Part of Periodical |
| Language: | English |
| Date of completion: | 2007/07/24 |
| Date of publication: | 2007/07/24 |
| Publishing institution: | Universität Koblenz-Landau, Campus Koblenz, Universitätsbibliothek |
| Release Date: | 2007/07/24 |
| Tag: | directed acyclic graphs; finite state automata; regular dag languages directed acyclic graphs; finite state automata; regular dag languages |
| Edition: | Extended version |
| Number of pages: | 19 |
| Institutes: | Fachbereich 4 / Fachbereich 4 |
| Fachbereich 4 / Institut für Computervisualistik | |
| Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Licence (German): |  Es gilt das deutsche Urheberrecht: § 53 UrhG |
