On deciding the confluence of a finite string-rewriting system on a given congruence class
From MaRDI portal
(Redirected from Publication:1102946)
Recommendations
- Some results on Green's relations for monoids presented by monadic string-rewriting systems
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- scientific article; zbMATH DE number 789389
- scientific article; zbMATH DE number 177883
- On weakly confluent monadic string-rewriting systems
- Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
- Some properties of finite special string-rewriting systems
- The word matching problem is undecidable for finite special string-rewriting systems that are confluent
- Reachability in Unions of Commutative Rewriting Systems Is Decidable
Cites work
- scientific article; zbMATH DE number 3836321 (Why is no real title available?)
- scientific article; zbMATH DE number 3811849 (Why is no real title available?)
- scientific article; zbMATH DE number 3898258 (Why is no real title available?)
- scientific article; zbMATH DE number 43246 (Why is no real title available?)
- scientific article; zbMATH DE number 3563392 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- A note on a special one-rule semi-Thue system
- A note on special thue systems with a single defining relation
- A note on thue systems with a single defining relation
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Cancellativity in finitely presented semigroups
- Complexity of certain decision problems about congruential languages
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- Finite canonical rewriting systems for congruences generated by concurrency relations
- Finite complete rewriting systems and the complexity of word problem
- Infinite regular Thue systems
- Monadic Thue systems
- On Proving Uniform Termination and Restricted Termination of Rewriting Systems
- On theories with a combinatorial definition of 'equivalence'
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Testing for the Church-Rosser property
- The equation \(a_ M=b^ Nc^ P\) in a free group
- The equivalence problem for deterministic finite-turn pushdown automata
Cited in
(24)- Algorithms and reductions for rewriting problems
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Using string-rewriting for solving the word problem for finitely presented groups
- scientific article; zbMATH DE number 177883 (Why is no real title available?)
- About the descriptive power of certain classes of finite string-rewriting systems
- Some decision problems about controlled rewriting systems
- Infinite Families of Finite String Rewriting Systems and Their Confluence
- Lambda-confluence for context rewriting systems
- Some properties of finite special string-rewriting systems
- On weakly confluent monadic string-rewriting systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- On Simon's congruence closure of a string
- Complexity of certain decision problems about congruential languages
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- The pre-NTS property is undecidable for context-free grammars
- The Knuth-Bendix algorithm and the conjugacy problem in monoids.
- It is decidable whether a monadic thue system is canonical over a regular set
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Restrictions of congruences generated by finite canonical string-rewriting systems
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Reducing the gradedness problem of string rewriting systems to a termination problem
- Lambda-confluence is undecidable for clearing restarting automata
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
This page was built for publication: On deciding the confluence of a finite string-rewriting system on a given congruence class
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102946)
