Une application de la representation matricielle des transductions
1985; Elsevier BV; Volume: 35; Linguagem: Francês
10.1016/0304-3975(85)90019-2
ISSN1879-2294
AutoresJean-Éric Pin, Jacques Sakarovitch,
Tópico(s)Chemical Synthesis and Analysis
ResumoOn étudie le problème suivant, fréquemment rencontré en théorie des langages: soient n langages L1,…,Ln reconnus par les monoïdes M1,…,Mn respectivement. Etant donné une opération ϕ, on cherche à construire un monoïde M, fonction de M1,…,Mn, qui reconnaisse le langage (L1,…,Ln)ϕ. Nous montrons que la plupart des constructions proposées dans la littérature pour ce type de problème sont en fait des cas particuliers d'une méthode générale que nous exposons ici. Cette méthode s'applique également à certains problèmes moins classiques relatifs par exemple à la réduction du groupe libre ou aux opérations de contrôle sur les T0L-systèmes. We study the following classical problem of formal language theory: let L1,…,Ln be n languages recognized by the monoids M1,…,Mn respectively. Given an operation ϕ, we want to build a monoid M, function of M1,…,Mn, which recognizes the language (L1,…,Ln)ϕ. We show that most of the constructions given in the literature for this kind of problem are particular cases of a general method. This method can also be applied to some less classical problems related for example to the Dyck-reduction of the free-group or to control operations on T0L-systems.
Referência(s)