Vi undersöker gcf-Petri nät, en generalisering av kommunikationsfria Petri nät som tillåter godtyckliga kantmångfald, och kännetecknas av den enda begränsning som varje övergång har som mest en inkommande kant. Vi använder kanoniska ringsekvenser med fina egenskaper för gcf-PNs för att visa att Reclfs, (noll-)åtkomlighet, täckning och begränsningsproblem för gcf-PNs är i PSPACE. Genom att visa, hur PSPACE-Turing maskiner kan simuleras av gss-PNs, en underklass av gcf-PNs där dessutom alla övergångar har som mest en utgående kant, vi slutligen bevisa PSPACE-fullbordande av dessa problem för gss/gcf-PNs. Sedan visar vi PSPACE-hårdhet samt ett dubbelt exponentiellt utrymme som är bundet till inneslutning, och ekvivalensproblem av gss/gcf-PNs. Slutligen överväger vi en ny naturlig generalisering av kontextfri pendlande grammatik. Våra resultat för gcf-PN innebär PSPACE-fullständighet för dess enhetliga ordproblem.
En ytterligare generalisering av kommunikationsfria Petri-nät, som nyligen studerats av Mayr och Weihmann, är kommunikationsfria Petri-nät med godtyckliga kantmångfaldigheter REF.
Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Arc Multiplicities
{'venue': 'Fundam. Inform.', 'journal': 'Fundam. Inform.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}