pith. sign in

arxiv: 2311.03234 · v2 · submitted 2023-11-06 · 🧮 math.CO · cs.DM· cs.FL· cs.NI

Combinatorics of nondeterministic walks

\'Elie de Panafieu , Michael Wallner This is my paper

Pith reviewed 2026-05-24 05:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.FLcs.NI
keywords nondeterministic walkslattice pathsalgebraic generating functionsbridgesmeandersexcursionsanalytic combinatoricsreachable points
0
0 comments X

The pith

Nondeterministic walks on the line are algebraic for bridges and meanders once the endpoint is replaced by the full set of reachable points.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines nondeterministic walks so that each step is a set of possible moves explored simultaneously rather than a single choice. It proves that the generating functions counting nondeterministic bridges remain algebraic for any underlying step set, and that the same holds for several natural subclasses of meanders. The central device is the reachable-points set, which replaces the classical single endpoint and keeps the equations algebraic. The authors conjecture algebraicity also for nondeterministic excursions and supply software to test the claim on concrete families. The work is motivated by counting behaviors in networks that encapsulate and decapsulate protocols.

Core claim

Nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. The same is conjectured for nondeterministic excursions. These statements hold first for Dyck and Motzkin step sets and then for arbitrary step sets; the proofs rely on generating functions, analytic combinatorics, and additive combinatorics once the single ending height is replaced by the set of all reachable heights.

What carries the argument

The reachable-points set: the collection of all heights that can be reached after a given sequence of nondeterministic steps, which replaces the classical single endpoint in the generating-function equations.

If this is right

  • Nondeterministic bridges admit algebraic generating functions for every finite step set.
  • Several natural subclasses of nondeterministic meanders are algebraic.
  • The same algebraicity is expected for nondeterministic excursions, backed by computational evidence.
  • The reachable-points construction extends directly from Dyck and Motzkin steps to arbitrary steps while preserving algebraicity for bridges.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reachable-set technique may produce algebraic counts for other nondeterministic objects such as walks on graphs or higher-dimensional lattices.
  • If the conjecture holds, the software packages can be used to extract limit laws and asymptotic densities for the conjectured algebraic cases.
  • Protocol-network models that motivated the work could be re-expressed directly as nondeterministic excursions or meanders.

Load-bearing premise

Switching from a single ending height to the full set of reachable heights keeps the generating functions algebraic for the listed walk classes.

What would settle it

An explicit step set for which the ordinary generating function of nondeterministic bridges is proved non-algebraic.

Figures

Figures reproduced from arXiv: 2311.03234 by \'Elie de Panafieu, Michael Wallner.

Figure 1
Figure 1. Figure 1: Geometric realization of the classical meander [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The bijection of Dyck N-walks to two-dimensional lattice paths transforms the N-steps [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An N-Dyck meander corresponds to a two-dimensional walk with an absorbing [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of theoretical expectation and averaged simulation (over [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The law of the final maximal point of an N-excursion from Theorem [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Maximum point reached at the end according to path length (left) and returns to [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The automaton representing the structure of reachable points of Motzkin N-walks. [PITH_FULL_IMAGE:figures/full_fig_p021_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The automaton representing the structure of reachable points of Motzkin N-meanders. [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Type transition matrices involved in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Number of returns to 0 according to path length (averaged simulation over 105 runs) of Dyck N-excursions. 0 20 40 60 80 100 20 40 60 80 100 120 140 160 180 200 Maximum at the end Path length p1 = p−1 = 1/3 p1 = 1/2, p−1 = 1/4 p1 = 1/4, p−1 = 1/2 sqrtn (a) Short paths (from 0 to 200) 0 500 1000 1500 2000 500 1000 1500 2000 2500 3000 3500 4000 Maximum at the end Path length p1 = p−1 = 1/3 p1 = 1/2, p−1 = 1/… view at source ↗
Figure 11
Figure 11. Figure 11: Maximum point reached at the end according to path length (averaged simulation over [PITH_FULL_IMAGE:figures/full_fig_p047_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Number of times max = 0. 48 [PITH_FULL_IMAGE:figures/full_fig_p048_12.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. This paper introduces nondeterministic walks, a variant of one-dimensional lattice paths in which each step is a set of steps from a fixed step set, with all extensions explored in parallel. The central technical device is replacing the single ending position by the set of reachable positions. For Dyck and Motzkin step sets the authors establish algebraicity of the generating functions for bridges, excursions and meanders. They extend the algebraicity claim to arbitrary step sets for bridges and several subclasses of meanders, conjecture the same for excursions, and supply Python and Maple packages that computationally support the conjecture. The work is motivated by protocol encapsulation networks and employs generating functions together with additive combinatorics.

Significance. If the algebraicity statements hold, the manuscript supplies a new family of algebraic generating functions inside analytic combinatorics and demonstrates that the reachable-set construction preserves algebraicity for the listed classes. The explicit release of verification packages is a concrete strength that permits independent checking of the computational evidence for the excursion conjecture.

major comments (2)
  1. [section extending results to general step sets] The claim that nondeterministic bridges remain algebraic for arbitrary step sets (abstract and the section extending results to general step sets) rests on the reachable-points construction producing a finite collection of states whose transition rules yield an algebraic system. No explicit argument is given that the attainable subsets of integers remain finite when the underlying step set is arbitrary; for Dyck/Motzkin steps the reachable sets are intervals and finiteness is immediate, but the general case is not addressed. This finiteness is load-bearing for the “always algebraic” assertion.
  2. [conjecture statement and computational support] The conjecture that nondeterministic excursions are algebraic for general step sets is supported only computationally. The manuscript supplies no partial analytic result, kernel-equation analysis, or state-space bound that would indicate why the reachable-set system stays algebraic in the excursion case, leaving the central conjecture without a clear path to proof.
minor comments (2)
  1. The abstract states that “several subclasses of nondeterministic meanders” are algebraic but does not name the subclasses; an explicit list or reference to the relevant theorem should appear in the introduction.
  2. A compact table summarizing which classes are proved algebraic, which are conjectured, and for which step sets would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting points that require clarification or strengthening. We respond to each major comment below.

read point-by-point responses

  1. Referee: [section extending results to general step sets] The claim that nondeterministic bridges remain algebraic for arbitrary step sets (abstract and the section extending results to general step sets) rests on the reachable-points construction producing a finite collection of states whose transition rules yield an algebraic system. No explicit argument is given that the attainable subsets of integers remain finite when the underlying step set is arbitrary; for Dyck/Motzkin steps the reachable sets are intervals and finiteness is immediate, but the general case is not addressed. This finiteness is load-bearing for the “always algebraic” assertion.

    Authors: We agree that the manuscript does not supply an explicit argument establishing finiteness of reachable subsets for arbitrary finite step sets. In the revised version we will add a short subsection in the general-step-sets section that proves the reachable point sets remain finite for bridges: any reachable set is contained in an interval whose length is bounded by the diameter of the step set and the number of steps needed to return to the origin in the additive sense, using standard facts from additive combinatorics on finite generating sets. revision: yes

  2. Referee: [conjecture statement and computational support] The conjecture that nondeterministic excursions are algebraic for general step sets is supported only computationally. The manuscript supplies no partial analytic result, kernel-equation analysis, or state-space bound that would indicate why the reachable-set system stays algebraic in the excursion case, leaving the central conjecture without a clear path to proof.

    Authors: The manuscript presents the algebraicity of excursions for general step sets explicitly as a conjecture, supported by the computational evidence in the released Python and Maple packages. We do not possess a partial analytic result, kernel analysis, or state-space bound at this time; the conjecture is offered precisely because such a proof is currently unavailable. The computational verification remains a concrete contribution as stated. revision: no

Circularity Check

0 steps flagged

No circularity: algebraicity claims rest on independent generating-function analysis of reachable-point models.

full rationale

The paper introduces nondeterministic walks via the reachable-points generalization and applies standard generating-function and analytic-combinatorics techniques to establish algebraicity for bridges and selected meander subclasses. No equations, definitions, or claims reduce the target result to a fitted parameter, self-citation, or ansatz imported from the authors' prior work; the derivation is presented as self-contained and externally motivated by protocol networks. The skeptic concern addresses potential correctness of the finite-state argument for general steps but does not exhibit a definitional or constructional reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the applicability of standard generating-function and analytic-combinatorics machinery to the newly defined objects; no numerical free parameters are mentioned, and the only invented entity is the nondeterministic walk itself.

axioms (1)
  • domain assumption Standard techniques of generating functions and analytic combinatorics extend directly to the reachable-points formulation of nondeterministic walks.
    Invoked when the authors state that the key concept is the generalization to reachable points and then conclude algebraicity.
invented entities (1)
  • nondeterministic walk no independent evidence
    purpose: Model parallel exploration of multiple steps at once, motivated by protocol encapsulation networks.
    New object introduced in the paper; no independent falsifiable prediction outside the combinatorics results is supplied.

pith-pipeline@v0.9.0 · 5729 in / 1524 out tokens · 32537 ms · 2026-05-24T05:53:37.906022+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    Analytic combi- natorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata.Algorithmica, 82(3):386–428, 2020

    Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic combi- natorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata.Algorithmica, 82(3):386–428, 2020. 40

    work page 2020

  2. [2]

    Basic analytic combinatorics of directed lattice paths

    Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science, 281(1–2):37 – 80, 2002

    work page 2002

  3. [3]

    Springer, Cham, 2019

    Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Nguyen, and Michael Wallner.Explicit Formulas for Enumeration of Lattice Paths: Basketball and the Kernel Method, volume 58 ofDevelopments in Mathematics, pages 78–118. Springer, Cham, 2019. [doi]

    work page 2019

  4. [4]

    Latticepathology and Symmetric Functions (Extended Abstract)

    Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). InAofA 2020, volume 159 ofLIPIcs, pages 2:1–2:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. [doi]

    work page 2020

  5. [5]

    Some reflections on directed lattice paths

    Cyril Banderier and Michael Wallner. Some reflections on directed lattice paths. InProceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, pages 25–36, 2014

    work page 2014

  6. [6]

    Lattice paths with catastrophes.Discrete Mathematics & Theoretical Computer Science, Vol 19 no

    Cyril Banderier and Michael Wallner. Lattice paths with catastrophes.Discrete Mathematics & Theoretical Computer Science, Vol 19 no. 1, September 2017

    work page 2017

  7. [7]

    Springer, Cham,

    Cyril Banderier and Michael Wallner.The kernel method for lattice paths below a line of rational slope, volume 58 ofDevelopments in Mathematics, pages 119–154. Springer, Cham,

    work page

  8. [8]

    Exact solution of some quarter plane walks with interacting boundaries.arXiv preprint arXiv:1807.08853, 2018

    Nicholas R Beaton, Aleksander L Owczarek, and Andrew Rechnitzer. Exact solution of some quarter plane walks with interacting boundaries.arXiv preprint arXiv:1807.08853, 2018

    work page arXiv 2018

  9. [9]

    Beaton, Aleksander L

    Nicholas R. Beaton, Aleksander L. Owczarek, and Ruijie Xu. Quarter-plane lattice paths with interacting boundaries: Kreweras and friends.Sém. Lothar. Combin., 82B:Art. 26, 12, 2020

    work page 2020

  10. [10]

    Polynomial equations with one catalytic variable, algebraic series and map enumeration.J

    Mireille Bousquet-Mélou and Arnaud Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration.J. Combin. Theory Ser. B, 96(5):623–672,

    work page

  11. [11]

    Walks with small steps in the quarter plane

    Mireille Bousquet-Mélou and Marni Mishna. Walks with small steps in the quarter plane. In Algorithmic probability and combinatorics, volume 520 ofContemp. Math., pages 1–39. Amer. Math. Soc., Providence, RI, 2010. [doi]

    work page 2010

  12. [12]

    Culminating paths.Discrete Math

    Mireille Bousquet-Mélou and Yann Ponty. Culminating paths.Discrete Math. Theor. Comput. Sci., 10(2):125–152, 2008

    work page 2008

  13. [13]

    Inhomogeneous Restricted Lattice Walks

    Manfred Buchacher and Manuel Kauers. Inhomogeneous restricted lattice walks. arXiv preprint arXiv:1811.06725, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  14. [14]

    Courtiel, S

    J. Courtiel, S. Melczer, M. Mishna, and K. Raschel. Weighted lattice walks and universality classes. J. Combin. Theory Ser. A, 152:255–302, 2017. [doi]

    work page 2017

  15. [15]

    Combinatorics of nondeter- ministic walks of the Dyck and Motzkin type

    Élie de Panafieu, Mohamed Lamine Lamali, and Michael Wallner. Combinatorics of nondeter- ministic walks of the Dyck and Motzkin type. InANALCO 2019, pages 1–12, 2019

    work page 2019

  16. [16]

    Walks in the quarter plane, genus zero case.arXiv preprint arXiv:1710.02848, 2017

    Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F Singer. Walks in the quarter plane, genus zero case.arXiv preprint arXiv:1710.02848, 2017. 41

    work page arXiv 2017

  17. [17]

    Images and preimages in random mappings.SIAM Journal on Discrete Mathematics, 10(2):246–269, 1997

    Michael Drmota and Michèle Soria. Images and preimages in random mappings.SIAM Journal on Discrete Mathematics, 10(2):246–269, 1997

    work page 1997

  18. [18]

    On the enumeration and generation of generalized Dyck words.Discrete Math., 225(1-3):121–135, 2000

    Philippe Duchon. On the enumeration and generation of generalized Dyck words.Discrete Math., 225(1-3):121–135, 2000

    work page 2000

  19. [19]

    Cambridge University Press, 2009

    Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics. Cambridge University Press, 2009

    work page 2009

  20. [20]

    Ira M. Gessel. A factorization for formal Laurent series and lattice path enumeration.J. Combin. Theory Ser. A, 28(3):321–337, 1980. [doi]

    work page 1980

  21. [21]

    Higher-order Airy scaling in deformed Dyck paths

    Nils Haug, Adri Olde Daalhuis, and Thomas Prellberg. Higher-order Airy scaling in deformed Dyck paths. Journal of Statistical Physics, pages 1–16, 2017. [doi]

    work page 2017

  22. [22]

    On convergence rates in the central limit theorems for combinatorial structures

    Hsien-Kuei Hwang. On convergence rates in the central limit theorems for combinatorial structures. European J. Combin., 19(3):329–343, 1998. [doi]

    work page 1998

  23. [23]

    Janse van Rensburg, Thomas Prellberg, and Andrew Rechnitzer

    Esaias J. Janse van Rensburg, Thomas Prellberg, and Andrew Rechnitzer. Partially directed paths in a wedge.J. Combin. Theory Ser. A, 115(4):623–650, 2008

    work page 2008

  24. [24]

    Donald E. Knuth. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley, 1968

    work page 1968

  25. [25]

    Path computation in multi-layer networks: Complexity and algorithms

    Mohamed Lamine Lamali, Nasreddine Fergani, Johanne Cohen, and Hélia Pouyllau. Path computation in multi-layer networks: Complexity and algorithms. InIEEE INFOCOM 2016, San Francisco, CA, USA, April 10-14, 2016, pages 1–9, 2016

    work page 2016

  26. [26]

    Lipshitz

    L. Lipshitz. The diagonal of aD-finite power series isD-finite. J. Algebra, 113(2):373–378,

    work page

  27. [27]

    Donatella Merlini, D. G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri. Underdiagonal lattice paths with unrestricted steps.Discrete Appl. Math., 91(1-3):197–213, 1999. [doi]

    work page 1999

  28. [28]

    Two non-holonomic lattice walks in the quarter plane

    Marni Mishna and Andrew Rechnitzer. Two non-holonomic lattice walks in the quarter plane. Theoret. Comput. Sci., 410(38-40):3616–3630, 2009. [doi]

    work page 2009

  29. [29]

    RFC7582 - multicast virtual private network (mvpn): Using bidirectional p-tunnels, 2015

    E Rosen, IJ Wijnands, Y Cai, and A Boers. RFC7582 - multicast virtual private network (mvpn): Using bidirectional p-tunnels, 2015

    work page 2015

  30. [30]

    RFC4301 - security architecture for the internet protocol, 2005

    Karen Seo and Stephen Kent. RFC4301 - security architecture for the internet protocol, 2005

    work page 2005

  31. [31]

    Tabbara, A

    R. Tabbara, A. L. Owczarek, and A. Rechnitzer. An exact solution of two friendly interacting directed walks near a sticky wall.J. Phys. A, 47(1):015202, 34, 2014. [doi]

    work page 2014

  32. [32]

    Cambridge University Press, Cambridge, 2006

    Terence Tao and Van Vu.Additive combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. [doi]

    work page 2006

  33. [33]

    Transition from IPv4 to IPv6: A state-of-the-art survey.IEEE Communications Surveys & Tutorials, 15(3):1407–1424, 2013

    Peng Wu, Yong Cui, Jianping Wu, Jiangchuan Liu, and Chris Metz. Transition from IPv4 to IPv6: A state-of-the-art survey.IEEE Communications Surveys & Tutorials, 15(3):1407–1424, 2013. 42 A Subclasses of Motzkin N-walks in the OEIS In Theorem 3.7 we have characterized the generating function of Motzkin N-meandersM +(x,y ;t) and proved that it is always alg...

    work page 2013