Journée-séminaire de combinatoire

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

Le 26 novembre 2019 à 14h00 en B107, Massimiliano Goldwurm nous parlera de : Analysis of algorithms for membership problems on trace languages

Résumé : A classical problem over trace monoids is the recognition of rational trace languages. This problem can be solved in a time proportional to the number of prefixes of the input trace. In this talk I will present some results on the number of prefixes of a trace of length n in the worst case and in the average case under suitable probabilistic assumptions. I will also discuss other results concerning the variance, the moments and the limit distribution of the corresponding random variables.


Dernière modification : Sunday 24 November 2019 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at