Re: generic state machine transaltion algorithm

"Piotr Wyderski" <>
2 Oct 2004 01:11:54 -0400

          From comp.compilers

Related articles
generic state machine transaltion algorithm (2004-09-21)
Re: generic state machine transaltion algorithm (Chris F Clark) (2004-09-24)
Re: generic state machine transaltion algorithm (Piotr Wyderski) (2004-10-02)
| List of all articles for this month |

From: "Piotr Wyderski" <>
Newsgroups: comp.compilers
Date: 2 Oct 2004 01:11:54 -0400
Organization: Faculty of Computer Science, University of Wroclaw
References: 04-09-126
Keywords: theory
Posted-Date: 02 Oct 2004 01:11:54 EDT

Paul wrote:

> There is generic algorithm for translating between state machines so
> that programs that used to run on one state machine can be run on
> another via this translation process.

What do you mean by "state machine"? This term usually means
finite automata, which do not run programs, but recognize a class of
languages. It's possible to check whether two different specifications
describe the same regular language. But if by "state machine" you
mean computer processors, then, generally, the answer is "no",
since the translation process is undecidable (have a look at
semi-Thue processes for example, as well as many others rewriting
problems). On the other hand, there are some decidable subclasses,
which may turn out to be extremelly important for practical applications.
Search the ACM library for references addressing the area called
"binary translation". However, most of the so-called automatic
translators are in fact not so automatic, they often require tremendous
human support.

> So far as I know, all such processes are manual and non automatic.

And -- oversimplifying -- you are right.

> Is there any theory,

Yes: Term Rewriting Systems, automatic theorem proving, various
state space exploration and compression techniques (BDD etc.). As
far as I know there's no consistent, general theory, but many bricks
to build one are already available.

> or some one might have found a way to do it?

Well, in fact I'm going to do exactly this. :-)

        Piotr Wyderski

Post a followup to this message

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