| （英） |
The state complexity of a finite(-state) automaton intuitively measures the size of the description of the automaton. Sakoda and Sipser (STOC 1972, pp. 275--286) were concerned with non-uniform families of finite automata and they discussed the behaviors of non-uniform complexity classes defined by families of such finite automata having polynomial-size state complexity.
In a similar fashion, we introduce non-uniform state complexity classes using families of quantum finite automata. Our primarily concern is one-way quantum finite automata empowered by garbage tapes. We show inclusion and separation relationships among non-uniform state complexity classes of various one-way finite automata, including deterministic, nondeterministic, probabilistic, and quantum finite automata. For two-way quantum finite automata with garbage tapes,
we discover a close relationship between the state complexity of non-uniform families of such quantum finite automata and the parameterized complexity class induced by quantum polynomial-time logarithmic-space computation with polynomial-size advice. |