Résumé : We introduce nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. We discuss in detail the nondeterministic Dyck step set $\{ \{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$, and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. We extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. We conjecture the same is true for nondeterministic excursions, and we present python and Maple packages to support our conjecture. This research is motivated by the study of networks involving encapsulation and decapsulation of protocols. Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics. Joint work with Élie de Panafieu.
| Dernière modification : Monday 18 March 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |