Parallel and two-way automata on directed ordered acyclic graphs
From MaRDI portal
Publication:3940852
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
directed acyclic graphsgraph automataclosure properties of classes of d-dag languagesderivation dagsderivations of phrase structure grammars
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
