Re: FYI: Regex paper for UTC

From: Hans Aberg (
Date: Sat Oct 13 2007 - 12:06:24 CDT

  • Next message: Mark Davis: "Re: FYI: Regex paper for UTC"

    On 13 Oct 2007, at 17:38, Philippe Verdy wrote:

    >>> Andy and I put together a paper of recommendations for the UTC at
    >>> .
    >> I suspect you will run into problems when mixing complement with the
    >> Kleene closure (zero or more concatenations) operator (and other
    >> operators generating an infinite number of strings in the associated
    >> language).
    >> So one safe way is to admit the usual set operations on character
    >> classes only, and letting regular expressions having only the usual
    >> operators acting on character classes.
    > This is only true if you use the assumption that the current state
    > of the
    > generated DFA should be represented using a single integer type.

    I am not sure what the DFAs have here to do.

    If the RE r generates the language L(r), and ~r is the complement,
    what is the definition of L(~r)? Specifically:

    If L(ε) is the empty string, what is L(~ε)?

    What is the definition of L(~(r*))?

       Hans Åberg

    This archive was generated by hypermail 2.1.5 : Sat Oct 13 2007 - 12:08:23 CDT