I den här artikeln överväger vi att avsluta probabilistiska program med verkligt värderade variabler. De frågor som berörs är följande: kvalitativa frågor som ställer (i) huruvida programmet avslutas med sannolikhet 1 (nästan säkert avslutande) och (ii) huruvida den förväntade termineringstiden är ändlig (slutlig uppsägning), och kvantitativa frågor som ber (i) att approximera den förväntade termineringstiden (förväntningsproblem) och (ii) att beräkna en bunden B så att sannolikheten att inte avsluta efter B steg minskar exponentiellt (koncentrationsproblem). För att lösa dessa frågor använder vi begreppet rankning supermartingales, vilket är ett kraftfullt tillvägagångssätt för att bevisa avslutande av probabilistiska program. I detalj fokuserar vi på algoritmisk syntes av linjär rankning-supermartingales över affin probabilistiska program (Apps) med både ängla- och demonisk icke-determinism. En viktig underklass av Apps är LRApp som definieras som den klass av alla Apps över vilken en linjär ranking-supermartingale finns. Våra viktigaste bidrag är följande: För det första visar vi att medlemskap problemet med LRApp (i) kan avgöras i polynom tid för Apps med som mest demonisk icke-determinism, och (ii) är NP-hård och i PSPACE för Apps med ängla icke-determinism. Dessutom har NP-hårdhet resultatet redan för Apps utan sannolikhet och demonisk icke-determinism. För det andra visar vi att koncentrationsproblemet över LRApp kan lösas i samma komplexitet som för medlemskap problemet med LRApp. Slutligen visar vi att förväntan problem över LRApp kan lösas i 2EXPTIME och är PSPACE-hård även för Apps utan sannolikhet och icke-determinism (dvs. deterministiska program). Våra experimentella resultat visar effektiviteten i vår strategi för att besvara de kvalitativa och kvantitativa frågorna över Apps med som mest demonisk icke-determinism.
Särskilt Chatterjee et al. REF anser den klass av affin probabilistiska program för vilka linjär rankning supermartingales finns (Lrapp); vilket bevisar (positiv 2 ) nästan säker avslutning för alla program inom denna klass.
Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs
{'venue': 'TOPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}