Bottom-up tree pushdown automata: Classification and connection with rewrite systems
From MaRDI portal
Publication:1325836
DOI10.1016/0304-3975(94)90101-5zbMath0805.68083OpenAlexW1974542856MaRDI QIDQ1325836
Sándor Vágvölgyi, Max Dauchet, Jean-Luc Coquidé, Rémi Gilleron
Publication date: 15 May 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90101-5
Related Items
Right-linear half-monadic term rewrite systems ⋮ Losing recognizability ⋮ Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy ⋮ Descendants of a recognizable tree language for sets of linear monadic term rewrite rules ⋮ Linear generalized semi-monadic rewrite systems effectively preserve recognizability ⋮ The equivalence problem for letter-to-letter bottom-up tree transducers is solvable ⋮ Decidability for left-linear growing term rewriting systems. ⋮ One-variable context-free hedge automata ⋮ Term rewriting restricted to ground terms. ⋮ Normalization properties for shallow TRS and innermost rewriting ⋮ Reachability analysis over term rewriting systems ⋮ Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Congruential complements of ground term rewrite systems ⋮ A property of left-linear rewrite systems preserving recognizability ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION ⋮ Derivation trees of ground term rewriting systems.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
- Tree pushdown automata
- Reductions in tree replacement systems
- Thue systems as rewriting systems
- Deterministic tree pushdown automata and monadic tree rewriting systems
- Pushdown tree automata
- Semantic confluence tests and completion methods
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Bottom-up and top-down tree transformations— a comparison
- Bottom-up tree pushdown automata and rewrite systems
- Tree generating regular systems