On the Computability of Measures of Regular Sets of Infinite Trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913582043627520 |
|---|---|
| author | Niwiński, Damian Parys, Paweł Skrzypczak, Michał |
| author_facet | Niwiński, Damian Parys, Paweł Skrzypczak, Michał |
| contents | The Rabin tree theorem yields an algorithm to solve the satisfiability problem for monadic second-order logic over infinite trees. Here we solve the probabilistic variant of this problem. Namely, we show how to compute the probability that a randomly chosen tree satisfies a given formula. We additionally show that this probability is an algebraic number. This closes a line of research where similar results were shown for formalisms weaker than the full monadic second-order logic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12158 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Computability of Measures of Regular Sets of Infinite Trees Niwiński, Damian Parys, Paweł Skrzypczak, Michał Logic in Computer Science The Rabin tree theorem yields an algorithm to solve the satisfiability problem for monadic second-order logic over infinite trees. Here we solve the probabilistic variant of this problem. Namely, we show how to compute the probability that a randomly chosen tree satisfies a given formula. We additionally show that this probability is an algebraic number. This closes a line of research where similar results were shown for formalisms weaker than the full monadic second-order logic. |
| title | On the Computability of Measures of Regular Sets of Infinite Trees |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2304.12158 |