Une ligne de recherche présente dans la littérature depuis les années soixante est celle des \emph{théorèmes de représentation}. Son résultat fondateur est le théorème de Chomsky--Schützenberger qui stipule qu'un langage est algébrique si et seulement si il est l'image par homomorphisme de l'intersection entre un langage régulier et le langage de Dyck. Ce résultat a connu depuis diverses généralisations à différentes familles de langages. Dans cette thèse, nous proposons plusieurs généralisations de ce résultat aux langages d'ordres supérieurs. En particulier, nous introduisons une notion de langages de Dyck d'ordres supérieurs, nous définissons et étudions des classes de transductions que nous qualifions d'$\varepsilon$-sûres et nous montrons qu'un langage appartient à un niveau $k+l$ de la hiérarchie des ordres supérieurs si et seulement si il est l'image d'un langage de Dyck de niveau $k$ par une transductions $\varepsilon$-sûre de niveau $l$. Ces résultats nous permettent aussi d'obtenir d'autres types de caractérisations tels que des caractérisations logiques. / Amongst the classical results of the language theory, one can cite the known characterization of algebraic languages proved by Chomsky and Schützenberger and which states that a language is algebraic if and only if it is the homomorphic image of a regular set intersected with the Dyck language. This result has opened a new line of research and defined a new type of characterizations known as \emph{representation theorems}. In this thesis, we prove various representation theorems for the higher order languages hierarchy. In particular, we introduce a notion of higher order Dyck languages and a hierarchy of classes of transductions that we call $\varepsilon$-stable (or $\varepsilon$-safe) transductions and we prove that a language belongs to some level $k+l$ of the higher order hierarchy if and only if it can be represented as the image of a level-$k$ Dyck language by a level-$l$ $\varepsilon$-stable transduction. These representations also allow us to approach other types of characterizations such as logical characterizations.
| Identifer | oai:union.ndltd.org:theses.fr/2017AIXM0249 |
| Date | 15 November 2017 |
| Creators | Voundy, El Makki |
| Contributors | Aix-Marseille, Talbot, Jean-Marc, Fratani, Séverine |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.002 seconds