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. |