[Solved]: Closure under intersection of context free binary trees

Problem Detail: 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.

Asked By : Antimony

Answered By : Hendrik Jan

If I correctly read your question there are two types of terminal symbols, disjoint sets for internal labels and leaf labels. In that way the structure of the tree is uniquely determined by the string. 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 $Pto_2 a QR$ we join them to $(A,P) to a (B,Q)(C,R)$ and $A to_1 a$ and $Pto_2 a$ are joined to $(A,P)to a$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11114 Ask a Question Download Related Notes/Documents