Decision problems for finite special string-rewriting systems that are confluent on some congruence class
type: Item
instance of: scholarly article
title: Decision problems for finite special string-rewriting systems that are confluent on some congruence class
zbMATH Open document ID: 0699.20047
DOI: 10.1007/BF01178585
author: Louxin Zhang
author: Friedrich Otto
published in: Acta Informatica
publication date: 1991-01-01T00:00:00Z
review text: The class of decision problems for which finite, special string-rewriting systems that are confluent on some congruence class effectively provide algorithms is compared to the class of decision problems for which finite, monadic, and confluent string-rewriting systems effectively yield algorithms. Among the decision problems solved are the word problem, the power problem, the left- and right-divisibility problems, the finiteness problem, the group problem, the problem of torsion-freeness, the inclusion problem for submonoids generated by regular sets, and the generalized word problem. In particular, it is shown that the technique of linear sentences of \textit{R. Book} [Theor. Comput. Sci. 24, 301-312 (1983; Zbl 0525.68015)] applies to finite, special string-rewriting systems that are confluent on some congruence class.
reviewed by: O. Fekete
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 03D05
zbMATH DE Number: 4146268
zbMATH Keywords: decision problems
zbMATH Keywords: finite, special string-rewriting systems
zbMATH Keywords: congruence class
zbMATH Keywords: algorithms
zbMATH Keywords: word problem
zbMATH Keywords: power problem
zbMATH Keywords: divisibility problems
zbMATH Keywords: finiteness problem
zbMATH Keywords: group problem
zbMATH Keywords: inclusion problem
zbMATH Keywords: regular sets
zbMATH Keywords: generalized word problem
MaRDI profile type: Publication
cites work: Systems of reductions
cites work: Q3714479
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: Thue systems as rewriting systems
cites work: Thue congruences and the Church-Rosser property
cites work: Testing for the Church-Rosser property
cites work: Presentations of groups and monoids
cites work: Q3862379
cites work: On the equivalence, containment, and covering problems for the regular and context-free languages
cites work: A note on a special one-rule semi-Thue system
cites work: Q3994922
cites work: An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
cites work: A finite Thue system with decidable word problem and without equivalent finite canonical system
cites work: Q5581665
cites work: Fast Pattern Matching in Strings
cites work: Q3853827
cites work: Q4145882
cites work: Using string-rewriting for solving the word problem for finitely presented groups
cites work: About the descriptive power of certain classes of finite string-rewriting systems
cites work: Special monoids and special Thue systems
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: Elements of finite order for finite weight-reducing and confluent Thue systems
cites work: Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems
cites work: On theories with a combinatorial definition of 'equivalence'
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: Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
cites work: On deciding whether a monoid is a free monoid or is a group
cites work: On two problems related to cancellativity
cites work: On deciding the confluence of a finite string-rewriting system on a given congruence class
cites work: An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group
cites work: Conjugacy in special monoids
full work available at URL: https://doi.org/10.1007/bf01178585
OpenAlex ID: W2076828696
description: scientific article; zbMATH DE number 4146268