Fast diagnosis of some semigroup properties of automata
Marie Demlová, Vácłav Koubek · Czech digital mathematics library · 1986
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 0(\Q\ • \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 0(|<2| 2 • \X\) time.