Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
The Finite Variant Property: How to Get Rid of Some Algebraic Properties
verfasst von : Hubert Comon-Lundh, Stéphanie Delaune
Erschienen in: Term Rewriting and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the following problem: Given a term
t
, a rewrite system
$\cal R$
, a finite set of equations
E
′ such that
$\cal R$
is
E
′-convergent, compute finitely many instances of
t
:
t
1
,...,
t
n
such that, for every substitution
σ
, there is an index
i
and a substitution
θ
such that
$t\sigma\mathord\downarrow =_{E'} t_i\theta$
(where
$t\sigma\mathord\downarrow$
is the normal form of
tσ
w.r.t.
$\to_{E'\mathord{\setminus}\mathcal R}$
).
The goal of this paper is to give equivalent (resp. sufficient) conditions for the finite variant property and to systematically investigate this property for equational theories, which are relevant to security protocols verification. For instance, we prove that the finite variant property holds for Abelian Groups, and a theory of modular exponentiation and does not hold for the theory
ACUNh
(Associativity, Commutativity, Unit, Nilpotence, homomorphism).