Congruence Closure Modulo Groups
Author:
Open Access
- 28 February 2025
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Abstract
This paper presents a new framework for constructing congruence closure of a finite set of ground equations over uninterpreted symbols and interpreted symbols for the group axioms. In this framework, ground equations are flattened into certain forms by introducing new constants, and a completion procedure is performed on ground flat equations. The proposed completion procedure uses equational inference rules and constructs a ground convergent rewrite system for congruence closure with such interpreted symbols. If the completion procedure terminates, then it yields a decision procedure for the word problem for a finite set of ground equations with respect to the group axioms. This paper also provides a sufficient terminating condition of the completion procedure for constructing a ground convergent rewrite system from ground flat equations containing interpreted symbols for the group axioms. In addition, this paper presents a new method for constructing congruence closure of a finite set of ground equations containing interpreted symbols for the semigroup, monoid, and the multiple disjoint sets of group axioms, respectively, using the proposed framework.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Deciding the Word Problem for Ground Identities with Commutative and Extensional Symbols2020
- Finding a Finite Group Presentation Using Rewriting1998
- Shostak's congruence closure as completion1997
- Normalized Rewriting: an Alternative to Rewriting modulo a Set of EquationsJournal of Symbolic Computation, 1996
- Theorem proving modulo associativity1996
- Effective theorem proving for hardware verification1995
- String-Rewriting Systems1993
- Canonical Equational Proofs1991
- An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebrasLecture Notes in Computer Science, 1985
- Canonical Forms in Finitely Presented Algebras1984