5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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 $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$.

$\endgroup$
  • $\begingroup$ Thanks! I hadn't heard of the term Regular Tree Grammars, so I had trouble searching online for it. $\endgroup$ – Antimony Apr 7 '13 at 21:37
  • $\begingroup$ By the way, is there anything known about RTG minimization? $\endgroup$ – Antimony Apr 8 '13 at 2:06
  • $\begingroup$ See Tree Automata Techniques and Applications linked in Wikipedia's lemma on regular tree grammars. "TATA" is an online book, a great reference on the topic. Chapter 1 has a section Minimizing Tree Automata. I guess that is what you need. $\endgroup$ – Hendrik Jan Apr 8 '13 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.