×

An Eilenberg theorem for \(\infty\)-languages. (English) Zbl 0766.68083

Automata, languages and programming, Proc. 18th Int. Colloq., Madrid/Spain 1991, Lect. Notes Comput. Sci. 510, 588-599 (1991).
Summary: [For the entire collection see Zbl 0753.00027.]
We use a new algebraic structure to characterize regular sets of finite and infinite words through recognizing morphisms. A one-to-one correspondence between special classes of regular \(\infty\)-languages and pseudovarieties of right binoids according to Eilenberg’s theorem for regular sets of finite words is established. We give the connections to semigroup theoretical characterizations and classifications of regular \(\omega\)-languages, and treat concrete classes of \(\infty\)-languages in the new framework.

MSC:

68Q45 Formal languages and automata
08A70 Applications of universal algebra in computer science
20M35 Semigroups in automata theory, linguistics, etc.

Citations:

Zbl 0753.00027
PDFBibTeX XMLCite