Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Counting and generating permutations in regular classes
Basset N. Algorithmica76 (4):989-1034,2016.Type:Article
Date Reviewed: May 19 2017

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.

Reviewer:  Paparao Kavalipati Review #: CR145287 (1708-0551)
1) Marchal, P. Permutations with a prescribed descent set, hal-00944244, version 1 (10 February 2014). HAL archives, https://hal.archives-ouvertes.fr/hal-00944244/document (04/30/2017).
2) Luck, J. M. On the frequencies of patterns of rises and falls. Physica A: Statistical Mechanics and its Applications 407 (2014), 252–275.
3) Stanley, R. P. A survey of alternating permutations. MIT, http://www-math.mit.edu/~rstan/papers/altperm.pdf (04/30/2017).
4) Asarin, E.; Basset, N.; Degorre, A. Entropy of regular timed languages. HAL archives, https://hal.archives-ouvertes.fr/hal-01078613/document (04/30/2017).
Bookmark and Share
  Featured Reviewer  
 
Permutations And Combinations (G.2.1 ... )
 
 
Classes Defined By Grammars Or Automata (F.4.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Permutations And Combinations": Date
Computing short generator sequences
Driscoll J., Furst M. Information and Computation 72(2): 117-132, 1987. Type: Article
Jan 1 1988
Permutations of bounded degree generate groups of polynomial diameter
McKenzie P. (ed) Information Processing Letters 19(5): 253-254, 1984. Type: Article
Aug 1 1985
How to construct pseudorandom permutations from pseudorandom functions
Luby M. (ed), Rackoff C. SIAM Journal on Computing 17(2): 373-386, 1988. Type: Article
Jul 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy