Résumé : Building upon the rule-algebraic stochastic mechanics framework, I will present a new approach to computing multi-variate generating function expressions in combinatorics. This approach is applicable for combinatorial structures which can be described as some initial configuration together with a generator (ideally uniform) whose repeated applications render the structures of increasing sizes. Unlike in species theory, computations in this approach are based upon the notion of rewriting rules, their sequential compositions and the so-called rule algebras (which encode information on the combinatorics of sequences of rewriting steps). I will introduce a computational strategy for determining multi-variate generating functions describing joint distributions of pattern counts in a species, namely via a form of ODE system obtained from the computation of certain commutators (of rules in the generator with rules implementing pattern counts). Some concrete results for the species of planar rooted binary trees will be presented for illustration. I will put a particular emphasis on an interesting open problem which concerns the existence of the aforementioned type of combinatorial evolution equations as seen in the planar rooted binary trees example. Reference: Nicolas Behr (2021). “On Stochastic Rewriting and Combinatorics via Rule-Algebraic Methods”. Invited Paper in Patrick Bahr (ed.): Proceedings 11th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2020), Online, 5th July 2020, Electronic Proceedings in Theoretical Computer Science 334, pp. 11–28. http://eptcs.web.cse.unsw.edu.au/paper.cgi?TERMGRAPH2020.2

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr