Random expansions of trees with bounded height
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908302145748992 |
|---|---|
| author | Koponen, Vera Tousinejad, Yasmin |
| author_facet | Koponen, Vera Tousinejad, Yasmin |
| contents | We consider a sequence $\mathbf{T} = (\mathcal{T}_n : n \in \mathbb{N}^+)$ of trees $\mathcal{T}_n$ where, for some $Δ\in \mathbb{N}^+$ every $\mathcal{T}_n$ has height at most $Δ$ and as $n \to \infty$ the minimal number of children of a nonleaf tends to infinity. We can view every tree as a (first-order) $τ$-structure where $τ$ is a signature with one binary relation symbol. For a fixed (arbitrary) finite and relational signature $σ\supseteq τ$ we consider the set $\mathbf{W}_n$ of expansions of $\mathcal{T}_n$ to $σ$ and a probability distribution $\mathbb{P}_n$ on $\mathbf{W}_n$ which is determined by a (parametrized/lifted) Probabilistic Graphical Model (PGM) $\mathbb{G}$ which can use the information given by $\mathcal{T}_n$.
The kind of PGM that we consider uses formulas of a many-valued logic that we call $PLA^*$ with truth values in the unit interval $[0, 1]$. We also use $PLA^*$ to express queries, or events, on $\mathbf{W}_n$. With this setup we prove that, under some assumptions on $\mathbf{T}$, $\mathbb{G}$, and a (possibly quite complex) formula $φ(x_1, \ldots, x_k)$ of $PLA^*$, as $n \to \infty$, if $a_1, \ldots, a_k$ are vertices of the tree $\mathcal{T}_n$ then the value of $φ(a_1, \ldots, a_k)$ will, with high probability, be almost the same as the value of $ψ(a_1, \ldots, a_k)$, where $ψ(x_1, \ldots, x_k)$ is a ``simple'' formula the value of which can always be computed quickly (without reference to $n$), and $ψ$ itself can be found by using only the information that defines $\mathbf{T}$, $\mathbb{G}$ and $φ$. A corollary of this, subject to the same conditions, is a probabilistic convergence law for $PLA^*$-formulas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11775 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random expansions of trees with bounded height Koponen, Vera Tousinejad, Yasmin Logic in Computer Science 03C13, 03C80, 03C98, 03B42, 03B70, 68T27, 68T30 F.4 We consider a sequence $\mathbf{T} = (\mathcal{T}_n : n \in \mathbb{N}^+)$ of trees $\mathcal{T}_n$ where, for some $Δ\in \mathbb{N}^+$ every $\mathcal{T}_n$ has height at most $Δ$ and as $n \to \infty$ the minimal number of children of a nonleaf tends to infinity. We can view every tree as a (first-order) $τ$-structure where $τ$ is a signature with one binary relation symbol. For a fixed (arbitrary) finite and relational signature $σ\supseteq τ$ we consider the set $\mathbf{W}_n$ of expansions of $\mathcal{T}_n$ to $σ$ and a probability distribution $\mathbb{P}_n$ on $\mathbf{W}_n$ which is determined by a (parametrized/lifted) Probabilistic Graphical Model (PGM) $\mathbb{G}$ which can use the information given by $\mathcal{T}_n$. The kind of PGM that we consider uses formulas of a many-valued logic that we call $PLA^*$ with truth values in the unit interval $[0, 1]$. We also use $PLA^*$ to express queries, or events, on $\mathbf{W}_n$. With this setup we prove that, under some assumptions on $\mathbf{T}$, $\mathbb{G}$, and a (possibly quite complex) formula $φ(x_1, \ldots, x_k)$ of $PLA^*$, as $n \to \infty$, if $a_1, \ldots, a_k$ are vertices of the tree $\mathcal{T}_n$ then the value of $φ(a_1, \ldots, a_k)$ will, with high probability, be almost the same as the value of $ψ(a_1, \ldots, a_k)$, where $ψ(x_1, \ldots, x_k)$ is a ``simple'' formula the value of which can always be computed quickly (without reference to $n$), and $ψ$ itself can be found by using only the information that defines $\mathbf{T}$, $\mathbb{G}$ and $φ$. A corollary of this, subject to the same conditions, is a probabilistic convergence law for $PLA^*$-formulas. |
| title | Random expansions of trees with bounded height |
| topic | Logic in Computer Science 03C13, 03C80, 03C98, 03B42, 03B70, 68T27, 68T30 F.4 |
| url | https://arxiv.org/abs/2410.11775 |