Probabilistic verification beyond context-freeness
<p>Probability theory and probabilistic modelling have become indispensable across a wide range of scientific disciplines, with probabilistic programs emerging as a particularly flexible means of encoding sophisticated models in executable code. These programs, which merge traditional programm...
| Prif Awdur: | |
|---|---|
| Awduron Eraill: | |
| Fformat: | Traethawd Ymchwil |
| Iaith: | English |
| Cyhoeddwyd: |
2024
|
| Pynciau: |
| _version_ | 1826316872150155264 |
|---|---|
| author | Li, G |
| author2 | Murawski, A |
| author_facet | Murawski, A Li, G |
| author_sort | Li, G |
| collection | OXFORD |
| description | <p>Probability theory and probabilistic modelling have become indispensable across a wide range of scientific disciplines, with probabilistic programs emerging as a particularly flexible means of encoding sophisticated models in executable code. These programs, which merge traditional programming constructs with probabilistic reasoning, play a pivotal role in areas such as machine learning and systems biology. However, as these programs gain prominence, the demand for robust verification methods becomes increasingly urgent.</p>
<br>
<p>While Markov Chains (MCs) have long been foundational tools in this field, their limitations in modelling complex, recursive systems have prompted the development of more expressive models, such as Recursive Markov Chains (RMCs) and Probabilistic Pushdown Automata (pPDAs). Recent advancements, including extensions to higher-order grammars like Probabilistic Higher-Order Recursion Schemes (PHORS), offer enhanced expressiveness but introduce significant challenges, such as the undecidability of Almost Sure Termination (AST). This underscores the need for models that balance expressiveness with decidability.</p>
<br>
<p>This research presents and examines the Restricted Probabilistic Tree-Stack Automaton (rPTSA), a novel probabilistic model that extends recursive models while circumventing the undecidability issues associated with PHORS. Originating from the Restricted Tree-Stack Automaton (rTSA), the rPTSA model inherits broad connections to various fields, including linguistics and higher-order verification. Building on these connections, the research also introduces Probabilistic Additive HORS (PAHORS), which incorporates an affineness constraint and pair-product structures into PHORS.</p>
<br>
<p>We demonstrate that these two models, rPTSA and PAHORS, are equi-expressive, as they inherit characteristics from their non-probabilistic counterparts, rTSA and Multiplicative Additive HORS (MAHORS). Furthermore, rPTSA and PAHORS are shown to be strictly more expressive than order-1 PHORS and incomparable to order-2 PHORS, and they hence offer a balance between expressiveness and decidability.</p>
<br>
<p>Utilising their equi-expressiveness, this work primarily focuses on the rPTSA model. Firstly, it establishes the decidability of the Almost-Sure Termination (AST) and Positive Almost-Sure Termination (PAST) properties for rPTSA, and develops methods for quantitatively analysing termination probability and expected termination time. The research also delves into model checking for both linear-time properties (ω-regular and LTL) and branching-time properties (PCTL*). Notably, the PCTL* model checking procedure relies heavily upon the algorithm established for LTL. Additionally, this research examines the restriction property of rPTSA, a crucial feature that prevents rPTSA from attaining Turing-completeness.</p>
<br>
<p>The practical contribution of this work is the development of the Probabilistic Tree-Stack Verifier (PTSV), an efficient tool for determining termination probability and expected termination time. Further attention is given to PAHORS and other key models, such as pPDA and MCFG. The study discusses the mutual conversions between rPTSA and PAHORS, as well as conversions from other models of interest, such as pPDA and Stochastic MCFG, to rPTSA.</p> |
| first_indexed | 2025-02-19T04:29:42Z |
| format | Thesis |
| id | oxford-uuid:493fba3f-e4ef-43f2-afdb-86b67e8306df |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:29:42Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | oxford-uuid:493fba3f-e4ef-43f2-afdb-86b67e8306df2024-12-18T10:01:13ZProbabilistic verification beyond context-freenessThesishttp://purl.org/coar/resource_type/c_db06uuid:493fba3f-e4ef-43f2-afdb-86b67e8306dfTheoretical computer scienceEnglishHyrax Deposit2024Li, GMurawski, AOng, LWorrell, JTotzke, P<p>Probability theory and probabilistic modelling have become indispensable across a wide range of scientific disciplines, with probabilistic programs emerging as a particularly flexible means of encoding sophisticated models in executable code. These programs, which merge traditional programming constructs with probabilistic reasoning, play a pivotal role in areas such as machine learning and systems biology. However, as these programs gain prominence, the demand for robust verification methods becomes increasingly urgent.</p> <br> <p>While Markov Chains (MCs) have long been foundational tools in this field, their limitations in modelling complex, recursive systems have prompted the development of more expressive models, such as Recursive Markov Chains (RMCs) and Probabilistic Pushdown Automata (pPDAs). Recent advancements, including extensions to higher-order grammars like Probabilistic Higher-Order Recursion Schemes (PHORS), offer enhanced expressiveness but introduce significant challenges, such as the undecidability of Almost Sure Termination (AST). This underscores the need for models that balance expressiveness with decidability.</p> <br> <p>This research presents and examines the Restricted Probabilistic Tree-Stack Automaton (rPTSA), a novel probabilistic model that extends recursive models while circumventing the undecidability issues associated with PHORS. Originating from the Restricted Tree-Stack Automaton (rTSA), the rPTSA model inherits broad connections to various fields, including linguistics and higher-order verification. Building on these connections, the research also introduces Probabilistic Additive HORS (PAHORS), which incorporates an affineness constraint and pair-product structures into PHORS.</p> <br> <p>We demonstrate that these two models, rPTSA and PAHORS, are equi-expressive, as they inherit characteristics from their non-probabilistic counterparts, rTSA and Multiplicative Additive HORS (MAHORS). Furthermore, rPTSA and PAHORS are shown to be strictly more expressive than order-1 PHORS and incomparable to order-2 PHORS, and they hence offer a balance between expressiveness and decidability.</p> <br> <p>Utilising their equi-expressiveness, this work primarily focuses on the rPTSA model. Firstly, it establishes the decidability of the Almost-Sure Termination (AST) and Positive Almost-Sure Termination (PAST) properties for rPTSA, and develops methods for quantitatively analysing termination probability and expected termination time. The research also delves into model checking for both linear-time properties (ω-regular and LTL) and branching-time properties (PCTL*). Notably, the PCTL* model checking procedure relies heavily upon the algorithm established for LTL. Additionally, this research examines the restriction property of rPTSA, a crucial feature that prevents rPTSA from attaining Turing-completeness.</p> <br> <p>The practical contribution of this work is the development of the Probabilistic Tree-Stack Verifier (PTSV), an efficient tool for determining termination probability and expected termination time. Further attention is given to PAHORS and other key models, such as pPDA and MCFG. The study discusses the mutual conversions between rPTSA and PAHORS, as well as conversions from other models of interest, such as pPDA and Stochastic MCFG, to rPTSA.</p> |
| spellingShingle | Theoretical computer science Li, G Probabilistic verification beyond context-freeness |
| title | Probabilistic verification beyond context-freeness |
| title_full | Probabilistic verification beyond context-freeness |
| title_fullStr | Probabilistic verification beyond context-freeness |
| title_full_unstemmed | Probabilistic verification beyond context-freeness |
| title_short | Probabilistic verification beyond context-freeness |
| title_sort | probabilistic verification beyond context freeness |
| topic | Theoretical computer science |
| work_keys_str_mv | AT lig probabilisticverificationbeyondcontextfreeness |