Completing a finite special string-rewriting system on the congruence class of the empty word

DOI10.1007/BF01614148zbMath0746.68048MaRDI QIDQ1191634

Friedrich Otto

Publication date: 27 September 1992

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

completion procedure\(e\)-confluencemonoid-presentationstring- rewriting systems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (3)

The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ The word problem for one-relation monoids: a survey ⋮ On weakly confluent monadic string-rewriting systems

Cites Work

• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• About the descriptive power of certain classes of finite string-rewriting systems
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Conjugacy in special monoids
• It is undecidable whether a finite special string-rewriting system presents a group
• The Knuth-Bendix Completion Procedure and Thue Systems

This page was built for publication: Completing a finite special string-rewriting system on the congruence class of the empty word