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 graphsautomata on acyclic graphsdeterministic graph automatafinite-state graph automatalabelled finite graphsnon-deterministic graph automatarecognizability of graph languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Related Items (10)

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

This page was built for publication: Nondeterminism versus determinism of finite automata over directed acyclic graphs