Some undecidability results for non-monadic Church-Rosser Thue systems
type: Item
instance of: scholarly article
title: Some undecidability results for non-monadic Church-Rosser Thue systems
zbMATH Open document ID: 0563.03019
DOI: 10.1016/0304-3975(84)90090-2
author: Friedrich Otto
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: A linear sentence on the alphabet A is a string of the form \(\forall u_ 1...\forall u_ m\exists v_ 1...\exists v_ nF\) or \(\exists v_ 1...\exists v_ n\forall u_ 1...\forall u_ mF\) where \(u_ i\in V_ u\), the set of universal variables, \(v_ i\in V_ E\), the set of existential variables and F has one of the forms \(x\sim y\) (x,y\(\in (A\cup V_ u)^*\cup (A\cup V_ E)^*)\), \(F_ 1\wedge F_ 2\), or \(F_ 1\vee F_ 2\) and no variable occurs twice in F. A Thue system on A defines an interpretation of the linear sentences on A by taking the congruence relation for \(\sim\). It is known that there is an algorithm which decides whether a linear sentence on A is true or not under the interpretation given by a monadic finite Thue system on A that is Church- Rosser. In the paper the case of non-monadic finite Thue systems that are Church-Rosser is considered. The main result claims that it is undecidable whether a linear sentence on A is true or not under the interpretation given by a non-monadic finite Thue system on A that is Church-Rosser. Some problems that are decidable for monadic Church-Rosser Thue systems but that are undecidable for non-monadic Church-Rosser Thue systems are presented.
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3896913
zbMATH Keywords: linear sentence
zbMATH Keywords: Thue system
reviewed by: Dorel Lucanu
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90090-2
OpenAlex ID: W1998439085
cites work: Confluent and Other Types of Thue Systems
cites work: When is a monoid a group? The Church-Rosser case is tractable
cites work: Decidable sentences of Church-Rosser congruences
cites work: Q3939790
cites work: Monadic Thue systems
cites work: FINITELY PRESENTED GROUP WHOSE WORD PROBLEM HAS THE SAME DEGREE AS THAT OF AN ARBITRARILY GIVEN THUE SYSTEM (AN APPLICATION OF METHODS OF BRITTON)
cites work: Q5586401
cites work: Q5824357
cites work: Strong Computability and Variants of the Uniform Halting Problem
cites work: Q5592246
cites work: Q3676128
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q3853827
cites work: The honest subrecursive classes are a lattice
cites work: Infinite regular Thue systems
cites work: Machine Configuration and Word Problems of Given Degree of Unsolvability
cites work: Q4044553
description: scientific article; zbMATH DE number 3896913