Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1303.2967 · Lecture notes in computer science

Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem

Alberto Bertoni, Christian Choffrut, Flavio D’Alessandro

Published Jan 1, 2013• 4 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-38771-5_9

Related papers

Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Daowen Qiu, Lvzhou Li, Xiangfu Zou +2 more

Acta Informatica•Aug 1, 2011•21 citations

Languages Recognizable by Quantum Finite Automata

Rūsiņš Freivalds

Lecture notes in computer science•Jan 1, 2006•5 citations

ON THE DECIDABILITY OF THE INTERSECTION PROBLEM FOR QUANTUM AUTOMATA AND CONTEXT-FREE LANGUAGES

Alberto Bertoni, Christian Choffrut, Flavio D’Alessandro

We consider the so-called measure once finite quantum automata model introduced by Moore and Crutchfield in 2000. We show that given a language recognized by such a device and a linear context-free language, it is decidable whether or not they have a nonempty intersection. This extends a result of Blondel et al. which can be interpreted as solving the problem with the free monoid in place of the family of linear context-free languages.

International Journal of Foundations of Computer Science•Dec 1, 2014•4 citations

Quantum Finite Automata and Logics

Ilze Dzelme-Bērziņa

Lecture notes in computer science•Jan 1, 2006•4 citations

An Algebraic Approach to the Study of Quantum Finite Automata

Andrea Benso

In this thesis we will study the decidability of the Intersection problem for the measure-once quantum finite automata introduced by Moore and Crutchfield in the 2000s. Specifically, we ask for which families of grammars it is possible to find conditions ensuring that, given a language recognized by such model of computation and a language generated by such families of grammars, it is decidable whether or not they have a nonempty intersection. Throughout the thesis, we will investigate the correlation between this problem and some decidability problems for matrices subsets on the Zariski topology, so as to apply the corresponding results to show the decidability of the problem for languages generated by monoidal context-free grammars and restricted matrix context-free grammars of finite index.

•Jan 1, 2025•0 citations

Decidable and Undecidable Problems about Quantum Automata

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran +1 more

We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict andnonstrict thresholds both lead to undecidable problems.

arXiv:quant-ph/0304082•SIAM Journal on Computing•Jan 1, 2005•76 citations
In this thesis we will study the decidability of the Intersection problem for the measure-once quantum finite automata introduced by Moore and Crutchfield in the 2000s. Specifically, we ask for which families of grammars it is possible to find conditions ensuring that, given a language recognized by such model of computation and a language generated by such families of grammars, it is decidable whether or not they have a nonempty intersection. Throughout the thesis, we will investigate the correlation between this problem and some decidability problems for matrices subsets on the Zariski topology, so as to apply the corresponding results to show the decidability of the problem for languages generated by monoidal context-free grammars and restricted matrix context-free grammars of finite index.