×

On the complexity of search of a deterministic subautomaton. (Russian) Zbl 0661.68043

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^{n/\log (n)})\setminus DTIME(d^{n/\log (n)}) \] for appropriate constants c and d.
Reviewer: A.P.Stolboushkin

MSC:

68Q25 Analysis of algorithms and problem complexity