Abstract:
Motivated by the study of networks involving encapsulation and decapsulation of protocols, 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. In the first part of the talk, 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. In the scond part, we extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic.

Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics. This is joint work with Élie de Panafieu and Mohamed Lamine Lamali.