A finite Thue system with decidable word problem and without equivalent finite canonical system
type: Item
instance of: scholarly article
title: A finite Thue system with decidable word problem and without equivalent finite canonical system
zbMATH Open document ID: 0588.03023
DOI: 10.1016/0304-3975(85)90023-4
author: Deepak Kapur
author: Paliath Narendran
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: It is shown that the following single axiom Thue system \(T=\{aba\leftrightarrow bab\}\) has no equivalent finite canonical (i.e. Noetherian and confluent) semi-Thue system. However, an equivalent finite canonical system for this Thue system can be obtained if new symbols are introduced in the representation.
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 3943794
zbMATH Keywords: Church-Rosser property
zbMATH Keywords: term rewriting systems
zbMATH Keywords: single axiom Thue system
zbMATH Keywords: semi-Thue system
reviewed by: Stasys Jukna
describes a project that uses: REVE
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90023-4
OpenAlex ID: W2064672594
cites work: Confluent and Other Types of Thue Systems
cites work: On Proving Uniform Termination and Restricted Termination of Rewriting Systems
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q3346296
cites work: Q3319767
cites work: Q5581665
cites work: The Church-Rosser property and special Thue systems
cites work: Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
description: scientific article; zbMATH DE number 3943794