The reachability and related decision problems for monadic and semi-constructor TRSs

DOI10.1016/J.IPL.2006.02.014MaRDI QIDQ844204zbMATH OpenOpenAlexFDO

Authors Ichiro Mitsuhashi, Michio Oyamaguchi, Toshiyuki Yamada

Publication date 18 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.02.014

zbMATH Keywords

term rewriting systemstheory of computation

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Rewriting Techniques and Applications
• The Confluence Problem for Flat TRSs
• Reachability and confluence are undecidable for flat term rewriting systems
• Decidability of confluence and termination of monadic term rewriting systems
• Undecidable properties of flat term rewrite systems

Cites work

• Algorithms and reductions for rewriting problems
• Reachability and confluence are undecidable for flat term rewriting systems
• Rewriting Techniques and Applications

Cited in

(7)

• Problematic configurations and choice-join pairs on Mono-T-Semiflow nets: towards the characterization of behavior-structural properties
• Reachability via cooperating morphisms
• New Undecidability Results for Properties of Term Rewrite Systems
• The Confluence Problem for Flat TRSs
• Rewriting Techniques and Applications
• Tail reduction free term rewriting systems revisited
• Murg term rewrite systems

This page was built for publication: The reachability and related decision problems for monadic and semi-constructor TRSs

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