Bottom-up tree pushdown automata: Classification and connection with rewrite systems

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

zbMATH Keywords

decidabilityrewrite systemsrecognizabilitybottom-up tree pushdown automataground reducibility

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

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