  This paper introduces 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
most natural nondeterministic step sets (Dyck and Motzkin step sets), 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.
  Keywords. Random walks, analytic combinatorics, generating functions, limit
laws, networking, encapsulation.
