n-level rewriting systems
type: Item
instance of: scholarly article
title: n-level rewriting systems
zbMATH Open document ID: 0606.68025
DOI: 10.1016/0304-3975(85)90160-4
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: It is well known that a monoid which is presented by a finite complete rewriting system has a decidable word problem. On the other hand, the problem whether each finitely presentable recursive monoid can be presented by a finite complete rewriting system is still unsolved. It is conjectured that this is not always possible. By generalizing the rewriting systems to the n-level rewriting systems it is shown that exactly the finitely presentable recursive monoids can be presented by finite complete 2-level rewriting systems.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3980470
zbMATH Keywords: finitely presentable recursive monoids
zbMATH Keywords: finite complete 2-level rewriting systems
author: Günther Bauer
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90160-4
OpenAlex ID: W2121691985
cites work: Finite complete rewriting systems and the complexity of word problem
cites work: Confluent and Other Types of Thue Systems
cites work: Q3677188
cites work: Algebraic simplification
cites work: Q3247126
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: A note on a special one-rule semi-Thue system
cites work: A finite Thue system with decidable word problem and without equivalent finite canonical system
cites work: Q5581665
Recommended article: Rewriting systems over nested data words
Recommended article: Higher-order rewrite systems and their confluence
Recommended article: Q4938608
Recommended article: Q3982097
Recommended article: Natural Rewriting for General Term Rewriting Systems
Recommended article: A higher-order implementation of rewriting
Recommended article: Complete involutive rewriting systems
Recommended article: Rewriting P systems: improved hierarchies
Recommended article: An abstract formulation for rewrite systems
description: scientific article; zbMATH DE number 3980470