# Closure under intersection of context free binary trees

Some sets of ordered binary trees can be represented as a CFG with rules of the form

A -> aBC
A -> b


Where A,B,C are nonterminals and a and b are terminals representing internal nodes and leaf nodes respectively. The tree can be recovered from any word in the language by a preorder traversal.

The set of all such grammars forms a class of languages which is a subset of context free languages but isomorphic to a superset of regular languages (by unary encoding the alphabet and adding a dummy terminal for the second nonterminal in every production). It is obviously closed under union as you can simply concatenate the lists of productions to get a new tree grammar.

My question is whether this class is closed under intersection. I have been unable to prove that is either closed or not closed, and I figured I should see if anyone else can see how to do this.

Then your formalism is known as regular tree grammars. A production $A \to a BC$ seems to label a tree node by $a$ while attaching children $B$ and $C$. This formalism is closed under intersection. This can be proved precisely as for finite state automata or right-linear grammars. Simulate the two in parallel, as a product construction. With productions $A \to_1 a BC$ and $P\to_2 a QR$ we join them to $(A,P) \to a (B,Q)(C,R)$ and $A \to_1 a$ and $P\to_2 a$ are joined to $(A,P)\to a$.