The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
From MaRDI portal
Publication:4013403
DOI10.1007/BF01213858zbMATH Open0780.68080MaRDI QIDQ4013403FDOQ4013403
Authors: Friedrich Otto 
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
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
- Title not available (Why is that?)
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Presentations of groups and monoids
- Confluent and Other Types of Thue Systems
- Using string-rewriting for solving the word problem for finitely presented groups
- Testing for the Church-Rosser property
- Decidable sentences of Church-Rosser congruences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Systems of reductions
- Thue systems as rewriting systems
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Special monoids and special Thue systems
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)
