COMETA-GAE

Enumerative combinatorics is the branch of mathematics that focuses on counting, exactly or approximately, certain combinatorial structures, such as trees, graphs, permutations, or words in formal languages, that underlie discrete modeling in various fields of research. Generation algorithms instead aim at producing such structures, either at random with respect to a target probability distribution, or exhaustively to list all possibilities. Random and exhaustive generation algorithms are routinely developed in computer science for verification purposes, in statistical physics for computer experiments, or in bioinformatics to assess statistical significance. The COMETA-GAE project is focused on constructive enumeration, that is, counting technics that can be lifted effectively into generation procedures. The last few years have witnessed significant progress in this area and we are convinced it is a good time for a collective leap forward. We plan to address in particular combinatorial structures with D-finite generating functions or with catalytic decompositions, which are currently attracting strong interest. An example of challenge is to build on the recent result that Parikh automata languages provide natural combinatorial interpretations to certain diagonals of rational series. Typical questions are: to what extent are such interpretations generic, how effective are they in terms of design of random or exhaustive generation algorithms? We intend to extend the tools of constructive enumeration to new universality classes of combinatorial models, beyond the now standard framework of the celebrated Boltzmann method. The idea is to start from classical models and reach new types of structures by enforcing constraints or adding decorations. We will also explore the interplay of these constructive technics with recent progress on generation algorithmics like the bit optimality result of Sportiello for rational and context-free structures.