Nåbarhetsproblemet för Vector Addition Systems (VAS) är ett centralt problem för nätteorin. Det allmänna problemet är känt decidable av algoritmer uteslutande baserat på den klassiska Kosaraju-Lambert-Mayr-SacerdoteTenney nedbrytning. Denna nedbrytning används i detta papper för att bevisa att Parikh-bilderna av språk som accepteras av VAS är semipseudo-linjära; en klass som utökar de semilinjära uppsättningarna, alias. de uppsättningar som kan definieras i aritmetiken i Presburger. Vi tillhandahåller en tillämpning av detta resultat; vi bevisar att en slutlig konfiguration inte kan nås från en initial om och endast om det finns en Presburger formel som anger en framåt induktiv invariant som innehåller den ursprungliga konfigurationen men inte den slutliga. Eftersom vi kan avgöra om en Preburger-formel betecknar en induktiv invariant, drar vi slutsatsen att det finns kontrollerbara intyg om icke-uppnåelighet. I synnerhet finns det en enkel algoritm för att bestämma den allmänna VAS räckvidd problem baserat på två semi-algoritmer. En första som försöker bevisa nåbarheten genom att räkna upp ändliga sekvenser av handlingar och en andra som försöker bevisa icke-uppnåeligheten genom att räkna Presburger formler.
I REF visas det att en stat är ouppnåelig i fordonslarmet iff det finns en "induktiv" Presburger-formel som separerar de ursprungliga och slutliga staterna.
The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
{'venue': '2009 24th Annual IEEE Symposium on Logic In Computer Science', 'journal': '2009 24th Annual IEEE Symposium on Logic In Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}