Fast diagnosis of some semigroup properties of automata. (English) Zbl 0608.68042

Author’s summary: ”The aim of this note is to improve the results of Watanabe and Nakamura. We present algorithms which for a given automaton A decide whether the transition semigroup of A contains left or right identity, or whether the transition semigroup of A is a left or a right group, or permutation group, in linear time (i.e. it requires O(\(| Q| \cdot | X|)\) time where Q is the set of states of A, X is the set of inputs of A. Further we give algorithms which for a given automaton A decide whether A is quasi-state independent, or state independent and requires \(O(| Q|^ 2\cdot | X|)\) time.”
Reviewer: I.Peák


68Q70 Algebraic theory of languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: EuDML


[1] A. V. Aho J. E. Hopcroft, J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesiey, Reading, Mass. 1974. · Zbl 0326.68005
[2] A. H. Clifford, G. B. Preston: The Algebraic Theory of Semigroups. AMS Providence, Rhode Island 1967. · Zbl 0178.01203
[3] M. Demlová J. Demel, V. Koubek: On subdirectly irreducible automata. RAIRO - Inform. Théor. 15 (1981), 23-46. · Zbl 0482.68050
[4] R. E. Tarjan: Depth first search and linear graph algorithms. SIAM J. Comput. 1 (1971), 146-160. · Zbl 0251.05107
[5] T. Watanabe, A. Nakamura: On the transformation semigroups of finite automata. J. Comp. System Sci. 26 (1983), 107-138. · Zbl 0504.68029 · doi:10.1016/0022-0000(83)90024-7
[6] T. Watanabe, S. Noguchi: The amalgamation of automata. J. Comp. System Sci. 15 (1977), 1-16. · Zbl 0357.94058 · doi:10.1016/S0022-0000(77)80024-X
[7] T. Watanabe, S. Noguchi: Quasi-state independent automata. I.E.C.E. Japan. Trans. 60-D (1977), 177-179.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.