Re: FYI: Regex paper for UTC

From: Hans Aberg (haberg@math.su.se)
Date: Sat Oct 13 2007 - 17:48:55 CDT

  • Next message: Philippe Verdy: "RE: FYI: Regex paper for UTC"

    On 14 Oct 2007, at 00:05, Philippe Verdy wrote:

    > All my regexps are first normalized to alternations and negations ONLY
    > (instead of putting the negation at the beginning of the regexp
    > ONLY and
    > using multiple binary set operators "|", "&", "\" like suggested in
    > the
    > recent paper submitted to the UTC).

    The definition in terms of a language L(x) has the advantage of
    avoiding that problem, and being theoretically clearer exactly as to
    what is being defined.

    > This greatly simplifies the optimization of the transition graph,
    > where I
    > reduce and reorder the number of transitions per node in the graph
    > to reduce
    > the number of tests to perform at each state.

    And leaving this to an implementation problem. For example, somebody
    might want to implement a hybrid FA, where the DFA states are
    computed dynamically from the NFA and cached. The book by Aho et al.
    [loc.cit.] says this gives the best overall time and space complexity.

       Hans Åberg



    This archive was generated by hypermail 2.1.5 : Sat Oct 13 2007 - 17:50:34 CDT