2011 | OriginalPaper | Chapter
Generalized One-Unambiguity
Authors : Pascal Caron, Yo-Sub Han, Ludovic Mignot
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.