Some properties of multiple context-free languages (Murray Elder, University of Technology Sydney)

12.03.2024 10:30

I will explain what multiple context-free languages are, giving both grammar and machine (informal) definitions. I will then explain a new \emph{swapping lemma} for proving that a language is not multiple context-free, and apply it to some examples, including the word problem of $F_2\times \mathbb Z$. I will also explain our result that \emph{permutation closure} of a multiple context-free is multiple context-free, which complements work of Brandst\"adt (resp. Brough \emph{et al.}) who showed the same result for regular, context-sensitive, recursively enumerable (resp. EDT0L and ET0L) languages.
Both results exploit the machine definition.

Lieu

Bâtiment: Conseil Général 7-9

Room 1-05,Tuesday 12.03.2024, Séminaire "Groupes et Géométrie"

entrée libre