On the intersection problem for quantum finite automata

Abstract: In this talk we consider the quantum finite automata according to the model "measure-once" introduced by Moore and Crutchfield in the late 90's. More precisely, we are interested in some results that prove the decidability of the Emptiness problem (for languages accepted by the model with strict threshold) obtained by Blondel, Jeandel, Koiran, and Portier, and of one of its generalisation, called the Intersection Problem, obtained by Bertoni, Choffrut et al. In this presentation, we will highlight, in particular, the role of algebraic groups in defining the aforementioned decidability constructs, and, time permitting, describe some recent developments.

formal languages and automata theory

Audience: researchers in the topic

( slides | video )

One FLAT World Seminar