Prev: hi
Next: VMCAI 2009: Call for Papers
From: Eric Bodden on 27 Jun 2008 18:38
I am currently writing a paper about an analysis that should be
feasible for any computational system for which one can decide
reachability of configurations, e.g. finite state machines, petri nets
etc. This made me wonder: Is there any concise classification of
"languages for which reachability is decidable"?

I know that reachability is undecidable for Turing-complete systems
but I am not sure if the inverse direction also holds. Are there non-
Turing-complete languages for which reachability is undecidable or
does "non-Turing-complete" somehow imply that one can decide
reachability?

Hope you see what I mean ;-)

Cheers,
Eric
From: Bhupinder Singh Anand on 28 Jun 2008 04:05
On Jun 28, 3:38 am, Eric Bodden <eric.bod...(a)googlemail.com> wrote in
comp.theory:

EB>> Is there any concise classification of "languages for which
reachability is decidable"? <<EB

Erik
====
Could these concepts be related to 'constructive computabilty' and
Turing-computability', which I address in "A trivial solution to
PvNP"?

http://alixcomsi.com/18_A_trivial_solution_to_PvNP.pdf

Bhup
From: Hans H�ttel on 30 Jun 2008 17:26
In article
<2223bc46-5bd6-49dc-8521-2018c8ad19ca(a)m3g2000hsc.googlegroups.com>,
Eric Bodden <eric.bodden(a)googlemail.com> wrote:

> I am currently writing a paper about an analysis that should be
> feasible for any computational system for which one can decide
> reachability of configurations, e.g. finite state machines, petri nets
> etc. This made me wonder: Is there any concise classification of
> "languages for which reachability is decidable"?
>
> I know that reachability is undecidable for Turing-complete systems
> but I am not sure if the inverse direction also holds. Are there non-
> Turing-complete languages for which reachability is undecidable or
> does "non-Turing-complete" somehow imply that one can decide
> reachability?
>
> Hope you see what I mean ;-)

First I should warn you that this is not my research area. But I do know
that Petri nets are not Turing-powerful and their reachability problem
is decidable, but hard, so a natural candidate would be an extension of
Petri nets.

Timed-arc Petri nets are not Turing-powerful but reachability is
undecidable. See e.g.

http://www.informatik.uni-hamburg.de/TGI/pnbib/v/valero_ruiz_v1.html

--
Hans H�ttel
Department of Computer Science
Aalborg University
Denmark
 | 
Pages: 1
Prev: hi
Next: VMCAI 2009: Call for Papers