Counting and generating permutations in regular classes

DOI10.1007/S00453-016-0136-9MaRDI QIDQ727971zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Counting and Generating Permutations Using Timed Languages
• Generating permutations with given ups and downs
• scientific article; zbMATH DE number 3865284
• Generating restricted classes of involutions, Bell and Stirling permutations
• Signatures des permutations et des mots extraits. (Signatures of permutations and extracted words)

Cites work

• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 1916671 (Why is no real title available?)
• scientific article; zbMATH DE number 3322983 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• A linear algorithm for the random sampling from regular languages
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• A spectral approach to consecutive pattern-avoiding permutations
• A survey of alternating permutations
• A theory of timed automata
• Algorithms for combinatorial structures: well-founded systems and Newton iterations
• Analytic combinatorics
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
• Consecutive patterns in permutations
• Counting and Generating Permutations Using Timed Languages
• Descent pattern avoidance
• Entropy of regular timed languages
• Generating Functions of Timed Languages
• Introduction to algorithms.
• Inverting Polynomials and Formal Power Series
• Multi-dimensional Boltzmann sampling of languages
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• On the frequencies of patterns of rises and falls
• Patterns in permutations and words.
• Permutations ayant une forme donnée
• Two poset polytopes
• Uniform random generation of decomposable structures using floating-point arithmetic
• Unimodular equivalence of order and chain polytopes

Cited in

(11)

• Rollercoasters and caterpillars
• Permutation classes
• Regular languages of plus- and minus-(in)decomposable permutations
• A counting scheme and some algebraic properties of a class of special permutation patterns
• Finding and counting permutations via CSPs
• Finding regular insertion encodings for permutation classes
• scientific article; zbMATH DE number 3865284 (Why is no real title available?)
• Young tableaux with periodic walls: counting with the density method
• Rollercoasters: Long Sequences without Short Runs
• Generating Countable Sets of Permutations
• Max-entropy sampling for deterministic timed automata under linear duration constraints

Describes a project that uses

Uses Software

• SymPy
• SageMath

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

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