Formal language encoding WS2S and closed under complementation.

Question

It is known that the relations encoded in WS1S are also represented by the words accepted by certain finite automata and thus can be represented as regular languages.

A similar connection holds between WS2S, tree automata and context-free languages (see the work of Doner "Tree acceptors...").

However, context-free languages are not closed under complementation.

Is there a formal language that "represents" the relations of WS2S and yet it is closed under union, intersection and complementation?

Answer 1

You'll want to look into regular languages of trees https://en.wikipedia.org/wiki/Tree_automaton. The basic idea is that just as you can index a position within a word by a natural number, you can index a position within a rooted binary tree with ordered children (child nodes are always left-children or right-children) by a first-order element of WS2S. Here the two successor operations operate on the nodes of trees and are left-child and right-child. So a first-order element of WS2S describes the path to navigate to a node from the root node.

So the thing that corresponds to a word in the WS2S case is a rooted binary tree with ordered children whose nodes are labeled with characters from some finite alphabet. Given such a tree, we get an element of WS2S for each character that's just "the set of positions in the tree where this character occurs".

A regular tree expression (I'm looking at Downey and Fellows' "Parameterized Complexity" Definition 6.39, but you can also find this in Gecseg and Steinby's "Tree Automata" (https://arxiv.org/abs/1509.06233) definition 2.5.1) is constructed recursively:

Starting from:

• the empty set ($\emptyset$)
• for each character $a \in \Sigma$, the language which is just a one-node tree with that node labeled $a$ (denoted $a$)

Freely apply the following operations: $L, W$ regular tree languages, $a$ a character in $\Sigma$:

• $L \cdot_a W$: for each labeled tree $T$ in $W$, replace all leaves with the label $a$ by (potentially different) labeled trees in $L$.
• $L^{*a} = \bigcup_{n \geq 1} \underbrace{L \cdot_a \cdots \cdot_a L}_{n}$
• $L \odot_a W$: for each labeled tree $T_1 \in L, T_2 \in W$, construct a tree with root labeled by $a$ and children $T_1$ and $T_2$.
• $L + W$: union