Weakly prudent self-avoiding bridges

Autor: Axel Bacher, Nicholas Beaton

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AT,..., Iss Proceedings (2014)

We define and enumerate a new class of self-avoiding walks on the square lattice, which we call weakly prudent bridges. Their definition is inspired by two previously-considered classes of self-avoiding walks, and can be viewed as a combination of th

Externí odkaz: https://doaj.org/article/edc1cc6cf96b40aa9d83e0800fd7e6a3

Efficient random sampling of binary and unary-binary trees via holonomic equations

Autor: Alice Jacquot, Axel Bacher, Olivier Bodini

Publikováno v: Theoretical Computer Science. 695:42-53

We present a new uniform random sampler for binary trees with n internal nodes consuming 2 n + Θ ( log ⁡ ( n ) 2 ) random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for una

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b3ba83e17166adbb131d02b51638b76
https://doi.org/10.1016/j.tcs.2017.07.009

Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects

Autor: Cyril Banderier, Bernhard Gittenberger, Andrei Asinowski, Axel Bacher

Publikováno v: Lecture Notes in Computer Science
Lecture Notes in Computer Science, Springer, 2018, Proceedings of the 12th International Conference on Language and Automata Theory and Applications, 10792, pp.195-206
Language and Automata Theory and Applications ISBN: 9783319773124
LATA

This article presents a powerful method for the enumeration of pattern-avoiding words generated by an automaton or a context-free grammar. It relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. Due to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c97fe7894581a330bd47a18a4503ca34
https://hal.archives-ouvertes.fr/hal-02414212

Complexity of Anticipated Rejection Algorithms and the Darling-Mandelbrot Distribution

Autor: Andrea Sportiello, Axel Bacher

We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is line

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d64228cf961ece1e8289f490f6700025
http://arxiv.org/abs/1508.05634

Directed and multi-directed animals on the King's lattice

Autor: Axel Bacher

Publikováno v: The Seventh European Conference on Combinatorics, Graph Theory and Applications
EuroComb 2013
EuroComb 2013, Sep 2013, Pise, Italy. pp 535-541, ⟨10.1007/978-88-7642-475-5_84⟩
The Seventh European Conference on Combinatorics, Graph Theory and Applications ISBN: 9788876424748

This article introduces a new, simple solvable lattice for directed animals: the directed king's lattice, or square lattice with next nearest neighbor bonds and preferred directions {W, NW, N, NE, E}. We show that the directed animals in this lattice

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a5f4d381534629629987dedc46c95ae7
https://hal.archives-ouvertes.fr/hal-00989608/file/175.pdf