Nondeterminism versus determinism of finite automata over directed acyclic graphs

zbMath0803.68032MaRDI QIDQ1326955

Sebastian Seibert, Wolfgang Thomas, Andreas Potthoff

Publication date: 15 June 1994

Published in: Bulletin of the Belgian Mathematical Society - Simon Stevin (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/226178

zbMATH Keywords

directed acyclic graphs; automata on acyclic graphs; deterministic graph automata; finite-state graph automata; labelled finite graphs; non-deterministic graph automata; recognizability of graph languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68R10: Graph theory (including graph drawing) in computer science

03D05: Automata and formal grammars in connection with logical questions

Related Items

Deterministic and unambiguous two-dimensional languages over one-letter alphabet, Some notes on graph automata, tiling systems and partition logic, Grammatical inference of directed acyclic graph languages with polynomial time complexity, Language theoretic properties of regular DAG languages, Communication complexity tools on recognizable picture languages, Classes of two-dimensional languages and recognizability conditions, Unambiguous recognizable two-dimensional languages, Tiling Recognizable Two-Dimensional Languages, Deterministic Two-Dimensional Languages over One-Letter Alphabet