202503141903

Tags : Finite Model Theory, Logic

Unranked Trees in Logic

---

An Unranked Tree is a tree where each node can have different finite number of children.

Definition

A Tree Domain is a subset $D$ of ${\mathbb{N}}^{\ast }$ which is prefix closed such that for each $s\cdot i\in D$ we have $s\cdot j\in D$ for all $i\le j$.

A $\Sigma$-tree is defined as a tuple $(D,f)$ where $D$ is a tree-domain and $f:D\to \Sigma$ is a labelling function.

Unliked Ranked Trees it is no longer sufficient to have 2 successor relations as there are arbitrarily many children for each node, so we add further structure on to the tree.

$$M_T=⟨D,\prec ,(P_a{)}_{a\in \Sigma },{<}_{\text{sibl}}⟩$$

The structure added here is that there is an order relation on the sibling.

Definition

The set of trees that can be represented by a formula $\Phi$ for some logic is the set of trees that satisfy the formula

$$L_T(\Phi )=\{T\in \text{Treesq}(\Sigma )\mid M_T\models \Phi \}$$

---

References