R. , R. £. We-define, R. S. , £. , and ?. {@bullet, 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 )

R. When-a-grammar and . @bullet, ? 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

. (. As, ? 1 is level-unambiguous when R is, we get the closure under complement of Sync(R) using Lemmas 13

]. D. Caucal and S. Hassen, Synchronization of grammars, 3 rd CSR, LNCS, vol.5010, pp.110-121, 2008.

N. Limaye, M. Mahajan, and A. Meyer, On the complexity of membership and counting in height-deterministic pushdown automata, 3 rd CSR, LNCS, vol.5010, pp.240-251, 2008.

P. D. Muller and . Schupp, 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