Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-20T10:31:13.391Z Has data issue: false hasContentIssue false

Une Generalization DU Theoreme DE Ginsburg-Rose

Published online by Cambridge University Press:  20 November 2018

Daniel Chaput
Affiliation:
CEGEP de Miette, Juliette, Québec
Gert Sabidussi
Affiliation:
Université de Montréal, Montréal, Québec
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Nous présentons ici une étude relative aux applications entre monoïdes, que nous nommerons transductions, qui peuvent être réalisées par un transducteur (machine séquentielle généralisée). L'exposé s'oriente sur l'examen des conditions caractérisant de telles applications. Le point de départ est le théorème de Ginsburg-Rose [2], qui caractérise les transductions entre monoïdes libres de type fini, en termes de quatre conditions dont une, la condition de “bounded output”, implique la longueur des mots et, par conséquent, ne peut être formulée que dans un monoïde libre. A l'aide d'un langage propre aux structures algébriques en général, celle des congruences, nous étudions des conditions remplaçant ‘'bounded output”, pour généraliser le théorème connu aux monoïdes quelconques et aux monoïdes libres quelconques.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1980

References

Bibliographie

1. Eilenberg, S., Automata, languages, and machines, Volume A (Academic Press, New York and London, 1974).Google Scholar
2. Ginsburg, S. and Rose, G. F., A characterization of machine mappings, Can. J. Math. 18 (1966), 381388.Google Scholar
3. Nerode, A., Linear automaton transformation, Proc. Amer. Math. Soc. 9 (1958), 541544.Google Scholar