Portal de Periódicos da CAPES

Closure properties of certain families of formal languages with respect to a generalization of cyclic closure

1981; EDP Sciences; Volume: 15; Issue: 3 Linguagem: Francês

10.1051/ita/1981150302331

2777-3337

Andreas Brandstädt,

Logic, programming, and type systems

The weü-known circular closure of languages which permits the cyclic permutation of words is generahzed to afamily of opérations C n each opération being defined as the concaténation of permuted partitions of words into arbitrarüy chosen n parts The main objective of this paper is the investigation of closure properties of certain well-known families of formai languages Thus the families of regular, context-sensitwe and recurswely enumerable languages are shown to be closed under C" for every natural n and the main resuit states that one obtains a strongly increasing hierarchy if one apphes the opérations C" to the class of contextfree (hnear, one-counter) languages The same result holds for the full semi-AFLs generated by these families In contrast to a result by Maslov and Oshiba that the class of contextfree languages is closed under circular closure C 2 $ we can show that the same class is not closed under C 3 Résumé -La fermeture circulaire des langages, opération bien connue basée sur la permutation cyclique des mots, est généralisée en une famille d'opérations C, chaque opération étant définie comme la concaténation des partitions permutées des mots dans n parts choisis arbitrairement Le but principal de cet article est Vétude des propriétés de fermeture de quelques familles de langages formels très connues On montre alors que les familles de langages rationels, dépendants de contexte et dénombrables récursivement sont fermées par C n pour chaque entier n Le résultat principal affirme qu'on obtient une hiérarchie strictement croissante si on applique les opérations C n à la famille des langages algébriques (linéaires, langages à un compteur) Le même résultat est vrai pour les « full semi-AFLs » engendrés par ces famillesEn contrast au résultat de Maslov et Oshiba que la famille des langages algébriques est fermée par la fermeture circulaire C 2 , on montre que la même famille n'est pas fermée par C 3 (*)