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 : Monday 27 May 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |