Right-justified characterization for generating regular pattern permutations
Speaker: Do Phan Thuan and Tran Thi Thu Huong

Time: 9h30, Thursday, April 13, 2017
Location: Room 201, Institute of Mathematics, 18 Hoang Quoc Viet
Abtract: ECO-method and its corresponding succession rules allow to recursively define and construct combinatorial objects. The induced generating trees can be coded corresponding pattern avoiding permutations. We refine succession rules by using succession functions in case when avoided patterns are regular or c-regular. Although regular patterns are hard to recognize in general, we give a characterization for its right-justified property which is a prerequisite in the definition of the regular pattern. Based on this characterization, we show the (c-)regularity, c-regularity for some new classes of permutations avoiding sets of patterns with variable lengths. Last, the technique of succession functions permits to construct general efficient generating models for classes of (c) regular pattern avoiding permutations which are constant amortized time for pattern sets mentioned above.

Back

New Scientiffic Publications