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||Contact : Cyril.Banderier at lipn.univ-paris13.fr|