An algebraic theory for regular languages of finite and infinite words. (English) Zbl 0791.68116

An algebraic approach to the theory of regular languages of finite and infinite words (\(\infty\)-languages) is presented. It extends the algebraic theory of regular languages of finite words, which is based on finite semigroups. Their role is taken over by a structure called right binoid. A variety theorem is proved: there is a one-to-one correspondence between varieties of \(\infty\)-languages and pseudovarieties of right binoids. The class of locally threshold testable languages and several natural subclasses (such as the class of locally testable languages) as well as classes of the Borel hierarchy over the Cantor space (restricted to regular languages) are investigated as examples for varieties of \(\infty\)-languages. The corresponding pseudovarieties of right binoids are characterized and in some cases defining equations are derived. The connections with the algebraic description and classification of regular languages of infinite words in terms of finite semigroups are pointed out.
Reviewer: Thomas Wilke


68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
08A70 Applications of universal algebra in computer science
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI