Re: Looking for a rooted DAG isomorphism algorithm

karlcz@ISI.EDU
12 Mar 1998 23:13:15 -0500

          From comp.compilers
Related articles
Looking for a rooted DAG isomorphism algorithm cburns@crl8.crl.com (Charlie Burns) (1998-02-15)
Re: Looking for a rooted DAG isomorphism algorithm carl@bitstream.net (Carl Sturtivant) (1998-03-03)
Re: Looking for a rooted DAG isomorphism algorithm lkaplan@mips.complang.tuwien.ac.at (1998-03-05)
Re: Looking for a rooted DAG isomorphism algorithm cburns@crl2.crl.com (Charlie Burns) (1998-03-06)
Re: Looking for a rooted DAG isomorphism algorithm karlcz@ISI.EDU (1998-03-12)
| List of all articles for this month |
From: karlcz@ISI.EDU
Newsgroups: comp.compilers
Date: 12 Mar 1998 23:13:15 -0500
Organization: USC Information Sciences Institute
References: 98-02-073 98-03-028
Keywords: theory
Posted-Date: Sun, 8 Mar 1998 22:45:30 GMT

>Charlie Burns (cburns@crl8.crl.com) wrote:
>: I am looking for references to a rooted DAG isomorphism algorithm. The
>: DAGs I want to compare are like trees but nodes can have more than one
>: parent.


If I understand correctly what you want, it seems this could be
phrased as a minor variant of structural unification. you Might Try
looking at the type-inference literature where such problems come up
All The Time. If your DAGs are multi-rooted (like a forest), I think
you would have to introduce some extra top-level decision to unify
each interesting permutation of rooted DAG pairs.


karl
--
Karl Czajkowski
karlcz@isi.edu
--

Post a followup to this message

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