Linear context-free tree languages and inverse homomorphisms (Q2280337)

The contribution shows that the linear context-free tree languages are not closed under inverse linear tree homomorphisms, whereas this closure holds for monadic linear context-free tree languages. A tree language is linear context-free if there exists a linear context-free tree grammar that generates it. Such a grammar is essentially a regular tree grammar in which the nonterminals can occur at internal positions of a tree and can reference the subtrees below it. However, the linearity restriction ensures that only a single reference to each subtree is possible. Similarly, a tree homomorphism maps each symbol to a tree with references to the translations of the subtrees. Again the linearity restriction enforces that only a single reference to each translated subtree is possible. The main result shows that there exists a linear context-free tree language \(L\) together with a linear tree homomorphism \(h\) such that the preimage \(h^{-1}(L)\) of \(L\) via \(h\) cannot be generated by any (i.e., even nonlinear) context-free tree grammar. In the monadic case, the nonterminals of the grammar are restricted to rank \(1\), so they have only a single subtree. With this additional restriction the mentioned closure holds true, so if \(L\) is generated by a monadic linear context-free tree grammar, also \(h^{-1}(L)\) can be generated by a linear context-free tree grammar. The approach first presents a special linear context-free tree language \(L\) in whose trees chains of unary symbols hang off a single spine and those chains enjoy strong synchronization properties (for each occurrence of the unary symbol `c' in chain \(1\), there is a corresponding occurrence of unary symbol `d' in chain \(4\)). These chains are grouped in neighboring pairs, but all nested along the same spine (using binary branching). The inverse linear tree homomorphism is designed such that it will partially flatten this structure and will group a pair of these chains below a single symbol of rank \(3\). Next, the authors develop normal forms for each context-free tree grammar that can potentially generate this preimage. This normal form then allows them to prove that no context-free tree grammar can actually generate the preimage. The positive result for monadic linear context-free tree grammars is established by means of an effective construction of a linear context-free tree grammar for the preimage. Overall, the contribution is exceptionally well written but presupposes significant exposure to tree language theory (context-free tree languages, tree homomorphisms, etc.). Examples, illustrations, and intuition are generously provided and are always helpful. The proofs are elementary, but the discussed notions are rather intricate.