Query on Path Problems

"Usha" <usha_solanki@pune.tcs.co.in>
11 Mar 2004 12:56:14 -0500

          From comp.compilers
Related articles
Query on Path Problems usha_solanki@pune.tcs.co.in (Usha) (2004-03-11)
Query on Path Problems larus@ucbvax.Berkeley.EDU (1988-02-05)
| List of all articles for this month |
From: "Usha" <usha_solanki@pune.tcs.co.in>
Newsgroups: comp.compilers
Date: 11 Mar 2004 12:56:14 -0500
Organization: Compilers Central
Keywords: analysis, question
Posted-Date: 11 Mar 2004 12:56:14 EST

Hi,


Robert Tarjan published a pair of papers in the JACM (July 1981) on
path problems and data flow analysis. Has anyone implemented his algorithms
and compared their space and runtime requirements with conventional data
flow
algorithms? Is anyone aware of a paper on this subject?


For those who haven't read the papers (which I highly recommend), Tarjan
showed how to efficiently construct a regular expression that describes
the set of possible paths in a control flow graph. A data flow problem
can be solved by giving a non-standard interpretation to the operators
(".", "|", and "*") in the expression. It is not actually necessary to
construct the expression, though it may be of benefit if more than one
problem is to be solved on the same graph.


Thanks,
Usha

Post a followup to this message

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