Decision problems for term rewriting systems and recognizable tree languages

DOI10.1007/BFB0020795MaRDI QIDQ4035665zbMATH OpenFDO

Authors Rémi Gilleron

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020795

zbMATH Keywords

confluence propertyrecognizable tree languages

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 794243
• Rewriting preserving recognizability of finite tree languages
• Undecidable properties of deterministic top-down tree transducers
• Decidability of regularity and related properties of ground normal form languages
• Decidability of regularity and related properties of ground normal form languages

Cited in

(29)

• Linear generalized semi-monadic rewrite systems effectively preserve recognizability
• Some undecidability results concerning the property of preserving regularity
• Decidability of the existential theory of infinite terms with subterm relation
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Undecidable properties of deterministic top-down tree transducers
• A property of left-linear rewrite systems preserving recognizability
• Decidability of regularity and related properties of ground normal form languages
• Rewriting preserving recognizability of finite tree languages
• Losing recognizability
• Some decidability results on one-pass reductions
• One-variable context-free hedge automata
• Tree automata for rewrite strategies
• Linear bounded automata and rewrite systems: influence of initial configurations on decision properties
• Visibly Pushdown Languages and Term Rewriting
• scientific article; zbMATH DE number 5722791 (Why is no real title available?)
• scientific article; zbMATH DE number 17534 (Why is no real title available?)
• scientific article; zbMATH DE number 19765 (Why is no real title available?)
• scientific article; zbMATH DE number 1354853 (Why is no real title available?)
• scientific article; zbMATH DE number 2090070 (Why is no real title available?)
• scientific article; zbMATH DE number 794243 (Why is no real title available?)
• Homomorphisms and concurrent term rewriting
• Deciding the satisfiability of quantifier free formulae on one-step rewriting
• A new result about the decidability of the existential one-step rewriting theory
• Open problems in rewriting
• More problems in rewriting
• Decidable approximations of term rewriting systems
• Decidability of regularity and related properties of ground normal form languages
• Restricting tree grammars with term rewriting
• Descendants of a recognizable tree language for sets of linear monadic term rewrite rules

This page was built for publication: Decision problems for term rewriting systems and recognizable tree languages

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