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

Lecture notes in computer science

Quantum Automata and Languages of Finite Index

Andrea Benso, Flavio D’Alessandro, Paolo Papi

Published Jan 1, 2024• 2 citations
Publisher
DOI
10.1007/978-3-031-72621-7_7

Related papers

Languages Recognizable by Quantum Finite Automata

Rūsiņš Freivalds

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

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

Alberto Bertoni, Christian Choffrut, Flavio D’Alessandro

arXiv:1303.2967•Lecture notes in computer science•Jan 1, 2013•4 citations

Probabilities to Accept Languages by Quantum Finite Automata

Andris Ambainis, Richard Bonner, Rūsiņš Freivalds +1 more

arXiv:quant-ph/9904066•Lecture notes in computer science•Jan 1, 1999•35 citations

Languages Recognized with Unbounded Error by Quantum Finite Automata

Abuzer Yakaryılmaz, A. C. Cem Say

Lecture notes in computer science•Jan 1, 2009•30 citations

On the Class of Languages Recognizable by 1-Way Quantum Finite Automata

Andris Ambainis, Arnolds Ķikusts, Māris Valdats

Springer eBooks•Jun 12, 2007•46 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
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.