Deterministic tree pushdown automata and monadic tree rewriting systems

DOI10.1016/0022-0000(88)90014-1zbMath0668.68084OpenAlexW2026901712MaRDI QIDQ1118421

Kai Salomaa

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90014-1

zbMATH Keywords

tree automatatree languagesdeterministic tree pushdown automatontree rewriting system

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (26)

Bottom-up tree pushdown automata: Classification and connection with rewrite systems ⋮ Controlled Term Rewriting ⋮ Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy ⋮ Decidability of confluence and termination of monadic term rewriting systems ⋮ Bottom-up tree pushdown automata and rewrite systems ⋮ Descendants of a recognizable tree language for sets of linear monadic term rewrite rules ⋮ Linear generalized semi-monadic rewrite systems effectively preserve recognizability ⋮ Decidability for left-linear growing term rewriting systems. ⋮ One-variable context-free hedge automata ⋮ Term rewriting restricted to ground terms. ⋮ Tree automata for rewrite strategies ⋮ Reachability analysis of fragments of mobile ambients in AC term rewriting ⋮ On characterization of fuzzy tree pushdown automata ⋮ Normalization properties for shallow TRS and innermost rewriting ⋮ Closure of Tree Automata Languages under Innermost Rewriting ⋮ Rigid tree automata and applications ⋮ Murg term rewrite systems ⋮ Reachability analysis over term rewriting systems ⋮ Termination criteria for tree automata completion ⋮ Unique Normalization for Shallow TRS ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Handling Left-Quadratic Rules When Completing Tree Automata ⋮ Lattice-valued tree pushdown automata: pumping lemma and closure properties ⋮ Congruential complements of ground term rewrite systems ⋮ A property of left-linear rewrite systems preserving recognizability ⋮ Decidability of EDT0L structural equivalence

Cites Work

• Unnamed Item
• Tree pushdown automata
• Reductions in tree replacement systems
• Thue systems as rewriting systems
• Monadic Thue systems
• Un théorème de duplication pour les forets algébriques
• IO and OI. II
• Pushdown tree automata
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Forêts Algébriques et Homomorphismes Inverses
• Indexed Grammars—An Extension of Context-Free Grammars
• Mappings and grammars on trees
• Tree-Manipulating Systems and Church-Rosser Theorems

This page was built for publication: Deterministic tree pushdown automata and monadic tree rewriting systems