Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Deterministic regular expressions
du 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 
Emailbenoit.groz@inria.fr 
UrlTel Aviv University 



Aucun document lié à cet événement.

Retour
Retour à l'index