Abstrakt. Vi associerar en graf med ett 1-säkert Petri-nät och studerar den parameteriserade komplexiteten hos olika problem med parametrar som härleds från grafen. Med trädbredd som parameter ger vi W[1]-hårdhetsresultat för många problem kring 1-säkra Petrinät. Som en följd av detta bevisar detta ett antagande av Downey et. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. om hårdheten hos vissa graf pebbling problem. Vi anser parametern nytta djup (som är känt för att vara till hjälp för att få bättre algoritmer för allmänna Petri nät) och återigen ge W[1]-hårdhet resultat för olika problem på 1-säkra Petri nät. Vi anser också att den starkare parametern vertex täcknummer. Genom att kombinera den välkända automatiska-teoretiska metoden och ett kraftfullt fast parameterdragbarhet (Fpt) resultat om Integer Linjär programmering, ger vi en Fpt algoritm för modellkontroll Monadic Second Order (MSO) formler på 1-säkra Petri nät, med parametrar vertex täcknummer och storleken på formeln.
På senare tid har REF utvecklat en algoritm för modellkontroll av monadiska andra ordningens formler på 1-säkra Petri-nät.
Parameterized complexity results for 1-safe Petri nets
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}