Generalized Rational Relations and their Logical Definability

C. Choffrut, L.Guerra

IBP-Litp 1996/02: Rapport de Recherche Litp / Litp research reports
15 pages - Février/February 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Generalized Rational Relations and their Logical Definability

Résumé : La famille des parties rationnelles d'un produit direct de monoïdes libres So(1;*)x ...x So(n;*) (les relations rationnelles) n'est pas fermée par les opérations booléennes que si n=1 ou si tous les So(i;*)'s sont des singletons. Dans ce travail nous iontroduisons la famille des parties rationnelles generalizées d'un monoïde arbitraire comme la fermeture des singletons par les opérations booléennes, les opérations de concatenation et d'étoile (ce qui revient à ajouter simplement la complémentation aux opérations rationnelles). Nous exhibons une logique dans laquelle toutes les parties rationnelles généralisées peuvent être exprimées. Nous conjecturons que la réciproque est vraie, à savoir que toute partie définie dans cette logique est rationnelle généralisée, mais nos efforts sont restés infructueux jusqu'a présent.

Abstract : The family of rational subsets of a direct product of free monoids So(1;*)x ...x So(n;*) (the rational relations) is not closed under Boolean operations, except when n=1 or when all So(i;*)'s are singletons. In this paper we introduce the family of generalized rational subsets of an arbitrary monoid as the closure of the singletons under the Boolean operations, concatenation and Kleene star (just adding complementation to the usual rational operations). We exhibit a logic in which all generalized rational relations can be expressed, and we leave the converse as an open question, to wit, all subsets defined by this logic are generalized rational subsets. We conjecture that it holds true but our tentatives have been unsuccessful so far.

Publications internes Litp 1996 / Litp research reports 1996