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-4zbMATH Open0588.03023OpenAlexW2064672594MaRDI QIDQ1073016FDOQ1073016
Authors: 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
Recommendations
Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40)
Cites Work
- Title not available (Why is that?)
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Confluent and Other Types of Thue Systems
- Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
- On Proving Uniform Termination and Restricted Termination of Rewriting Systems
- The Church-Rosser property and special Thue systems
Cited In (45)
- The undecidability of the preperfectness of Thue systems
- Complete rewriting systems and homology of monoid algebras
- Title not available (Why is that?)
- On weakly confluent monadic string-rewriting systems
- Thue systems as rewriting systems
- A decidable word problem without equivalent canonical term rewriting system
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Any ground associative-commutative theory has a finite canonical system
- Complete semi-Thue systems for abelian groups
- Finite derivation type for semi-direct products of monoids
- Schematization of infinite sets of rewrite rules generated by divergent completion processes
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- On ground-confluence of term rewriting systems
- On sufficient-completeness and related properties of term rewriting systems
- Using string-rewriting for solving the word problem for finitely presented groups
- Could orders be captured by term rewriting systems?
- Title not available (Why is that?)
- Church-Rooser property and homology of monoids
- Confluence of one-rule Thue systems
- Convergent presentations and polygraphic resolutions of associative algebras
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Higher-dimensional normalisation strategies for acyclicity
- Finite derivation type for Rees matrix semigroups
- On reduced thue systems
- Finite complete rewriting systems and the complexity of word problem
- Algebra and geometry of rewriting
- Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings
- Syntactical methods for braids of three strands
- About the descriptive power of certain classes of finite string-rewriting systems
- Commutative monoids have complete presentations by free (non-commutative) monoids
- Finite canonical rewriting systems for congruences generated by concurrency relations
- Almost all one-rule Thue systems have decidable word problems
- n-level rewriting systems
- Pseudo-natural algorithms for finitely generated presentations of monoids and groups
- Rewrite systems for varieties of semigroups
- Title not available (Why is that?)
- Coherent presentations of Artin monoids
- A result on braids via the investigation of a rewriting system.
- It is decidable whether a monadic thue system is canonical over a regular set
- Restrictions of congruences generated by finite canonical string-rewriting systems
- Conditional semi-Thue systems for presenting monoids
- Polygraphs of finite derivation type
- The Thue problem and logical specifications of derivation in formal systems
- A finitely presented monoid which has solvable word problem but has no regular complete presentation
- Reduction operators and completion of rewriting systems
Uses Software
This page was built for publication: A finite Thue system with decidable word problem and without equivalent finite canonical system
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1073016)
