A finite Thue system with decidable word problem and without equivalent finite canonical system
From MaRDI portal
Publication:1073016
DOI10.1016/0304-3975(85)90023-4zbMath0588.03023OpenAlexW2064672594MaRDI QIDQ1073016
Deepak Kapur, Paliath Narendran
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90023-4
Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items
On sufficient-completeness and related properties of term rewriting systems ⋮ Could orders be captured by term rewriting systems? ⋮ n-level rewriting systems ⋮ Commutative monoids have complete presentations by free (non-commutative) monoids ⋮ Complete semi-Thue systems for abelian groups ⋮ Finite derivation type for Rees matrix semigroups ⋮ Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ Thue systems as rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ Pseudo-natural algorithms for finitely generated presentations of monoids and groups ⋮ Church-Rooser property and homology of monoids ⋮ Reduction operators and completion of rewriting systems ⋮ Finite derivation type for semi-direct products of monoids ⋮ Conditional semi-Thue systems for presenting monoids ⋮ Confluence of one-rule Thue systems ⋮ Finite canonical rewriting systems for congruences generated by concurrency relations ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ On ground-confluence of term rewriting systems ⋮ Higher-dimensional normalisation strategies for acyclicity ⋮ Complete rewriting systems and homology of monoid algebras ⋮ A result on braids via the investigation of a rewriting system. ⋮ A decidable word problem without equivalent canonical term rewriting system ⋮ Algebra and geometry of rewriting ⋮ A finitely presented monoid which has solvable word problem but has no regular complete presentation ⋮ On weakly confluent monadic string-rewriting systems ⋮ Syntactical methods for braids of three strands ⋮ Convergent presentations and polygraphic resolutions of associative algebras ⋮ Using string-rewriting for solving the word problem for finitely presented groups ⋮ Any ground associative-commutative theory has a finite canonical system ⋮ Unnamed Item ⋮ Schematization of infinite sets of rewrite rules generated by divergent completion processes ⋮ Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings ⋮ Finite complete rewriting systems and the complexity of word problem ⋮ Polygraphs of finite derivation type ⋮ Coherent presentations of Artin monoids ⋮ Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
- The Church-Rosser property and special Thue systems
- On Proving Uniform Termination and Restricted Termination of Rewriting Systems
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
