0
$\begingroup$

This paper seems to point out that Bouziane’s solution is incorrect.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.143.9009&rep=rep1&type=pdf

In the conclusion:

This false claim served for deriving a bound on the number of states of the constructed automaton – which in reality can have infinitely many states.

I think I understand this point as it relates to the general reachibility problem, However The Petri-Net used as an illustration contains 'loops' at transitions: t3 and t1 - transitions that have both incoming and outgoing arcs.

If Petri-Net being examined were composed of only elementary paths, the resulting witness sequence / state machine language would not be susceptible to the pumping lemma.

Does this seem accurate? why or why not?

$\endgroup$
1
$\begingroup$

Found another article that helped me understand:

COMPEXITY OF SOME PROBLEMS IN PETRI NETS*

http://www.sciencedirect.com/science/article/pii/0304397577900147

This paper does a good job of explaining the difference between a k-bounded Petri-Net and an unbounded one.

A Petri net is bounded if and only if it has a finite reachability set.

Bouziane’s solution applies only to bounded Petri-Nets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.