Abstrakt. Vi anser att det är ett problem att kontrollera säkerheten hos välstrukturerade övergångssystem (WSS) med hjälplagring. WSTS med lagring är automatiska som (eventuellt) har oändligt många kontrolltillstånd tillsammans med en hjälpbutik, men som har en väl-quasi-ordning på uppsättningen av kontrolltillstånd. Den uppsättning av tillgängliga konfigurationer av automaton kan själva inte vara väl-quasi-ordning på grund av närvaron av den extra butiken. Vi ser på problemet med täckning för sådana system, som frågar om det är möjligt att nå ett kontrolltillstånd (med något lagervärde) som täcker vissa givna kontrolltillstånd. Vårt huvudresultat visar att om kontrolltillståndets räckvidd är deciderbar för automata med vissa lager och ändligt många kontrolltillstånd då kan skyddsproblemen avgöras för WSTS (med oändligt många kontrolltillstånd) och samma butik, förutsatt att beställningen på kontrollstaterna har vissa speciella egenskaper. Den speciella egenskap vi behöver definieras i termer av förekomsten av en rankningsfunktion som är förenlig med övergångsförhållandet. Vi visar sedan att det finns flera klasser av oändliga tillståndssystem som kan ses som WSTS med en extra lagring. Dessa observationer kan sedan användas för att både återställa gamla decledability resultat, samt upptäcka nya.
En automat med hjälpbutik REF består av en kontroll och en hjälpbutik.
Decidability results for well-structured transition systems with auxiliary storage
{'venue': 'In CONCUR, vol. 4703 of LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}