The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
From MaRDI portal
Publication:4013403
Recommendations
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Deciding confluence of certain term rewriting systems in polynomial time
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 42096 (Why is no real title available?)
- scientific article; zbMATH DE number 176741 (Why is no real title available?)
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Confluent and Other Types of Thue Systems
- Decidable sentences of Church-Rosser congruences
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Presentations of groups and monoids
- Special monoids and special Thue systems
- Systems of reductions
- Testing for the Church-Rosser property
- Thue systems as rewriting systems
- Using string-rewriting for solving the word problem for finitely presented groups
Cited in
(10)- On weakly confluent monadic string-rewriting systems
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Some properties of finite special string-rewriting systems
- Lambda-confluence for context rewriting systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Restrictions of congruences generated by finite canonical string-rewriting systems
This page was built for publication: The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4013403)
