• search hit 42 of 104
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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):License LogoEs gilt das deutsche Urheberrecht: § 53 UrhG