Ground reachability and joinability in linear term rewriting systems are fixed parameter tractable with respect to depth

DOI10.4230/LIPICS.IPEC.2016.25MaRDI QIDQ4634409zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira

Publication date 10 April 2018

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/6925/pdf/LIPIcs-IPEC-2016-25.pdf/

zbMATH Keywords

fixed parameter tractabilityground reachabilityground joinabilitylinear term rewriting systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 4043235
• Reachability in conditional term rewriting systems
• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems
• Reachability and confluence are undecidable for flat term rewriting systems
• Algorithms and reductions for rewriting problems. II.

This page was built for publication: Ground reachability and joinability in linear term rewriting systems are fixed parameter tractable with respect to depth

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