Almost all one-rule Thue systems have decidable word problems
type: Item
instance of: scholarly article
title: Almost all one-rule Thue systems have decidable word problems
zbMATH Open document ID: 0563.03020
DOI: 10.1016/0012-365X(84)90160-2
author: Ronald V. Book
author: Craig C. Squier
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A word \(w\in A^*\) has a border \(z\in A^*\) if there exist \(x,y\in A^*\) such that \(w=xz=zy\) and \(0<| x| <| w|\). A word is called unbordered if it has no border. It is shown that: (i) the word problem for a one-rule Thue system \(T=\{(u,v)\}\), with \(| u| >| v|\) and u unbordered, is decidable; and (ii) almost all words are unbordered. This together with the obvious decidability of the word problem for a one-rule Thue system \(T=\{(u,v)\}\) with \(| u| =| v|\) leads to the fact stated in the title of the paper.
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3896914
reviewed by: Stasys Jukna
MaRDI profile type: Publication
cites work: Q5602108
cites work: Confluent and Other Types of Thue Systems
cites work: Homogeneous Thue systems and the Church-Rosser property
cites work: Q3312417
Recommended article: A finite Thue system with decidable word problem and without equivalent finite canonical system
Recommended article: Decision problems for semi-Thue systems with a few rules
Recommended article: A decidable word problem without equivalent canonical term rewriting system
Recommended article: On the termination problem for one-rule semi-Thue system
Recommended article: Word problem for deterministic and reversible semi-Thue systems
Recommended article: On a connection between the word problem and decidability of the equational theory
Recommended article: Q2723899
Recommended article: A note on a special one-rule semi-Thue system
Recommended article: The word problem for Smullyan's lark combinator is decidable
Recommended article: A finitely axiomatizable undecidable equational theory with recursively solvable word problems
description: scientific article; zbMATH DE number 3896914