New decision algorithms for finitely presented commutative semigroups

DOI10.1016/0898-1221(81)90115-2zbMath0449.20059OpenAlexW2099954293MaRDI QIDQ1147232

A. M. Ballantyne, Dallas Lankford

Publication date: 1980

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(81)90115-2

zbMATH Keywords

decision algorithmsuniform word problemChurch-Rosser term rewriting systemcompletion procedure for commutative associative term rewriting systemsfinitely presented commutative semigroups

Mathematics Subject Classification ID

Commutative semigroups (20M14) Free semigroups, generators and relations, word problems (20M05) Artificial intelligence (68T99) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (37)

Reductions in tree replacement systems ⋮ Commutative monoids have complete presentations by free (non-commutative) monoids ⋮ Complete semi-Thue systems for abelian groups ⋮ Generalized Gröbner bases: Theory and applications. A condensation ⋮ Buchberger's algorithm: The term rewriter's point of view ⋮ Termination of rewriting ⋮ Complexity of matching problems ⋮ History and basic features of the critical-pair/completion procedure ⋮ Automatic inductive theorem proving using Prolog ⋮ Computing a Gröbner basis of a polynomial ideal over a Euclidean domain ⋮ Orderings for term-rewriting systems ⋮ Unnamed Item ⋮ Free products with amalgamation of monoids ⋮ Modularity and Combination of Associative Commutative Congruence Closure Algorithms enriched with Semantic Properties ⋮ New decision algorithms for finitely presented commutative semigroups ⋮ A complete proof of correctness of the Knuth-Bendix completion algorithm ⋮ Equational completion in order-sorted algebras ⋮ Word problems over traces which are solvable in linear time ⋮ A Noetherian and confluent rewrite system for idempotent semigroups ⋮ Conditional congruence closure over uninterpreted and interpreted symbols ⋮ Termination and completion modulo associativity, commutativity and identity ⋮ Hilbert's tenth problem is of unification type zero ⋮ Unification in a combination of arbitrary disjoint equational theories ⋮ Any ground associative-commutative theory has a finite canonical system ⋮ Paramodulated connection graphs ⋮ Completion for rewriting modulo a congruence ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ On deciding confluence of finite string-rewriting systems modulo partial commutativity ⋮ Complete sets of unifiers and matchers in equational theories ⋮ Cancellativity in finitely presented semigroups ⋮ On equational theories, unification, and (un)decidability ⋮ Unification in permutative equational theories is undecidable ⋮ Proofs by induction in equational theories with constructors ⋮ Residual finiteness in permutation varieties of semigroups ⋮ Refutational theorem proving using term-rewriting systems ⋮ Efficient solution of the word problem in slim varieties ⋮ Identities common to four Abelian group operations with zero

Cites Work

• New decision algorithms for finitely presented commutative semigroups
• Some algorithmic problems for finitely defined commutative semigroups
• On theories with a combinatorial definition of 'equivalence'
• Constructions in Algebra
• The Isomorphism Problem for Some Classes of Multiplicative Systems
• A Decision Problem for Transformations of Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New decision algorithms for finitely presented commutative semigroups