First we have to extend the level synchronization product R× ? S of any grammars R £ S in order to retain a path for all the words accepted by R. We take a new colour ? 1 and for? whose R ? 1 /? is obtained from R by replacing ? by ? 1 . The grammar R S satisfies (R S ) ?,? 1 ,? 1 £¡ R) for S ¡ R is the set of non accepting words labelling initial paths in (R S ) ? which end in a vertex coloured by ? 1 or ?, Closure under complement We now consider the closure under complement of Sync ) ?,? 1 ,? 1 ) ? L(R S ) = L((R S ) ? 1 ,? 1 ) ? L(R S ) ,
? 0 is unambiguous, the language L(R ? 0 ) ? L(R) is the set of words which label paths ending in non final vertices coloured by ? 0 ,
? 1 is level-unambiguous when R is, we get the closure under complement of Sync(R) using Lemmas 13 ,
Synchronization of grammars, 3 rd CSR, LNCS, vol.5010, pp.110-121, 2008. ,
On the complexity of membership and counting in height-deterministic pushdown automata, 3 rd CSR, LNCS, vol.5010, pp.240-251, 2008. ,
The theory of ends, pushdown automata, and second-order logic, Theoretical Computer Science, vol.37, pp.51-75, 1985. ,
DOI : 10.1016/0304-3975(85)90087-8