5 Feb 88 04:19:29 GMT

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) |

From: | larus@ucbvax.Berkeley.EDU |

Date: | 5 Feb 88 04:19:29 GMT |

Organization: | University of California, Berkeley |

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,

/Jim

ARPANet: larus@ginger.Berkeley.EDU

uucp: ucbvax!larus

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.