\input zb-basic
\input zb-ioport
\iteman{io-port 04080912}
\itemau{Marchenkov, S.S.}
\itemti{On the complexity of search of a deterministic subautomaton.}
\itemso{Izv. Vyssh. Uchebn. Zaved., Mat. 1988, No.7(314), 52-56 (1988).}
\itemab
Let A and B be two finite automata over the same input alphabet. A is called to be a subautomaton of B, if (1) states of A form a subset of states of B; (2) the state transition function of A is a restriction of that of B. The problem is, given a nondeterministic finite automaton B, to determine whether or not there exists a deterministic finite (nonempty) subautomaton A of B. The only theorem is that the above problem belongs to the following complexity class: $$ DTIME\quad (c\sp{n/\log (n)})\setminus DTIME(d\sp{n/\log (n)}) $$ for appropriate constants c and d.
\itemrv{A.P.Stolboushkin}
\itemcc{}
\itemut{exponential lower bounds; finite automata; subautomaton; complexity class}
\itemli{}
\end