The signature of a permutation can be described in terms of two symbols that represent ascent and descent in the ordering of the elements. For each regular language (that can be recognized by a finite-state automaton) over those two symbols, we can associate a class of permutations with a signature in that language, and such a class of permutations is then called “regular.”

Whereas the combinatorics of permutations with a given signature has been explored previously in the literature [1,2,3], here the formulation is extended to regular classes of permutations, considering language equations from automata theory.

The paper is well written and mathematically rigorous. Though the material is complex and advanced, it is also presented in a self-contained manner with the first two sections on introduction and preliminaries covering relevant basics and references, without assuming much prior knowledge of automata theory or the combinatorics involved.

The next sections cover two approaches to solve three different problems. First of these is computing the sequence of cardinalities of the sets of permutations of a given length in a given regular language. The second problem considered is that of computing an exponential generating function for such a sequence, and the third problem is about generating uniformly random permutations from a regular class.

The first approach to solve these problems is given in section 3, and it extends previous methods for counting and randomly generating permutations with a prescribed signature. Here, there are two alternatives, one dealing with discrete permutations and another considering the corresponding order polytopes on hyper cubes. Also, the generating function is characterized as the solution involving the integral of the exponential of a matrix.

The second solution approach given, in section 4, is based on a connection between the combinatorics of permutations and the theory of timed automata. The symmetric role played by ascents and descents is handled here. The concept of the volumetry of regular timed languages used here is relatively new [4].

Section 5 considers the problem of random sampling of permutations in a regular class. Such a sampling reduces to sampling timed words in the corresponding language of signatures as shown in a theorem. Section 6 concludes with suggestions on future directions to explore.

The content and contributions here are mostly theoretical, which will be of particular interest to researchers in the domain. There is not much emphasis on practical applications, though results are reported on a running example with the algorithms implemented using Sage.