Weakly Regular Relations and Applications

Sebastien Limet, Pierre Rety, and Helmut Seidl

Abstract:
A new class of tree-tuple languages is introduced:
the weakly regular relations.
It is an extension of the regular case (regular relations) and
a restriction of tree-tuple synchronized languages, that has
all usual nice properties, except closure by complement. 
Two applications are presented: to unification modulo a rewrite system,
and to one-step rewriting.