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.
| Verfasserangaben: | Lutz Priese |
|---|---|
| URN: | urn:nbn:de:kola-1311 |
| Schriftenreihe (Bandnummer): | Arbeitsberichte, FB Informatik (2007,22) |
| Dokumentart: | Ausgabe (Heft) zu einer Zeitschrift |
| Sprache: | Englisch |
| Datum der Fertigstellung: | 24.07.2007 |
| Datum der Veröffentlichung: | 24.07.2007 |
| Veröffentlichende Institution: | Universität Koblenz-Landau, Campus Koblenz, Universitätsbibliothek |
| Datum der Freischaltung: | 24.07.2007 |
| Freies Schlagwort / Tag: | directed acyclic graphs; finite state automata; regular dag languages directed acyclic graphs; finite state automata; regular dag languages |
| Auflage: | Extended version |
| Seitenzahl: | 19 |
| Institute: | Fachbereich 4 / Fachbereich 4 |
| Fachbereich 4 / Institut für Computervisualistik | |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Lizenz (Deutsch): |  Es gilt das deutsche Urheberrecht: § 53 UrhG |
