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

DOI10.1016/0304-3975(94)90101-5MaRDI QIDQ1325836zbMATH OpenOpenAlexFDO

Authors Jean-Luc Coquidé, Max Dauchet, Rémi Gilleron, Sándor Vágvölgyi

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

decidabilityrecognizabilityrewrite systemsbottom-up tree pushdown automataground reducibility

Mathematics Subject Classification ID

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

Recommendations

• Bottom-up tree pushdown automata and rewrite systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Deterministic bottom-up tree transducers and ground term rewrite systems
• Linear generalized semi-monadic rewrite systems effectively preserve recognizability
• Bottom-Up Rewriting Is Inverse Recognizability Preserving

Cites work

• scientific article; zbMATH DE number 4157904 (Why is no real title available?)
• scientific article; zbMATH DE number 17534 (Why is no real title available?)
• scientific article; zbMATH DE number 176501 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• Bottom-up and top-down tree transformations— a comparison
• Bottom-up tree pushdown automata and rewrite systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Pushdown tree automata
• Reductions in tree replacement systems
• Semantic confluence tests and completion methods
• Thue systems as rewriting systems
• Tree generating regular systems
• Tree pushdown automata

Cited in

(26)

• Deterministic tree pushdown automata and monadic tree rewriting systems
• Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy
• Congruential complements of ground term rewrite systems
• Deterministic bottom-up tree transducers and ground term rewrite systems
• The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
• Bottom-up tree pushdown automata and rewrite systems
• Linear generalized semi-monadic rewrite systems effectively preserve recognizability
• Term rewriting restricted to ground terms.
• Decidability and complexity of simultaneous rigid E-unification with one variable and related results
• Losing recognizability
• One-variable context-free hedge automata
• scientific article; zbMATH DE number 1530017 (Why is no real title available?)
• Right-linear half-monadic term rewrite systems
• Decidability for left-linear growing term rewriting systems.
• scientific article; zbMATH DE number 1786544 (Why is no real title available?)
• Bottom-up rewriting for words and terms
• Reachability analysis over term rewriting systems
• Some undecidability results concerning the property of preserving regularity
• Descendants of a recognizable tree language for sets of linear monadic term rewrite rules
• Refining the process rewrite systems hierarchy via ground tree rewrite systems
• scientific article; zbMATH DE number 7315101 (Why is no real title available?)
• Visibly Pushdown Languages and Term Rewriting
• A property of left-linear rewrite systems preserving recognizability
• RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION
• Normalization properties for shallow TRS and innermost rewriting
• Derivation trees of ground term rewriting systems.

This page was built for publication: Bottom-up tree pushdown automata: Classification and connection with rewrite systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1325836)