Vi studerar tillfredsställande problem för kvalitativa PCTL (Probabilistic Computation Tree Logic), som erhålls från "vanliga" CTL genom att ersätta EX, AX, EU och AU operatörer med deras kvalitativa motsvarigheter X >0, X =1, U >0, och U =1, respektive. I motsats till CTL, har kvalitativa PCTL inte en liten modell egendom, och det finns även kvalitativa PCTL formler som bara har oändliga modeller. Icke desto mindre visar vi att tillfredsställandet problem för kvalitativ PCTL är EXPTIM-komplett och vi ger en exponentiellt-tids algoritm som för en given formel beräknar en ändlig beskrivning av en modell (om den finns), eller svarar "inte tillfredsställande" (på annat sätt). Vi betraktar också det finita tillfredsställande problemet och ger liknande resultat. Det vill säga, vi visar att det finita tillfredsställande problemet för kvalitativ PCTL är EXPTIM-komplett, och varje finit tillfredsställande formel har en modell av en exponentiell storlek som effektivt kan konstrueras i exponentiell tid. Slutligen ger vi några resultat om den kvantitativa PCTL, där de numeriska gränserna i sannolikhetsbegränsningar kan vara godtyckliga rationella mellan 0 och 1. Vi bevisar att problemet med huruvida en viss kvantitativ PCTL formel har en modell av grenningsgraden som mest k, där k ≥ 2 är en godtycklig men fast konstant, är mycket obeslutbar. Vi visar också att varje tillfredsställande formel har en modell med grenningsgrad som mest + 2. Detta innebär dock ännu inte att det tillfredsställande problemet för kvantitativ PCT är obeslutbart, och vi förmodar tvärtom.
REF visar att problemet är obeslutbart om det för en viss PCTL-formel finns en modell med en grenningsgrad som begränsas av ett visst heltal, där grenningsgraden är antalet efterträdare till en stat.
The Satisfiability Problem for Probabilistic CTL
{'venue': '2008 23rd Annual IEEE Symposium on Logic in Computer Science', 'journal': '2008 23rd Annual IEEE Symposium on Logic in Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}