Notes on 1-Range Concatenation Grammars

Some quick notes on 1-RCGs after a first skim through Boullier (2000)'s paper.

Boolean Closure of Context-Free Languages

A striking aspect of 1-RCGs is how close to defining exactly the boolean closure of CFLs (Bool(CFL)) they seem to be. Thanks to their closure by intersection and complement and their inclusion of CFLs, 1-RCLs (actually proper 1-RCLs) clearly include Bool(CFL).

The inclusion is however proper. Using the results of Kutrib et al. (2004, Theorem 17), we can exploit the semilinearity of some languages in Bool(CFL) to show that the language

ℒ_exp = { aⁿb²ⁿ | 0 ≤ n }.

is not in Bool(CFL).

Nevertheless, I think we can generate this language with the 1-RCG

S(aXYZ) → S(XY) S(XZ) A(X) B(YZ)
S(b) → ε
A(aX) → A(X)
A(ε) → ε
B(bXb) → B(X)
B(bb) → ε

This grammar is not a proper 1-RCG: the calls to S(XY) and S(XZ) use two variables in a right-hand side predicate, without any clear way to obtain the same effect with only one variable. The class of languages generated by proper 1-RCGs would probably deserve to be further compared to Bool(CFL).

Tree Adjoining Languages

Boullier (2000) indicates that it is unknown, albeit very unlikely, whether any tree adjoining language could be expressed using a proper 1-RCG. I am really not sure about this, but I wondered whether the language

ℒ_palcopy = { ww^Rww^R | w ∈ {a,b}^* }

could not be a good candidate for a counter-example.