Classes of Automata Defined by Quasi-orders on a Free Monoid
by
Jelena Kovacevic
University of Nis, Faculty of Sciences and Mathematics, Cirila i Metodija 2, P. O. Box 224, 18000 Nis, Yugoslavia
Coauthors: Miroslav Ciric (University of Nis, Faculty of Sciences and Mathematics, Nis Yugoslavia), Tatjana Petkovic (University of Nis, Faculty of Sciences and Mathematics, Nis Yugoslavia, and Turku Centre for Computer Science, Turku, Finland), Stojan Bogdanovic (University of Nis, Faculty of Economics, Nis, Yugoslavia)

For a given quasi-order \xi on a free monoid X^*, an X-automaton A is called \xi-directable if there exists a word u in X^* such that av=bv for every word v in X^* such that u\xiv and every pair of states a, b in A. It is easy to see that \xi-directable automata are just a special type of directable automata , but for an appropriate choice of a quasi-order \xi as special cases of \xi-directable automata we obtain various important classes of automata such as ordinary directable automata, the well-known definite automata and the so-called piecewise directable automata , introduced and studied in a recent paper by T. Petkovic and M. Steinby.

We study some general properties of \xi-directable automata, as well as of certain related kinds of automata: trap \xi-directable, \xi-trapped and generalized \xi-directable automata. Interesting connections between the mentioned classes of automata, quasi-orders on a free monoid and ideals of a free monoid are established.

Date received: May 30, 2001