Counting and generating permutations in regular classes

DOI10.1007/s00453-016-0136-9zbMath1352.05005OpenAlexW2301044752MaRDI QIDQ727971

Nicolas Basset

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0136-9

zbMATH Keywords

timed automataexponential generating functionBoltzmann samplingregular class of permutationssignature of a permutationuniform random sampling

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Young tableaux with periodic walls: counting with the density method ⋮ Rollercoasters and Caterpillars ⋮ Rollercoasters: Long Sequences without Short Runs

Uses Software

• SageMath
• SymPy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Algorithms for combinatorial structures: well-founded systems and Newton iterations
• A spectral approach to consecutive pattern-avoiding permutations
• Patterns in permutations and words.
• Permutations ayant une forme donnée
• Two poset polytopes
• Uniform random generation of decomposable structures using floating-point arithmetic
• A theory of timed automata
• A calculus for the random generation of labelled combinatorial structures
• Consecutive patterns in permutations
• Descent pattern avoidance
• On the frequencies of patterns of rises and falls
• Entropy of regular timed languages
• A linear algorithm for the random sampling from regular languages
• Unimodular Equivalence of Order and Chain Polytopes
• Generating Functions of Timed Languages
• A Survey of Alternating Permutations
• Inverting Polynomials and Formal Power Series
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
• Counting and Generating Permutations Using Timed Languages

This page was built for publication: Counting and generating permutations in regular classes