Geodesic
SOUR graphs for efficient completion
Discrete mathematics & theoretical computer science, Tome 2 (1998).

Voir la notice de l'article provenant de la source Episciences

We introduce a data structure called \emphSOUR graphs and present an efficient Knuth-Bendix completion procedure based on it. \emphSOUR graphs allow for a maximal structure sharing of terms in rewriting systems. The term representation is a dag representation, except that edges are labelled with equational constraints and variable renamings. The rewrite rules correspond to rewrite edges, the unification problems to unification edges. The Critical Pair and Simplification inferences are recognized as patterns in the graph and are performed as local graph transformations. Our algorithm avoids duplicating term structure while performing inferences, which causes exponential behavior in the standard procedure. This approach gives a basis to design other completion algorithms, such as goal-oriented completion, concurrent completion and group completion procedures. 
@article{DMTCS_1998_2_a0,
     author = {Lynch, Christopher and Strogova, Polina},
     title = {SOUR graphs for efficient completion},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {2},
     year = {1998},
     doi = {10.46298/dmtcs.247},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.247/}
}
TY  - JOUR
AU  - Lynch, Christopher
AU  - Strogova, Polina
TI  - SOUR graphs for efficient completion
JO  - Discrete mathematics & theoretical computer science
PY  - 1998
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.247/
DO  - 10.46298/dmtcs.247
LA  - en
ID  - DMTCS_1998_2_a0
ER  - 
%0 Journal Article
%A Lynch, Christopher
%A Strogova, Polina
%T SOUR graphs for efficient completion
%J Discrete mathematics & theoretical computer science
%D 1998
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.247/
%R 10.46298/dmtcs.247
%G en
%F DMTCS_1998_2_a0
Lynch, Christopher; Strogova, Polina. SOUR graphs for efficient completion. Discrete mathematics & theoretical computer science, Tome 2 (1998). doi : 10.46298/dmtcs.247. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.247/

Cité par Sources :