FAIR EXPRESSIONS AND REGULAR LANGUAGES OVER LISTS

摘要

In this paper a formalism is proposed, named fair expressions, partly introduced in [Bre94], that extends regular expressions to lists, having strings as components. This formalism uses classical regular operators, i.e. catenation and its closure, and novel ones, namely the operator of merge and its closure, which are natural for lists. Fair expressions allow to define languages of lists, named fair languages, which can be compared to word languages by flattening the lists into strings. In this paper the basic properties of fair languages are briefly summarized and also extended with respect to previous works [Bre94]: hierarchy, semilinearity, closure, decidability and comparison with the Chomsky hierarchy are dealt with. The family of fair languages is however far larger than the regular one; as a novel contribution this paper investigates its subfamilies that are comparable with regular languages. The main result is that the regular subfamilies of fair languages constitute a proper hierarchy. These subfamilies are then characterized and their properties are explored, showing that they are, in general, more mathematically tractable than fair languages. The conclusion lists comparisons with related works, open problems and research directions.%Cet article propose un formalisme, appelé expressions équitables, qui a été partiellement introduit en [Bre94], et qui étend les expressions régulières aux listes dont les composantes sont des mots. Ce formalisme utilise les opérateurs rationnels classiques, c 'est-à-dire la concaténation et l'étoile, ainsi que de nouveaux opérateurs tels que celui de fusion et sa fermeture, qui sont des opérateurs naturels sur les listes. Les expressions équitables permettent de définir des languages de listes appelés languages équitables qui peuvent être comparés aux langages de mots, les listes une fois converties en mots par concaténation des composantes. Dans cet article les propriétés fondamentales des languages équitables sont brièvement rappelées et généralisées par rapport aux travaux antérieurs [Bre94]: hiérarchie, semilinéarité, clôture, décidabilité et comparaison avec la hiérarchie de Chomsky sont traités. Cette famille contient strictement celle des langages réguliers; l'étude des sous-familles comparables à celle des langages réguliers est une contribution originale de ce travail. Le résultat principal est que ces sous-familles régulières de langages équitables forme une hiérarchie propre. Ces sous-familles ensuite caractérisées et leurs propriétés sont explorées, et nous montrons ainsi qu 'elles sont mathématiquement plus manipulables que celle des langages équitables. En conclusion nous mentionnons des travaux qui sont reliés à notre recherche, nous posons des problèmes ouverts et indiquons des directions de recherche.