Data di Pubblicazione:
2017
Citazione:
Quantum finite automata : advances on Bertoni's ideas / M.P. Bianchi, C. Mereghetti, B.S. Palano. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 664(2017 Feb), pp. 39-53. [10.1016/j.tcs.2016.01.045]
Abstract:
We first outline main steps and achievements along Bertoni's research path in quantum finite automata theory - from the very basic definitions of the models of quantum finite automata throughout the investigation of their computational and descriptional power. Next, we choose to focus on Bertoni's studies on quantum finite automata descriptional complexity. In particular, we expand on a statistical framework for the synthesis of succinct quantum finite automata, discussing its adaptation to the case of multiperiodic events and languages. We then improve such a framework to obtain even more succinct quantum finite automata for some multiperiodic languages. Finally, we introduce some promise problems for multiperiodic inputs, showing that even on this class of problems the descriptional power of quantum finite automata greatly outperforms that of equivalent classical finite automata.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
descriptional complexity; quantum finite automata; theoretical computer science; computer science (all)
Elenco autori:
M.P. Bianchi, C. Mereghetti, B.S. Palano
Link alla scheda completa: