Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Finite state automata: A geometric approach

Author: Benjamin Steinberg
Journal: Trans. Amer. Math. Soc. 353 (2001), 3409-3464
MSC (1991): Primary 20M35, 20F10
Published electronically: May 4, 2001
MathSciNet review: 1837243
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


Recently, finite state automata, via the advent of hyperbolic and automatic groups, have become a powerful tool in geometric group theory. This paper develops a geometric approach to automata theory, analogous to various techniques used in combinatorial group theory, to solve various problems on the overlap between group theory and monoid theory. For instance, we give a geometric algorithm for computing the closure of a rational language in the profinite topology of a free group. We introduce some geometric notions for automata and show that certain important classes of monoids can be described in terms of the geometry of their Cayley graphs. A long standing open question, to which the answer was only known in the simplest of cases (and even then was non-trivial), is whether it is true, for a pseudovariety of groups $\mathbf{H}$, that a ${\mathcal J}$-trivial co-extension of a group in $\mathbf{H}$ must divide a semidirect product of a ${\mathcal J}$-trivial monoid and a group in $\mathbf{H}$. We show the answer is affirmative if $\mathbf{H}$ is closed under extension, and may be negative otherwise.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 20M35, 20F10

Retrieve articles in all journals with MSC (1991): 20M35, 20F10

Additional Information

Benjamin Steinberg
Affiliation: Faculdade de Ciências, da Universidade do Porto, 4099-002 Porto, Portugal

Keywords: Immersions, coverings, fundamental groups, profinite topologies, rational languages, automata, graphs, monoids, block groups, semidirect products, pseudovarieties, Mal$'$cev products
Received by editor(s): February 12, 1999
Received by editor(s) in revised form: August 24, 2000
Published electronically: May 4, 2001
Additional Notes: The author was supported in part by Praxis XXI scholarship BPD 16306 98
Article copyright: © Copyright 2001 American Mathematical Society