On Languages Accepted by P/T Systems Composed of joins

Details On Languages Accepted by P/T Systems Composed of joins On Languages Accepted by P/T Systems Composed of joins

2009-07-29

arxiv.org/abs/0907.5121v1

EPTCS 3, 2009, pp. 111-120

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.10

Recently, some studies linked the computational power of abstract computing systems based on multiset rewriting to models of Petri nets and the computation power of these nets to their topology. In turn, the computational power of these abstract computing devices can be understood by just looking at their topology, that is, information flow. Here we continue this line of research introducing J languages and proving that they can be accepted by place/transition systems whose underlying net is composed only of joins. Moreover, we investigate how J languages relate to other families of formal languages. In particular, we show that every J language can be accepted by a log n space-bounded non-deterministic Turing machine with a one-way read-only input. We also show that every J language has a semilinear Parikh map and that J languages and context-free languages (CFLs) are incomparable.

Affiliated with

Also associated with

No associations

Rating

On Languages Accepted by P/T Systems Composed of joins does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Languages Accepted by P/T Systems Composed of joins, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Languages Accepted by P/T Systems Composed of joins will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521643