Portal de Periódicos da CAPES

Mixed product and asynchronous automata

1986; Elsevier BV; Volume: 48; Linguagem: Francês

10.1016/0304-3975(86)90094-0

1879-2294

Christine Duboc,

Logic, programming, and type systems

We show the interest of the mixed (or synchronous) product for studying traces and trace languages in the free partially commutative monoids. We use this product to construct particular asynchronous automata and we show that each asynchronous automaton is the image by a strictly alphabetic morphism of a mixed product of automata. Then we use this result and Zielonka's theorem (1984) to obtain a result similar to Mezei's theorem in the free partially commutative monoids by showing that each recognizable trace language is the homomorphic image of some finite union of synchronous products of recognizable languages. Nous montrons l'intérět du produit de mixage (ou de synchronisation) pour l'étude des traces et langages traces, dans les monoïdes partiellement commutatifs libres. Nous utilisons ce produit pour construire des automates asynchrones particuliers et nous montrons que tout automate asynchrone est l'image par un morphisme strictement alphabétique d'un produit mixé d'automates. Nous utilisons alors ce résultat et le théorème de Zielonka (1984) pour obtenir un résultat similaire au théorème de Mezei dans les monoïdes partiellement commutatifs libres en montrant que tout langage trace reconnaissable est l'image homomorphe d'une union finie de produits de synchronisation de langages reconnaissables.