Eric Badouel ; Maurice Tchoupé Tchendji - Projections et cohérence de vues dans les grammaires algébriques

arima:1885 - Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées, November 6, 2008, Volume 8, Special Issue CARI'06, 2008 -
Projections et cohérence de vues dans les grammaires algébriques

Authors: Eric Badouel ; Maurice Tchoupé Tchendji

A complex structured document is intentionnally represented as a tree decorated with attributes. The set of legal structures is given by an abstract context-free grammar. We forget about the attributes; they are related with semantical issues that can be treated independently of the purely structural aspects that we address in this article. That intentional representation may be asynchronously manipulated by a set of independent tools each of which operates on a distinct partial view of the whole structure. In order to synchronize these various partial views, we are faced to the problem of their coherence: can we decide whether there exists some global structure corresponding to a given set of partial views and in the affirmative, can we produce such a global structure ? We solve this problem in the case where a view is given by a subset of grammatical symbols, those associated with the so-called visible syntactical categories. The proposed algorithm, that strongly relies on the mechanism of lazy evaluation, produces an answer to this problem even if partial views may correspond to an infinite set of related global structures.

Volume: Volume 8, Special Issue CARI'06, 2008
Published on: November 6, 2008
Submitted on: April 24, 2008
Keywords: XML, Contex-Free Grammar, Intentional Representation, Coherence of Views, Lazy Evaluation, Co-Algebra, Tree Automata, Anamorphism,DTD,XML,grammaire algébrique,représentation intentionnelle,cohérence de vues,évaluation paresseuse,co-algèbres,automates d'arbres,anamorphisme,[INFO] Computer Science [cs],[MATH] Mathematics [math]


Consultation statistics

This page has been seen 81 times.
This article's PDF has been downloaded 114 times.