Evènement pour le groupe BioInformatique et Visualisation


Date 2010-06-03  14:00-15:00
TitreData-structure Rewriting 
RésuméIn general, the expressions considered in functional languages are represented as labelled trees (e.g. terms). These expressions are well suited for encoding classical data-structures such as lists or trees. However, real-world programs handle much more complex data-structures with structure sharing and cycles such as circular lists or doubly-linked lists. In many cases, the use of such complex data structures is mandatory for efficiency reasons, namely time and space complexity of algorithms. These data-structures are formally defined as particular graphs, called term-graphs. We will introduce a class of term-graph rewriting systems which allows one to define functions operating on data-structures with pointers. This class will be defined following both the algorithmic and the algebraic approaches. We then discuss the confluence property of such systems and introduce a new modal logic tailored to describe graph transformations and discuss some of its properties. 
LieuA29, Salle Ada Lovelace 
OrateurRachid Echahed 
EmailRachid.Echahed@imag.fr 
UrlIMAG 



Aucun document lié à cet événement.

Retour
Retour à l'index