Abstrakt. Denna uppsats beskriver PReMo, ett verktyg för att analysera Recursive Markov Chains, och deras kontrollerade / spel förlängningar: (1-exit) Recursive Markov beslutsprocesser och Recursive Simple Stochastic Games. Inledning. Recursive Markov Chains (RMCs) [4, 5] är en naturlig abstrakt modell av probabilistiska procedurprogram och andra system som innefattar rekursion och sannolikhet. De är formellt likvärdiga med probabilistiska pushdown-system (pPDS) ([2, 3]), och de definierar en klass av oändliga Markov-kedjor som generaliserar ett antal väl studerade stokastiska modeller som Stochastic Context-Free Grammars (SCFGs) och Multi-Type Branching Processes. I en serie av senaste uppsatser ([4-7]) har den andra författaren och M. Yannakakis utvecklat algoritmer för analys och modellkontroll av RMC och deras kontrollerade och spelförlängningar: 1-exit Recursive Markov Decision Processes (1-RMDP) och 1-exit Recursive Simple Stochastic Games (1-RSSGs). Dessa tillägg tillåter modellering av icke-deterministiskt och interaktivt beteende. I detta dokument beskriver vi PReMo, ett programvaruverktyg för analys av modeller baserade på RMC, 1-RMDP och 1-RSSG. PReMo gör att dessa modeller kan specificeras i flera olika indataformat, inklusive ett enkelt imperativ stil språk för att ange RMCs och RSSGs, och ett indataformat för SCFGs. För RMC/RSSGs genererar PReMo en grafisk avbildning av modellen, användbar för att visualisera små modeller (se figur 1). PReMo har implementationer av numeriska algoritmer för ett antal analyser av RMC och 1-RSSGs. Från en RMC genererar PReMo ett motsvarande system av ickelinjära polynomekvationer, vars minsta fasta punkt (LFP) lösning ger exakt termineringssannolikhet för vertex-exit par i RMC. För 1-RSSGs, genererar det ett system av ickelinjära min-max ekvationer, vars LFP ger värdena för avslutande spelet med början vid varje vertex. Beräkning av sannolikheter för uppsägning är en nyckelingrediens för modellkontroll och andra analyser för RMC och pPDS ([4, 5, 2]). PReMo tillhandahåller ett antal optimerade numeriska algoritmer för beräkning av sannolikheter för terminering. Metoder som tillhandahålls inkluderar både täta och glesa versioner av en sönderbruten Newton metod som utvecklats i [4], samt versioner av värde iteration, optimerad med hjälp av icke-linjär generaliseringar av Gauss-Seidel och SOR tekniker. De senare metoderna gäller även för analys av 1-RSSG. Förutom att beräkna sannolikheter för terminering kan PReMo beräkna (maximum/minimum/game) förväntad termineringstid i 1-RMC, 1-RMDP och 1-RSSG. Det gör det genom att generera ett annat monotont system av linjära
PReMo REF är en modellkontroll för RMC.
PReMo: an analyzer for Probabilistic Recursive Models
{'venue': 'IN PROC. OF TACAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}