An Algebraic Approach to the Study of Quantum Finite Automata
Andrea Benso · Florence Research (University of Florence) · 2025
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.