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

DOI10.4230/LIPICS.IPEC.2016.25zbMATH Open1398.68288OpenAlexW2593118042MaRDI QIDQ4634409FDOQ4634409

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/

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.

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)

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)