Complexity of certain decision problems about congruential languages
type: Item
instance of: scholarly article
title: Complexity of certain decision problems about congruential languages
zbMATH Open document ID: 0607.68055
DOI: 10.1016/0022-0000(85)90051-0
author: Heinrich Rolletschek
author: Paliath Narendran
author: Colm P. O'Dunlaing
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: In the paper certain decision problems about congruence classes defined by Church-Rosser Thue systems and commutative Thue systems (i.e. rewriting systems over free commutative monoids) are studied. Among other things, it is shown that the question of whether every congruence class defined by a Church-Rosser Thue system is finite, is complete for \(\Pi_ 2\) (a refinement of Jantzen and Monien's construction) while similar question about commutative Thue systems is tractable (an application of Khachian's algorithm).
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D03
zbMATH DE Number: 3982539
zbMATH Keywords: congruential language
zbMATH Keywords: congruence classes
zbMATH Keywords: Church-Rosser Thue systems
zbMATH Keywords: commutative Thue systems
zbMATH Keywords: rewriting systems
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90051-0
OpenAlex ID: W2058954424
cites work: Confluent and Other Types of Thue Systems
cites work: Q4152749
cites work: Thue congruences and the Church-Rosser property
cites work: Q3247126
cites work: Strong Computability and Variants of the Uniform Halting Problem
cites work: The undecidability of the Turing machine immortality problem
cites work: Q3862379
cites work: Parallel program schemata
cites work: Q5585020
cites work: The Church-Rosser property and special Thue systems
cites work: Infinite regular Thue systems
cites work: Q4739657
cites work: Recursive Unsolvability of a problem of Thue
cites work: The covering and boundedness problems for vector addition systems
cites work: Q5573961
description: scientific article; zbMATH DE number 3982539