Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: formal sociology

Sortuj według:

Ogranicz wyniki do:

Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms

Mayr E. W., Weihmann J.

Fundamenta Informaticae

2015

Vol. 137, nr 1

61--86

We investigate several computational problems of communication-free Petri nets, and develop very efficient (mostly linear time) algorithms for different variations of the boundedness and liveness problems of cf-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. In the last part, we use our results for cf-PNs to give linear time algorithms for related problems of context-free (commutative) grammars, and, in turn, use known results for such grammars to give a coNEXPTIME-upper bound for the equivalence problem of cf-PNs.