We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
AC-KBO revisited.
- Authors
YAMADA, AKIHISA; WINKLER, SARAH; HIROKAWA, NAO; MIDDELDORP, AART
- Abstract
Equational theories that contain axioms expressing associativity and commutativity (AC) of certain operators are ubiquitous. Theorem proving methods in such theories rely on well-founded orders that are compatible with the AC axioms. In this paper, we consider various definitions of AC-compatible Knuth-Bendix orders. The orders of Steinbach and of Korovin and Voronkov are revisited. The former is enhanced to a more powerful version, and we modify the latter to amend its lack of monotonicity on non-ground terms. We further present new complexity results. An extension reflecting the recent proposal of subterm coefficients in standard Knuth-Bendix orders is also given. The various orders are compared on problems in termination and completion.
- Subjects
VARIETIES (Universal algebra); AXIOMS; UBIQUITOUS computing; REWRITING systems (Computer science); ASSOCIATIVITY (Propositional logic)
- Publication
Theory & Practice of Logic Programming, 2016, Vol 16, Issue 2, p163
- ISSN
1471-0684
- Publication type
Article
- DOI
10.1017/S1471068415000083