Applications in enumerative combinatorics of infinite weighted automata and graphs

DOI10.7561/SACS.2014.1.137MaRDI QIDQ4621179zbMATH OpenOpenAlexFDO

Authors Rodrigo De Castro, Andrés Ramírez, José L. Ramírez

Publication date 8 February 2019

Published in Scientific Annals of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.2449

zbMATH Keywords

continued fractionsgenerating functionslattice pathsenumerative combinatoricsinfinite weighted automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics in computer science (68R05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Continued fractions (11A55) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: In this paper we studied infinite weighted automata and a general methodology to solve a wide variety of classical lattice path counting problems in an uniform way. This counting problems are related to Dyck paths, Motzkin paths and some generalizations. These methodology uses weighted automata, equations of ordinary generating functions and continued fractions. It is a variation of the one proposed by J. Rutten.

Recommendations

• scientific article; zbMATH DE number 2040325
• Coinductive counting: bisimulation in enumerative combinatorics (extended abstract)
• Automated counting of restricted Motzkin paths
• On the lattice path method in convolution-type combinatorial identities. II: The weighted counting function method on lattice paths
• Dyck path enumeration

Cited in

(10)

• Applications of automata and graphs: Labeling operators in Hilbert space. II.
• Some enumerations on non-decreasing Motzkin paths
• Enumeration of \(k\)-Fibonacci paths using infinite weighted automata
• Automated counting of restricted Motzkin paths
• Further results on paths in an \(n\)-dimensional cubic lattice
• Applications of the finite state automata for counting restricted permutations and variations
• Statistics on bargraphs of Catalan words
• scientific article; zbMATH DE number 2040325 (Why is no real title available?)
• Applications of the theory of automata in enumeration
• A refinement of Dyck paths: A combinatorial approach

This page was built for publication: Applications in enumerative combinatorics of infinite weighted automata and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621179)