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 problemcompletionterm-rewriting systemsreductionsfinite termination propertyfinitely presented monoidsThue systemsChurch-Rosser propertyNoetherian systemsconfluencyKnuth- Bendix algorithmundecidable problems in general algebras

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Word problems (aspects of algebraic structures) (08A50)

Related Items

Semigroups satisfying x m+n = x n, Open problems in rewriting, Buchberger's algorithm: The term rewriter's point of view, Infinite complete group presentations, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems, Free products with amalgamation of monoids, Applying term rewriting methods to finite groups, An upper bound on the derivational complexity of Knuth-Bendix orderings., 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, A finitely presented monoid which has solvable word problem but has no regular complete presentation, The use of Knuth-Bendix methods to solve the word problem in automatic groups, New methods for using Cayley graphs in interconnection networks, Finite complete rewriting systems for groups, ON THE ZAPPA-SZÉP PRODUCT, On a graph connecting hyperbinary expansions, Deciding embeddability of partial groupoids into semigroups