Robert Cori

TCS Journal 2021 Journal Article

On doubly symmetric Dyck words

• Robert Cori
• Andrea Frosini
• Giulia Palma
• Elisa Pergola
• Simone Rinaldi

In this paper we consider doubly symmetric Dyck words, i. e. Dyck words which are fixed by two symmetry operations α and β introduced in [1]. We study combinatorial properties of doubly symmetric Dyck words, leading to the definition of two recursive algorithms to build these words. As a consequence we have a representation of doubly symmetric Dyck words as vectors of integers, called track vectors. Finally, we show some bijections between a subfamily of doubly symmetric Dyck words and a subfamily of integer partitions. The computation of the sequence f n of doubly symmetric Dyck words of semi-length n shows surprising properties giving rise to some conjectures.

TCS Journal 2016 Journal Article

Some permutations on Dyck words

• Marilena Barnabei
• Flavio Bonetti
• Niccolò Castronuovo
• Robert Cori

We examine three permutations on Dyck words. The first one, α, is related to the Baker and Norine theorem on graphs, the second one, β, is the symmetry, and the third one is the composition of these two. The first two permutations are involutions and it is not difficult to compute the number of their fixed points, while the third one has cycles of different lengths. We show that the lengths of these cycles are odd numbers. This result allows us to give some information about the interplay between α and β, and a characterization of the fixed points of α ∘ β.

TCS Journal 2003 Journal Article

Description trees and Tutte formulas

• Robert Cori
• Gilles Schaeffer

In this paper we introduce and enumerate families of description trees. These families of trees consist of plane trees in which the nodes are labelled by nonnegative integers, and where the label of each node satisfies a condition relating it to the labels of its sons. We give a recursive construction of these trees which translates simply in an equation for their generating function. By solving this equation via the quadratic method introduced by Brown and Tutte, we prove that this generating function is algebraic. For some families the number of trees we obtain is equal to the numbers given by Tutte to enumerate different kinds of planar maps. We provide bijections between description trees and corresponding families of planar maps to explain these equalities. Description trees are instances of objects that can be described by description operators; we conjecture that such families of objects have algebraic generating functions. They were find also to be related to the enumeration of pattern avoiding permutations.

TCS Journal 2002 Journal Article

Polynomial ideals for sandpiles and their Gröbner bases

• Robert Cori
• Dominique Rossin
• Bruno Salvy

A polynomial ideal encoding topplings in the abelian sandpile model on a graph is introduced. A Gröbner basis of this ideal is interpreted combinatorially in terms of well-connected subgraphs. This gives rise to algorithms to determine the identity and the operation in the group of recurrent configurations.

TCS Journal 1998 Journal Article

Counting non-isomorphic chord diagrams

• Robert Cori
• Michel Marcus

Different formulas counting families of non-isomorphic chord diagrams are given: planar and toroidal ones and those of maximal genus. These formulas are obtained establishing results on the structure of the automorphism group of diagrams of a given genus.

TCS Journal 1991 Journal Article

On the number of partially abelian square-free words on a three-letter alphabet

• Robert Cori
• Maria Rosaria Formisano

TCS Journal 1990 Journal Article

Editorial

• Robert Cori
• Burkhard Monien

TCS Journal 1988 Journal Article

2-Asynchronous automata

• Robert Cori
• Eric Sopena
• Michel Latteux
• Yves Roos

W. Zielonka has recently introduced a family of finite automata with a specific behavior, and called them asynchronous automata. They can be considered as a good model to describe concurrent processes exchanging data by means of some common storage. Hereafter, we restrict the family of asynchronous automata by defining the subclass of what we will call 2-asynchronous automata. We illustrate this subclass by a communication problem involving mailboxes, and prove that 2-asynchronous automata are as powerful as asynchronous ones.

TCS Journal 1985 Journal Article

Recognizable subsets of some partially abelian monoids

• Robert Cori
• Yves Métivier

We show that, in a free partially abelian monoid generated by a finite alphabet A, the subset [X∗ ] of A∗ containing all the words equivalent to a product of words of X is rational if X is a finite set of words, each word containing at least one occurrence of any letter of A. We suppose that the graph the vertices of which are letters of A and the edges of which correspond to noncommuting pairs of letters is connected.

TCS Journal 1982 Journal Article

Construction of maps with prescribed automorphism group

• Robert Cori
• Antonio Machi

We show that given a finite group G a hypermap can be constructed having automorphism group isomorphic to G. The bipartite map of a modified version of this hypermap then affords a map with the same property.