Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Generalized One-Unambiguity
verfasst von : Pascal Caron, Yo-Sub Han, Ludovic Mignot
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Brüggemann-Klein and Wood have introduced a new family of regular languages, the
one-unambiguous regular languages
, a very important notion in XML DTDs. A regular language
L
is one-unambiguous if and only if there exists a regular expression
E
over the operators of sum, catenation and Kleene star such that
L
(
E
) =
L
and the position automaton of
E
is deterministic. It implies that for a one-unambiguous expression, there exists an equivalent linear-size deterministic recognizer. In this paper, we extend the notion of one-unambiguity to weak one-unambiguity over regular expressions using the complement operator ¬. We show that a DFA with at most (
n
+ 2) states can be computed from a weakly one-unambiguous expression and that it is decidable whether or not a given DFA recognizes a weakly one-unambiguous language.