Elements of finite order for finite weight-reducing and confluent Thue systems
type: Item
instance of: scholarly article
title: Elements of finite order for finite weight-reducing and confluent Thue systems
zbMATH Open document ID: 0673.68025
author: Paliath Narendran
author: Friedrich Otto
published in: Acta Informatica
publication date: 1988-01-01T00:00:00Z
review text: Let T be a finite, weight-reducing, and confluent Thue system, and let \(M_ T\) be the monoid which it represents. The following properties are shown to be decidable in polynomial time: (1) \(M_ T\) is a group; (2) \(M_ T\) contains an idempotent element different from the identity element; (3) \(M_ T\) contains an element of finite order which is different from the identity element; (4) \(M_ T\) is a free group. Moreover, the proofs imply the following: if \(M_ T\) contains an idempotent or an element of finite order different from the identity element or an element which is not a unit then such an element can be constructed in polynomial time.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4102484
zbMATH Keywords: finite weight-reducing
zbMATH Keywords: confluent Thue systems
zbMATH Keywords: rewriting systems
MaRDI profile type: Publication
Recommended article: Q3153443
Recommended article: Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
Recommended article: On finite commutative Thue systems
Recommended article: On reduced thue systems
Recommended article: Multiplicative orders of elements in Conway towers of finite fields
Recommended article: Elements of finite order in \(\beta \mathbb{N}\)
Recommended article: Q3825221
Recommended article: On the regular equivalence problem for regular Thue systems
Recommended article: Q3717308
Recommended article: Elements of large order on varieties over prime finite fields
description: scientific article; zbMATH DE number 4102484