Evènement pour le groupe Graphes et Logique

Date 2013-03-05  11:00-12:00
TitreDeterministic regular expressions 
RésuméDeterministic regular expressions appear in many schema languages for XML (DTDs, XML Schemas) to define the possible content of an element. We prove that one can determine in linear time whether a given expression is deterministic. We also present algorithms to decide in linear time if a given word is accepted by an expression, for large families of deterministic regular expressions. Our algorithms build datastructures on the expression's parse tree, whereas classical algorithms for those problems rely on the Glushkov automaton which may have quadratic size when the size of the alphabet is not bounded. 
LieuSalle 076 
OrateurBenoît Groz 
UrlTel Aviv University 

Aucun document lié à cet événement.

Retour à l'index