|elimination methods... email@example.com (V.C. SREEDHAR) (1995-05-28)|
|Re: elimination methods... firstname.lastname@example.org (Michael Wolfe) (1995-06-23)|
|Re: elimination methods... email@example.com (1995-06-30)|
|Re: elimination methods... firstname.lastname@example.org (1995-07-05)|
|From:||email@example.com (Thomas Lindgren)|
|Date:||Wed, 5 Jul 1995 12:29:46 GMT|
firstname.lastname@example.org (Chris Smith) writes:
/.../ Elimination boils everything down to composition (ab),
alternation (a|b), and iteration (a*). There's a Tarjan paper that tells
how to parse an arbitrary directed graph and get an equivalent regexp.
Alas, I can't find the reference. It was someplace I don't read much,
perhaps JACM, something like 1980-85.
R.E. Tarjan, Fast algorithms for solving path problems,
JACM, 3(28):591-642, July 1981.
Steven Tjiang used a modification of this algorithm for his Sharlit
system, described in PLDI'92. There is more info about this at the SUIF site,
Thomas Lindgren, Uppsala University
Return to the
Search the comp.compilers archives again.