Semigroups,Automata
and Languages
Combinatorial
semigroup theory has taken on a new dimension in recent years,
involving
techniques from geometry (Cayley graphs), topology (CW-complexes) or
language
theory (automata). Automata and languages are now systematically used
into the
study of presentations and it became evident that inverse
semigroups/automata
were the most appropriate tools to study various problems in group
theory and
topology. Some members of this team are involved together in a project
whose
main objectives are to pursue research into the geometry of inverse
semigroups,
deepening connections with other branches of mathematics, and to apply
the recently
developed techniques to the solution of algorithmic problems involving
presentations of various types.
Among the
concrete goals, one includes the classification by inverse monoids of
the
arbitrary subcomplexes of a covering space of a combinatorial
2-complex, the development
of notions of hyperbolicity and automaticity for inverse monoids,
various
decidability problems related to embeddings (inspired by connections
with
topology), partial homomorphisms and isomorphisms, as well as the
membership
problem for the class of rational languages over the fundamental group
of a
closed surface. Previous work of team members along these lines
includes [11,12,13,14,15,16,18,19].One
of the most fruitful tools in finite semigroup theory over the last
15years has
been the study of relatively free profinite semigroups. While a lot of
information is known about some special cases leading to significant
applications [1,2,7], not much is known about (absolutely) free
profinite
semigroups.
Recently,
techniques from symbolic dynamics have been successfully applied to
bring forth
information on those semigroups [3,6] but we are still at the beginning
of research
in this direction. In particular, only partial information is known
about the
role played by finite factor complexity entropy in the structure of
free
profinite semigroups. One aim that is worth pursuing is the
characterization of
elements of low complexity. Certain recursively enumerable subalgebras
of
relatively free profinite semigroups have also been shown to be
important
through the notion of a tame pseudovariety [5] and its refinements [4].
For its
applications in finite semigroup theory and its relationships with
other areas
of Mathematics, it remains worthwhile to establish these properties for
various
common pseudovarieties. J. Almeida intends to pursue these topics.
Computational
tools are undoubtedly very useful in finite semigroup theory. The
development
of specific software in a computational system such as GAP has the
advantage of
benefiting from the possibility of using algorithms for related areas
already
implemented in the same system. Practical computations achieved with an
implementation of an algorithm to compute the Abelian kernel of a
finite monoid
[8,9] have been fundamental to form the ideas that led to the results
in [10].
M. Delgado plans to continue the development of this kind of software
and the
search for applications.
L. Lima plans to
continue research in these subjects. She is currently working with B.
Steinberg
in problems involving inverse semigroups and extensions of partial
actions of
groups on groups, and with P. Silva on decidability problems for
Clifford
Monoid presentations. The main objective of the proposed work of A.
Oliveira is
to solve algorithmic problems involving presentations of inverse
monoids;
namely, the problem of, given two finite subsets A and B of the free
inverse monoid
on a set X (beginning with the case when X has only one element), to
determine
when the inverse monoids generated by A and by B are isomorphic. In
general,
she intends to apply the techniques introduced in [20], using
Schutzenberger
graphs, to solve decidability problems. L. Oliveira is currently
preparing a
doctoral thesis on E-varieties of locally inverse semigroups and
varieties of
pseudosemilattices.
P. Silva intends
to develop his main research activity in the following directions:
solution of
decidability problems in the context of combinatorial semigroup theory
and
language theory; development of geometric inverse semigroup theory;
study of
combinatorics on bidimensional words, with connections to both language
theory
and symbolic dynamics. All these topics connect to his own research
work for
the past three years. The cited topics involve in each case at least
two
different areas of mathematics/computer science and they are
potentially
interesting to a wide audience
1. J. Almeida,
Finite Semigroups and Universal Algebra, World Scientific,1995
2. J. Almeida, A
syntactical proof of locality of DA, Int. J. Algebra Comput. 6 (1996)
165-177
3. J. Almeida,
Dynamics of implicit operations and tameness of pseudovarieties of
groups,
Trans. AMS 354 (2002) 387-411
4. J. Almeida,
Finite semigroups: an introduction to a unified theory of
pseudovarieties, CMUP
2002-02
5. J. Almeida,
B. Steinberg, Syntactic and Global Semigroup Theory, a Synthesis
Approach, in
Algorithmic Problems in Groups and Semigroups, J.C. Birget,
6. J. Almeida,
M.V. Volkov, Profinite methods in finite semigroup theory, CMUP 2001-02
7. J. Almeida,
P. Weil, Free profinite R-trivial monoids, Int. J. Algebra Comput. 7
(1997)
625-671
8. M. Delgado,
Abelian pointlikes of a monoid, Semigroup Forum 56 (1998) 127-146
9. M. Delgado,
Commutative images of rational languages and the Abelian kernel of a
monoid,
RAIRO Inf. Theor. et Appl. To appear
10. M. Delgado,
V.H. Fernandes, Abelian kernels of some monoids of injective partial
transformations and an application, Semigroup Forum 61 (2000) 435-452
11. M. Delgado,
12. M. Lawson,
13. F. Mignosi,
A. Restivo, P.V. Silva, On Fine and Wilf Theorem for bidimensional
words,
Theor. Comp. Sci. To appear
14. A. Oliveira,
P.V. Silva, Inverse automata and monoids and the undecidability of the
Cayley
subgraph problem for groups, Glasgow Math. J.42 (2000) 421-437
15. P.V. Silva,
The homomorphism problem for free monoids, Discrete Math.To appear
16. P.V. Silva,
B. Steinberg, Extensions and submonoids of automatic monoids,TheorComp.
Sci. To
appear
17. B.
Steinberg, Finite state automata: A geometric approach, Trans. AMS 353
(2001)
3409-3464
18. B.
Steinberg, Factorization theorems for morphisms of ordered groupoids
and
inverse semigroups, Proc. Edinburgh Math. Soc. 44 (2001) 549-569
19. B.
Steinberg, A topological approach to inverse and regular semigroups,
Pacific J.
Math. To appear
20. J. Stephen,
Presentations of inverse monoids, J. Pure Appl. Alg. 63 (1990) 81-112