|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice | | Tomoyuki Yamakami
; | | Date: |
5 Jul 2019 | | Abstract: | 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 nonuniform families of finite automata and they
discussed the behaviors of nonuniform complexity classes defined by families of
such finite automata having polynomial-size state complexity. In a similar
fashion, we introduce nonuniform 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 nonuniform state complexity classes of various one-way
finite automata, including deterministic, nondeterministic, probabilistic, and
quantum finite automata of polynomial size. For two-way quantum finite automata
equipped with garbage tapes, we discover a close relationship between the
nonuniform state complexity of such a polynomial-size quantum finite automata
family and the parameterized complexity class induced by quantum
logarithmic-space computation assisted by polynomial-size advice. | | Source: | arXiv, 1907.2916 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER