Parallel and two-way automata on directed ordered acyclic graphs

DOI10.1016/S0019-9958(81)90438-1zbMath0482.68051OpenAlexW2074048601MaRDI QIDQ3940852

Giora Slutzki, Tsutomu Kamimura

Publication date: 1981

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(81)90438-1

zbMATH Keywords

directed acyclic graphsgraph automataclosure properties of classes of d-dag languagesderivation dagsderivations of phrase structure grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

Alternating tree automata ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Query Automata for Nested Words ⋮ Automata for XML -- a survey ⋮ On the power of tree-walking automata. ⋮ Regular languages with variables on graphs ⋮ Reversibility of computations in graph-walking automata ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ Graph automata ⋮ Recognizability of graph and pattern languages ⋮ An axiomatization of graphs ⋮ Language theoretic properties of regular DAG languages ⋮ On a code problem concerning planar acyclic graphs ⋮ The time complexity of typechecking tree-walking tree transducers ⋮ Graph Automata: The Algebraic Properties of Abelian Relational Graphoids ⋮ On regular tree languages and deterministic pushdown automata ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ MINIMIZATION OF PLANAR DIRECTED ACYCLIC GRAPH ALGEBRAS ⋮ Tree-walking automata cannot be determinized

This page was built for publication: Parallel and two-way automata on directed ordered acyclic graphs