On a conjecture of Schnoebelen

Antonio Cano Gómez et Jean-Éric Pin



Résumé : Schnoebelen a introduit les notions de décompositions parallèles et séquentielles d'un langage sur un ensemble de de langages. Un langage est décomposable s'il appartient à un ensemble fini de langages S dont chaque membre admet une décomposition parallèle et séquentielle suivant S. Nous réfutons une conjecture de Schnoebelen concernant les langages décomposables et nous établissons quelques propriétés nouvelles de ces langages.

Abstract : The notion of sequential and parallel decomposition of a language over a set of languages was introduced by Schnoebelen. A language is decomposable if it belongs to a finite set of languages S such that each member of S admits a sequential and parallel decomposition over S. We disprove a conjecture of Schnoebelen concerning decomposable languages and establish some new properties of these languages.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!