New decision algorithms for finitely presented commutative semigroups
DOI10.1016/0898-1221(81)90115-2zbMATH Open0449.20059OpenAlexW2099954293MaRDI QIDQ1147232FDOQ1147232
Authors: 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
decision algorithmsuniform word problemChurch-Rosser term rewriting systemcompletion procedure for commutative associative term rewriting systemsfinitely presented commutative semigroups
Artificial intelligence (68T99) Commutative semigroups (20M14) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- On theories with a combinatorial definition of 'equivalence'
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Constructions in Algebra
- Title not available (Why is that?)
- New decision algorithms for finitely presented commutative semigroups
- Some algorithmic problems for finitely defined commutative semigroups
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Isomorphism Problem for Some Classes of Multiplicative Systems
- A Decision Problem for Transformations of Trees
Cited In (37)
- Hilbert's tenth problem is of unification type zero
- Modularity and Combination of Associative Commutative Congruence Closure Algorithms enriched with Semantic Properties
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- On equational theories, unification, and (un)decidability
- Conditional congruence closure over uninterpreted and interpreted symbols
- Completion for rewriting modulo a congruence
- Paramodulated connection graphs
- Any ground associative-commutative theory has a finite canonical system
- Complete semi-Thue systems for abelian groups
- Automatic inductive theorem proving using Prolog
- Complexity of matching problems
- Orderings for term-rewriting systems
- Title not available (Why is that?)
- Proofs by induction in equational theories with constructors
- Refutational theorem proving using term-rewriting systems
- Buchberger's algorithm: The term rewriter's point of view
- Unification in a combination of arbitrary disjoint equational theories
- A complete proof of correctness of the Knuth-Bendix completion algorithm
- Termination of rewriting
- New decision algorithms for finitely presented commutative semigroups
- A Noetherian and confluent rewrite system for idempotent semigroups
- Termination and completion modulo associativity, commutativity and identity
- Efficient solution of the word problem in slim varieties
- Identities common to four Abelian group operations with zero
- Complete sets of unifiers and matchers in equational theories
- Unification in permutative equational theories is undecidable
- Equational completion in order-sorted algebras
- Word problems over traces which are solvable in linear time
- Commutative monoids have complete presentations by free (non-commutative) monoids
- Reductions in tree replacement systems
- History and basic features of the critical-pair/completion procedure
- Computing a Gröbner basis of a polynomial ideal over a Euclidean domain
- On the Knuth-Bendix completion for concurrent processes
- Generalized Gröbner bases: Theory and applications. A condensation
- Residual finiteness in permutation varieties of semigroups
- Cancellativity in finitely presented semigroups
- Free products with amalgamation of monoids
This page was built for publication: New decision algorithms for finitely presented commutative semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1147232)
