Evènement pour le groupe Modélisation et Verification

Date 2012-03-08  11:30-12:30
TitreThe Cost of Repairing Regular Specifications 
RésuméWhat do you do if a computational object (e.g., a document, a program trace) fails a specification? An obvious approach is to perform a "repair": modify the object minimally to get something that satisfies the constraints. This approach has been extensively investigated in the database community for relational integrity constraints, and in the AI community for propositional logics. Different modification operators have been considered on the basis of the application scenarios. For instance, a repair of an XML document usually consists of applying to the underlying tree structure a certain number of editing operations such as relabelings, deletions, and insertions of nodes. In this talk I will survey some results related to the worst-case cost of repairing documents between regular specifications. Precisely, I will focus on the number of edits that are needed to get from a document (i.e., a word or a tree) that satisfies a source specification (i.e., a regular language S) to some document that satisfies a target specification (i.e., a regular language T). As this number may well be unbounded, I will consider the problem of determining those pairs of languages (S,T) such that one can get from any word/tree in S to a word/tree in T using a finite, uniformly bounded number of editing operations. I will give effective characterizations of these pairs when S and T are given by finite state automata (word case) or stepwise tree automata (tree case), and derive some complexity bounds for the corresponding problems. The presentation is based on joint works with Michael Benedikt, Cristian Riveros, and Sławek Staworko.  
OrateurGabriele Puppis 

Aucun document lié à cet événement.

Retour à l'index