Finite state automata: A geometric approach

DOI10.1090/S0002-9947-01-02774-XzbMath0980.20067MaRDI QIDQ2716145

Benjamin Steinberg

Publication date: 6 June 2001

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

semidirect productsgraphs\(\mathcal J\)-trivial semigroupsfree groupsmonoidspseudovarieties of finite groupsMal'cev productsprofinite topologiesfinite state automatarational languagespseudovarieties of finite monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Quasivarieties and varieties of groups (20E10)

Related Items (26)

PROFINITE METHODS IN SEMIGROUP THEORY ⋮ COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY ⋮ Pointlike sets and separation: a personal perspective ⋮ About the power pseudovariety \(\mathbf{PCS}\) ⋮ SOLVABLE MONOIDS WITH COMMUTING IDEMPOTENTS ⋮ Abelian kernels, profinite topologies and the extension problem ⋮ The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups ⋮ An upper bound for the power pseudovariety \(\mathbf{PCS}\). ⋮ UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS ⋮ On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties. ⋮ A Lower Bound For Reversible Automata ⋮ WHAT ARE MODULES? AN OVERVIEW OF BRET TILSON'S PAPER "MODULES" FROM A GEOMETRIC VIEWPOINT ⋮ On a locality-like property of the pseudovariety J ⋮ Groups acting on semimetric spaces and quasi-isometries of monoids ⋮ The pro-nilpotent group topology on a free group ⋮ Group extensions and graphs. ⋮ A NEW PROOF OF THE RHODES TYPE II CONJECTURE ⋮ Varieties of finite supersolvable groups with the M.~Hall property. ⋮ A constructive version of the Ribes-Zalesskiĭ product theorem. ⋮ On the complexity of computing the profinite closure of a rational language ⋮ Inverse automata and profinite topologies on a free group ⋮ The geometry of profinite graphs with applications to free groups and finite monoids ⋮ Expansions of inverse semigroups ⋮ Cayley graphs as classifiers for data mining: the influence of asymmetries ⋮ Constructing divisions into power groups ⋮ Commutative images of rational languages and the Abelian kernel of a monoid

Uses Software

• AMoRE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inverse semigroups and varieties of finite semigroups
• A category-theoretic approach to Boolean-valued models of set theory
• Categories as algebra: An essential ingredient in the theory of monoids
• Intersections of finitely generated subgroups of free groups and resolutions of graphs
• Profinite groups and Boolean graphs
• Separability properties of free groups and surface groups
• Some results on the dot-depth hierarchy
• Profinite categories and semidirect products
• Complexity of finite semigroups
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• A Conjecture on the Hall Topology for the Free Group
• Undecidability of the identity problem for finite semigroups
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• On The Profinite Topology on a Free Group
• THE PRO-p TOPOLOGY OF A FREE GROUP AND ALGORITHMIC PROBLEMS IN SEMIGROUPS
• On the Decidability of Iterated Semidirect Products with Applications to Complexity
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• On Pointlike Sets and Joins of Pseudovarieties
• The Gap Between Partial and Full
• INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
• CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATA
• ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
• ON SEPARABILITY PROPERTIES OF GROUPS
• Monoid kernels and profinite topologies on the free Abelian group
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Coset Representations in Free Groups
• Free inverse semigroups
• On algorithmic problems for joins of pseudovarieties
• Inverse automata and profinite topologies on a free group
• A topology for free groups and related groups

This page was built for publication: Finite state automata: A geometric approach