Succinctness of two-way probabilistic and quantum finite automata
A Yakaryilmaz, ACC Say - Discrete Mathematics & …, 2010 - dmtcs.episciences.org
Succinctness of two-way probabilistic and quantum finite automata Page 1 Discrete
Mathematics and Theoretical Computer Science DMTCS vol. 12:4, 2010, 19–40 Succinctness …
Mathematics and Theoretical Computer Science DMTCS vol. 12:4, 2010, 19–40 Succinctness …
Languages recognized by nondeterministic quantum finite automata
A Yakaryilmaz, AC Say - arXiv preprint arXiv:0902.2081, 2009 - arxiv.org
The nondeterministic quantum finite automaton (NQFA) is the only known case where a one-
way quantum finite automaton (QFA) model has been shown to be strictly superior in terms …
way quantum finite automaton (QFA) model has been shown to be strictly superior in terms …
One-Way Finite Automata with Quantum and Classical States.
In this paper, we introduce and explore a new model of quantum finite automata (QFA).
Namely, one-way finite automata with quantum and classical states (1QCFA), a one way …
Namely, one-way finite automata with quantum and classical states (1QCFA), a one way …
Photonic realization of a quantum finite automaton
We describe a physical implementation of a quantum finite automaton that recognizes a well-
known family of periodic languages. The realization exploits the polarization degree of …
known family of periodic languages. The realization exploits the polarization degree of …
[HTML][HTML] Quantum finite automata: Advances on Bertoni's ideas
MP Bianchi, C Mereghetti, B Palano - Theoretical Computer Science, 2017 - Elsevier
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 …
automata theory–from the very basic definitions of the models of quantum finite automata …
Descriptional complexity of iterated uniform finite-state transducers
M Kutrib, A Malcher, C Mereghetti, B Palano - Descriptional Complexity of …, 2019 - Springer
We introduce the deterministic computational model of an iterated uniform finite-state
transducer (iufst). A iufst performs the same length-preserving transduction on several left-to …
transducer (iufst). A iufst performs the same length-preserving transduction on several left-to …
On the state complexity of semi-quantum finite automata⋆⋆⋆
S Zheng, J Gruska, D Qiu - RAIRO-Theoretical Informatics and …, 2014 - cambridge.org
Some of the most interesting and important results concerning quantum finite automata are
those showing that they can recognize certain languages with (much) less resources than …
those showing that they can recognize certain languages with (much) less resources than …
Complexity of promise problems on classical and quantum automata
MP Bianchi, C Mereghetti, B Palano - … Dedicated to Jozef Gruska on the …, 2014 - Springer
We consider the promise problem A^ N, r_1, r_2 on a unary alphabet\left {σ\right\} studied by
Gruska et al. in 21. This problem is formally defined as the pair A^ N, r_1, r_2=(A^ N, r_1 …
Gruska et al. in 21. This problem is formally defined as the pair A^ N, r_1, r_2=(A^ N, r_1 …
Quantum finite automata with control language
C Mereghetti, B Palano - RAIRO-Theoretical Informatics and …, 2006 - cambridge.org
Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-
way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model …
way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model …
Unary probabilistic and quantum automata on promise problems
A Gainutdinova, A Yakaryılmaz - Quantum Information Processing, 2018 - Springer
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs
and QFAs) on promise problems by focusing on unary languages. We show that bounded …
and QFAs) on promise problems by focusing on unary languages. We show that bounded …