Re: elimination methods...

thomasl@groucho.csd.uu.se (Thomas Lindgren)
Wed, 5 Jul 1995 12:29:46 GMT

          From comp.compilers

Related articles
elimination methods... sreedhar@flo.cs.mcgill.ca (V.C. SREEDHAR) (1995-05-28)
Re: elimination methods... mwolfe@cse.ogi.edu (Michael Wolfe) (1995-06-23)
Re: elimination methods... csmith@convex.convex.com (1995-06-30)
Re: elimination methods... thomasl@groucho.csd.uu.se (1995-07-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: thomasl@groucho.csd.uu.se (Thomas Lindgren)
Keywords: optimize, bibliography
Organization: Uppsala University
References: 95-06-035 95-07-034
Date: Wed, 5 Jul 1995 12:29:46 GMT

  csmith@convex.convex.com (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.


Possibly:


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,


http://suif.stanford.edu/papers/papers.html


Thomas
--
Thomas Lindgren, Uppsala University
thomasl@csd.uu.se, lindgren@sics.se
http://www.csd.uu.se/~thomasl/home.html
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.