Grafer är bland de mest använda strukturerna inom datavetenskap. Några av de egenskaper som måste kontrolleras i många applikationer är konnektivitet, acyklicitet och Eulerian och Hamiltonian egenskaper. I detta arbete analyserar vi hur vi kan uttrycka dessa fyra egenskaper med modal logik. Det handlar om två frågor: om vart och ett av de aktuella modalspråken har tillräcklig uttryckskraft för att beskriva dessa egenskaper och hur komplext (beräkningsmässigt) det är att använda dessa logiker för att faktiskt testa om en viss graf har någon önskad egenskap. För det första visar vi att dessa egenskaper inte är definierbara i en grundläggande modal logik eller i någon bisimulation-invariant förlängning av det, som modal μ-kalculus. Vi visar sedan att det är möjligt att uttrycka några av ovanstående egenskaper i en grundläggande hybridlogik. Tyvärr kan de Hamiltonian och Eulerian egenskaper fortfarande inte kontrolleras effektivt. I ett andra försök föreslår vi en förlängning av CTL * med nominella värden och visar att Hamiltons egendom kan kontrolleras mer effektivt i denna logik än i föregående. I ett tredje försök utökar vi den grundläggande hybridlogiken med ↓-operatören och visar att vi kan kontrollera Hamiltons egendom med optimal (NP) komplexitet i denna logik. Slutligen tar vi itu med den eulerska egendomen på två olika sätt. För det första utvecklar vi en generisk metod för att uttrycka kantrelaterade egenskaper i hybridlogik och använda den för att uttrycka den eulerska egenskapen. För det andra uttrycker vi ett nödvändigt och tillräckligt villkor för att den eulerska egendomen ska hålla fast vid en graderad modal logik.
I REF analyserade författarna globala grafegenskaper som konnektivitet, acyklicitet och Eulerianska och Hamiltonska egenskaper som inte kan definieras i en grundläggande modal logik.
Using modal logics to express and check global graph properties
{'venue': 'Log. J. IGPL', 'journal': 'Log. J. IGPL', 'mag_field_of_study': ['Computer Science', 'Mathematics']}