On the regular equivalence problem for regular Thue systems
type: Item
instance of: scholarly article
title: On the regular equivalence problem for regular Thue systems
zbMATH Open document ID: 0609.68027
DOI: 10.1016/0304-3975(86)90121-0
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3986633
zbMATH Keywords: undecidability
zbMATH Keywords: preperfect Thue systems
zbMATH Keywords: decision procedure
zbMATH Keywords: almost- confluent Thue systems
author: Paliath Narendran
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90121-0
OpenAlex ID: W2075456171
cites work: Confluent and Other Types of Thue Systems
cites work: Homogeneous Thue systems and the Church-Rosser property
cites work: Monadic Thue systems
cites work: Q5592246
cites work: The Knuth-Bendix Completion Procedure and Thue Systems
cites work: Q3319767
cites work: The Church-Rosser property and special Thue systems
cites work: The undecidability of the preperfectness of Thue systems
cites work: Q4105657
cites work: Infinite regular Thue systems
cites work: Q3718694
cites work: Une généralisation des ensembles de Dyck
description: scientific article; zbMATH DE number 3986633