Semigroup Theoretical Methods in Automata Theory
by
Jelena Kovačević
University of Niš, Niš, Yugoslavia
Coauthors: Miroslav Ćirić (University of Niš), Stojan Bogdanović (University of Niš), Tatjana Petković (University of Niš and TUCS, Turku, Finland)

Semigroups appear in Automata theory mainly as input and transition semigroups of automata, what has been the starting point of many beautiful theories that connect semigroups and automata, as well as languages, as for example Krohn-Rhodes and Eilenberg theories. But, transfer of certain semigroup-theoretical ideas and methods in Automata theory has shown oneself to be equally important. The main aim of this paper to emphasize the role of some concepts and methods imported from Semigroup theory in study of certain direct sum and subdirect decompositions of automata, as well as of subdirectly irreducible automata.

Schein (1966) and Putcha (1973) studied subdirect products of nilpotent and nil-semigroups. Using a similar methodology here we study subdirect products of trap-connected automata. For that purpose we introduce the notion of a reversible state of an automaton, which can be viewed as an analogue of group or regular elements of semigroups, and we prove that automata without reversible states can be characterized as automata without traps decomposable into a subdirect product of trap-connected automata. We also study automata having reversible states and prove that every finite automaton can be uniquely represented as an extension of an automaton whose every state is reversible by a trap-directable automaton. Starting from the notion of a positive quasi-order \pi on an automaton, which also has its origin in Semigroup theory, we also define the notions of a \pi-reversible state and a \pi-connected automaton , which we use to describe various other subdirect and direct sum decompositions of automata.

On the other hand, we describe all subdirectly irreducible automata using a methodology similar to the one used by Schein (1966) in study of subdirectly irreducible semigroups and some methods and concepts imported from theory of ideal extension of semigroups. Namely, we characterize these automata in terms of traps, cores, Rees congruences and Rees extensions of congruences on subautomata, dense extensions of automata, disjunctive elements etc.

Date received: May 7, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-21.