Notes on finite asynchronous automata

Abstract

We introduc the notion offnite asynchronous automata. Having ability of simultaneous excution of independent actions, these automata are used in a natural way as recognizing devices for subsets off ree partially commutative monoids. We prove that a subset ofafp.c. monoid is recognizable by a jinite asynchronous automaton ijj it is recognizable by a finite automaton. As a corollary we obtain a new characterization of the recognizable subsets of the fp.c. monoids by means of a parallel composition and certain homomorphisms.