Alternating-time Temporal Logic (ATL), som infördes av Alur, Henzinger och Kupferman, är en logisk formalism för specifikation och verifiering av öppna system som involverar flera autonoma spelare (agenter, komponenter). I synnerhet möjliggör denna logik ett uttryckligt uttryck för koalitionens förmågor i sådana system, modellerade som oändliga övergångsspel mellan koalitionen och dess komplement. Formellt sett är ATL en icke-normal multimodal förlängning av CTL (som betraktas som ett fragment av ATL med en spelare) med temporaloperatörer som indexeras av koalitioner av spelare, och därmed uttrycker selektiv kvantifiering över de vägar som kan genomföras som resultat av oändliga övergångsspel mellan koalitionen och dess komplement. Vi presenterar en sund och fullständig axiomatisering av logiken ATL, baserad på Paulys axiomatisering av hans koalition Logik, förstärkt med axiomer och regler för fasta punktformler som kännetecknar de temporala operatörerna. Fullständigheten är genom konstruktion av en avgränsad trädmodell för varje ATL-konsistent formel. Dessa modeller kan vikas in i finita modeller och därmed göra den finita modellegendomen för ATL. Vi beskriver också ett automatiserat beslutsförfarande för ATL genom att översätta tillfredsställande problem till nonempty problem för alternerande automata på oändliga träd. När man överväger formler över en fast ändlig uppsättning spelare decledability problemet visas vara EXPTIM-fullständig.
Begränsningar av antalet agenter och deras lokala stater är ett direkt resultat av den ändliga modellen egendom för ATL REF.
Complete axiomatization and decidability of Alternating-time temporal logic
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}