Algorithms and reductions for rewriting problems
From MaRDI portal
confluencedecidabilitydecision problemsequational theorypolynomial-time reductionsrewrite systemsword problem
Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Grammars and rewriting systems (68Q42)
Recommendations
- Algorithms and reductions for rewriting problems. II.
- Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
- scientific article; zbMATH DE number 1418332
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- On deciding the confluence of a finite string-rewriting system on a given congruence class
Cited in
(21)- Reachability and confluence are undecidable for flat term rewriting systems
- Systems of reductions
- Computing circumscription revisited: A reduction algorithm
- Reduction algorithms for solving large systems of logical equations
- Algorithms and reductions for rewriting problems. II.
- Confluence problems for trace rewriting systems
- Deciding confluence of certain term rewriting systems in polynomial time
- Component-Based Security Policy Design with Colored Petri Nets
- Reducing the gradedness problem of string rewriting systems to a termination problem
- Reachability in Unions of Commutative Rewriting Systems Is Decidable
- Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
- scientific article; zbMATH DE number 54148 (Why is no real title available?)
- Deciding confluence and normal form properties of ground term rewrite systems efficiently
- The word matching problem is undecidable for finite special string-rewriting systems that are confluent
- Transformation of algorithms written in the form of composition schemes
- New Undecidability Results for Properties of Term Rewrite Systems
- Uniqueness of normal forms for shallow term rewrite systems
- On Reduct Construction Algorithms
- A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
- A fast algorithm for generating reduced ground rewriting systems from a set of ground equations
- The reachability and related decision problems for monadic and semi-constructor TRSs
This page was built for publication: Algorithms and reductions for rewriting problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2730723)
