Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 29 mars 2016 à 11h00 en B107, Alexander Meduna nous parlera de : Regulated Grammars and Automata

Résumé : This talk explains the gist underlying regulated grammars and automata as well as the main purpose of their investigation. This investigation is classified into four major topics--the study of their power, properties, reduction, and mutual convertibility. The talk illustrates this inevstigation by a case study in terms of one-sided random-context grammars. Most importantly, it points out that propagating versions of one-sided random-context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Open problem areas are formulated.


Dernière modification : vendredi 01 avril 2016 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at