Applications in enumerative combinatorics of infinite weighted automata and graphs

DOI10.7561/SACS.2014.1.137zbMATH Open1424.05151arXiv1310.2449OpenAlexW2963737578MaRDI QIDQ4621179FDOQ4621179

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)

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.

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

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

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)

Cited In (10)

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

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)