?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=A+New+Proof+Rule+for+Almost-Sure+Termination&rft.creator=McIver%2C+A&rft.creator=Morgan%2C+C&rft.creator=Kaminski%2C+BL&rft.creator=Katoen%2C+J-P&rft.description=An+important+question+for+a+probabilistic+program+is+whether+the+probability+mass+of+all+its+diverging+runs+is+zero%2C+that+is+that+it+terminates+%22almost+surely%22.+Proving+that+can+be+hard%2C+and+this+paper+presents+a+new+method+for+doing+so%3B+it+is+expressed+in+a+program+logic%2C+and+so+applies+directly+to+source+code.+The+programs+may+contain+both+probabilistic-+and+demonic+choice%2C+and+the+probabilistic+choices+may+depend+on+the+current+state.+As+do+other+researchers%2C+we+use+variant+functions+(a.k.a.+%22super-martingales%22)+that+are+real-valued+and+probabilistically+might+decrease+on+each+loop+iteration%3B+but+our+key+innovation+is+that+the+amount+as+well+as+the+probability+of+the+decrease+are+parametric.+We+prove+the+soundness+of+the+new+rule%2C+indicate+where+its+applicability+goes+beyond+existing+rules%2C+and+explain+its+connection+to+classical+results+on+denumerable+(non-demonic)+Markov+chains.&rft.subject=cs.PL%2C+cs.PL%2C+cs.LO&rft.publisher=ACM&rft.date=2018-01&rft.type=Proceedings+paper&rft.language=eng&rft.source=+++++In%3A++Proceedings+of+the+ACM+on+Programming+Languages.++(pp.+p.+33).++ACM%3A+Los+Angeles%2C+California%2C+USA.+(2018)+++++&rft.format=text&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10089705%2F1%2F1711.03588v2.pdf&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10089705%2F&rft.rights=open