Evelyne Contejean, Benjamin Monate
LRI, Universite Paris-Sud, France
CiME2 is intented to be a toolkit, which contains nowadays the following features:
The ordered completion of term rewriting systems will be used during
the competion to attempt to solve unification problems, that is
problems in the UEQ division.
- An interactive toplevel to allow naming of objects and call to
- Solving Diophantine constraints over finite intervals
- Solving Presburger constraints
- String Rewriting Systems, KB completion.
- Parameterized String Rewriting Systems confluence checking
- Term Rewriting Systems, possibly with commutative or
associative-commutative symbols, KB or ordered completion.
- Termination of TRSs using standard or dependency pairs criteria,
automatic generation of termination orderings based on polynomial
interpretations, including weak orderings for dependency pairs
CiME2 is fully written in Objective CAML, a functional
language of the ML family developed in the CRISTAL project at INRIA Rocquencourt.
CiME2 is available at http://cime.lri.fr/
as binaries for SPARC workstations running Solaris (at least version
2.6) and for pentium PCs running Linux, and its sources are
available by read-only anynomous CVS.
There are two distinct kinds of strategies to perform completion:
- the first one is, given an equation, how to choose its orientation
when it becomes a rule? The choice is made thanks an
ordering which has usually to be provided by the user.
During the competition, this ordering is arbitrarily fixed
to be an RPO ordering based on a precedence where the
symbols are ordered according to their arities.
- the second one is which inference rule has to be applied to the
system, among orienting an equation into a rule and
computing critical pairs. Each of these choices is given
a weight, and the lowest weighted choice is made. The weight
depends on the size of the involved equations/rules and
on how "old" they are. Some tuning may occur at this
point by choosing the ratio between the coefficients for
the size and the age. During the competition, this ratio
will be fixed.
Expected Competition Performance
This will be the first participation of CiME2 to CASC, in the UEQ
- Contejean Evelyne, Marché Claude, Monate Benjamin, Urbain Xavier (2000),
Cime version 2,
Prerelease available at http://cime.lri.fr/
- Contejean Evelyne, Marché Claude (July 1996),
CiME: Completion Modulo E,
International Conference on Rewriting Techniques and Applications
(New Brunswick, NJ, USA),
Lecture Notes in Computer Science 1103,
Acknowledgments: Claude Marché and Xavier Urbain contributed to the development of CiME2.