Systems of reductions

zbMath0636.68027MaRDI QIDQ1098283

S. Kemmerich, Benjamin Benninghofen, Michael M. Richter

Publication date: 1987

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

word problem; completion; term-rewriting systems; reductions; finite termination property; finitely presented monoids; Thue systems; Church-Rosser property; Noetherian systems; confluency; Knuth- Bendix algorithm; undecidable problems in general algebras

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q65: Abstract data types; algebraic specification

03B25: Decidability of theories and sets of sentences

20M35: Semigroups in automata theory, linguistics, etc.

68-02: Research exposition (monographs, survey articles) pertaining to computer science

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

08A50: Word problems (aspects of algebraic structures)

Related Items

Finite complete rewriting systems for groups, ON THE ZAPPA-SZÉP PRODUCT, A finitely presented monoid which has solvable word problem but has no regular complete presentation, 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, A complete rewriting system for a monoid of tree transformation classes, It is undecidable whether a finite special string-rewriting system presents a group, When is an extension of a specification consistent? Decidable and undecidable cases, The use of Knuth-Bendix methods to solve the word problem in automatic groups, New methods for using Cayley graphs in interconnection networks, Deciding embeddability of partial groupoids into semigroups, Buchberger's algorithm: The term rewriter's point of view, Free products with amalgamation of monoids, An upper bound on the derivational complexity of Knuth-Bendix orderings., Infinite complete group presentations, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems