id: 00065333
dt: j
an: 00065333
au: Zhang, Shuhua
ti: Efficient simplicity testing of automata.
so: Theor. Comput. Sci. 99, No.2, 265-278 (1992).
py: 1992
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: streams of regular languages; pseudovariety of finite semigroups
ci: 
li: doi:10.1016/0304-3975(92)90352-G
ab: Summary: Let $V$ be a pseudovariety of finite semigroups; an automaton
    ${\cal A}=(X,Σ,M)$ is called $V$-type if the transformation semigroup
    of ${\cal A}$ belongs to $V$. Polynomial-time algorithms for testing
    whether an automaton ${\cal A}=(X,Σ,M)$ is $S$-type, $RS$-type,
    $LS$-type or $RS\lor LS$-type are given, where $S$, $RS$ and $LS$
    denote, respectively, the pseudovarieties of all finite simple
    semigroups, all finite right simple semigroups and all finite left
    simple semigroups.
rv: