Trees, Congruences and Varieties of Finite Semigroups

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: A classification scheme for regular languages or finite semigroups was proposed by Pin through tree hierarchies, a scheme related to the concatenation product, an operation on languages, and to the Sch├╝tzenberger product, an operation on semigroups. Starting with a variety of finite semigroups (or pseudovariety of semigroups) V, a pseudovariety of semigroups ◊u(V) is associated to each tree u. In this paper, starting with the congruence γA generating a locally finite pseudovariety of semigroups V for the finite alphabet A, we construct a congruence ≡u (γA) in such a way to generate ◊u(V) for A. We give partial results on the problem of comparing the congruences ≡u (γA) or the pseudovarieties ◊u(V). We also propose case studies of associating trees to semidirect or two-sided semidirect products of locally finite pseudovarieties.

Additional Information

Publication
Discrete Applied Mathematics, Vol. 86, 1998, pp 157-179.
Language: English
Date: 1998
Keywords
Formal language, Groups, Trees, Classification, Taxonomy