Re: Are there any tools that can compare two source files

torbenm@eir.diku.dk (Torben Ęgidius Mogensen)
20 Dec 2001 00:35:22 -0500

          From comp.compilers
Related articles
Are there any tools that can compare two source files satyanandam_g@hotmail.com (2001-12-07)
Re: Are there any tools that can compare two source files joachim_d@gmx.de (Joachim Durchholz) (2001-12-11)
Re: Are there any tools that can compare two source files sarath_kumar@mentorg.com (Sarath Kumar) (2001-12-15)
Re: Are there any tools that can compare two source files nmm1@cus.cam.ac.uk (2001-12-19)
Re: Are there any tools that can compare two source files joachim_d@gmx.de (Joachim Durchholz) (2001-12-20)
Re: Are there any tools that can compare two source files torbenm@eir.diku.dk (2001-12-20)
Re: Are there any tools that can compare two source files Martin.Ward@durham.ac.uk (2001-12-20)
Re: Are there any tools that can compare two source files thp@cs.ucr.edu (2001-12-20)
Re: Are there any tools that can compare two source files idbaxter@semdesigns.com (Ira D. Baxter) (2001-12-22)
Re: Are there any tools that can compare two source files tej@melbpc.org.au (Tim Josling) (2001-12-22)
| List of all articles for this month |
From: torbenm@eir.diku.dk (Torben Ęgidius Mogensen)
Newsgroups: comp.compilers
Date: 20 Dec 2001 00:35:22 -0500
Organization: Department of Computer Science, University of Copenhagen
References: 01-12-027 01-12-058
Keywords: tools, theory
Posted-Date: 20 Dec 2001 00:35:22 EST

Sarath Kumar <sarath_kumar@mentorg.com> writes:


> Generalizing the problem refers to the problem of finding the
> semantic equivalence of two programs. Is this possible?? As the
> theorists go this is very tough and not possible in polynomial time.


If the language is Turing-complete, equivalence is undecidable.


This doesn't man that you can never the decide if two programs are
equivalent, but it means that there are cases where you can't.


Some languages, e.g., regular expressions, have decidable equivalence,
but even for these, polynomial time normally isn't enough.


Torben Mogensen (torbenm@diku.dk)

Post a followup to this message

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