Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata

DOI10.1007/s00453-019-00623-3zbMath1437.68091MaRDI QIDQ2292858

Axel Bacher, Bernhard Gittenberger, Andrei Asinowski, Cyril Banderier

Publication date: 6 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00623-3

zbMATH Keywords

generating functions; Markov chains; asymptotic analysis; kernel method; lattice paths; Motzkin paths; Wiener-Hopf factorization; finite automata; autocorrelation; Dyck paths; pattern avoidance; pushdown automata; Gaussian limit law; Łukasiewicz paths; Borges' theorem

Mathematics Subject Classification ID

05A15: Exact enumeration problems, generating functions

68Q45: Formal languages and automata

11B75: Other combinatorial number theory

05A16: Asymptotic enumeration

Uses Software

• OEIS