Portal de Periódicos da CAPES

A unified approach for deciding the existence of certain petri net paths

1992; Elsevier BV; Volume: 96; Issue: 1 Linguagem: Inglês

10.1016/0890-5401(92)90059-o

1090-2651

Hsu‐Chun Yen,

semigroups and automata theory

In this paper, we develop a unified approach for deriving complexity results for a number of Petri net problems. We first define a class of formulas for paths in Petri nets. We then show that the satisfiability problem for our formulas is EXPSPACE complete. Since a wide range of Petri net problems can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net Problems can be shown to be solvable in EXPSPACE.