Inequalities for one-step products

M. Branco and J.-É. Pin



Résumé : Soit a une lettre de l'alphabet A. Étant donné un treillis de langages L, nous décrivons l'ensemble des inégalités d'ultrafiltres satisfaites par le treillis La engendré par les langages de la forme L ou LaA*, où L est un langage de L. Nous décrivons également les inégalités d'ultrafiltres satisfaites par le treillis L1 engendré par le treillis La, pour a dans A. Lorsque L est un treillis of langages réguliers, nous décrivons tout d'abord les inégalités profinies satisfaites par La et L1, et nous donnons ensuite une petite base d'inégalités definissant L1 lorsque L est une algèbre de Boole de langages réguliers fermée par quotient.

Abstract : Let a be a letter of an alphabet A. Given a lattice of languages L, we describe the set of ultrafilter inequalities satisfied by the lattice La generated by the languages of the form L or LaA*, where L is a language of L. We also describe the ultrafilter inequalities satisfied by the lattice L1 generated by the lattices La, for a in A. When L is a lattice of regular languages, we first describe the profinite inequalities satisfied by La and L1 and then provide a small basis of inequalities defining L1 when L is a Boolean algebra of regular languages closed under quotient.

PDF file

Valid HTML 4.01!