On two problems related to cancellativity
type: Item
instance of: scholarly article
title: On two problems related to cancellativity
zbMATH Open document ID: 0584.20046
DOI: 10.1007/BF02573208
author: Friedrich Otto
published in: Semigroup Forum
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/134818
review text: The following two decision problems, that are related to the properties of right-cancellativity and left-cancellativity, respectively, of the monoid \({\mathfrak M}_ T\) defined by the presentation (\(\Sigma\) ;T), are investigated: Instance: A finite presentation (\(\Sigma\) ;T), and two words \(u,v\in \Sigma^*\). (1) Question: Does there exist a word \(x\in \Sigma^*\) such that \(ux\leftrightarrow^*_ Tvx?\) (2) Question: Does there exist a word \(x\in \Sigma^*\) such that \(xu\leftrightarrow^*_ Txv?\) It is shown that these problems are undecidable in general. In fact, they remain undecidable, even when they are restricted to presentations involving finite Church-Rosser Thue systems. On the other hand, when they are restricted to finite presentations involving monadic Church-Rosser Thue systems, then these two problems are decidable in polynomial space.
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 3935327
zbMATH Keywords: decision problems
zbMATH Keywords: right-cancellativity
zbMATH Keywords: left-cancellativity
zbMATH Keywords: finite Church-Rosser Thue systems
zbMATH Keywords: finite presentations
MaRDI profile type: Publication
cites work: Confluent and Other Types of Thue Systems
cites work: Decidable sentences of Church-Rosser congruences
cites work: Thue congruences and the Church-Rosser property
cites work: Q4198075
cites work: Q3862379
cites work: Q3853827
cites work: Cancellativity in finitely presented semigroups
cites work: Complexity results on the conjugacy problem for monoids
cites work: The problems of cyclic equality and conjugacy for finite complete rewriting systems
cites work: The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
cites work: Conjugacy in monoids with a special Church-Rosser presentation is decidable
cites work: Some undecidability results for non-monadic Church-Rosser Thue systems
cites work: Q3718694
cites work: Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
cites work: Church–Rosser Thue Systems that Present Free Monoids
cites work: On deciding whether a monoid is a free monoid or is a group
cites work: Relationships between nondeterministic and deterministic tape complexities
description: scientific article; zbMATH DE number 3935327