Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

An Eilenberg theorem for words on countable ordinals

Nicolas BedonContact Information and Olivier CartonContact Information

(1)  Institut Gaspard Monge, Université de Marne-la-Vallée, 2, rue de la Butte Verte, F-93166 Noisy-le-Grand Cedex
Abstract
We present in this paper an algebraic approach to the theory of languages of words on countable ordinals. The algebraic structure used, called an Ω1-semigroup, is an adaptation of the one used in the theory of regular languages of Ω-words. We show that finite Ω1-semigroups are equivalent to automata. In particular, the proof gives a new algorithm for determinizing automata on countable ordinals. As in the cases of finite and Ω-words, a syntactic Ω1-semigroup can effectively be associated with any regular language of words on countable ordinals. This result is used to prove an Eilenberg type theorem. There is a one-to-one correspondence between varieties of Ω1-languages and pseudo-varieties of Ω1-semigroups.

Contact Information Nicolas Bedon
Email: Nicolas.Bedon@univ-mlv.fr
URL: http://www-igm.univ-mlv.fr/~bedon

Contact Information Olivier Carton
Email: Olivier.Carton@univ-mlv.fr
URL: http://www-igm.univ-mlv.fr/~carton
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)