On the Intersection Problem for Quantum Finite Automata

2024/06/19 by Andrea Benso, Benso, Andrea, Flavio D’Alessandro +3 · 1 citation
Computer Science · #03D05 #68Q45 #81P68 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.2406.13797

openalex publication_date 2024/06/19 · openalex created_date 2024/06/22 · openalex updated_date 2026/07/28

Abstract

This paper is a continuation of a previous study on the so-called measure once finite quantum automata model introduced by Moore and Crutchfield in 2000. We investigate conditions assuring that, given a language recognized by such a device and a language generated by a context-free grammar of finite index or by a matrix context-free grammar, it is recursively decidable whether or not they have a nonempty intersection.

Cited by

• Computing the Zariski closure of a finitely generated rational matrix group

Related

• Quantum finite automata and linear context-free languages: a decidable problem
• Characterizations of 1-Way Quantum Finite Automata
• Decidable and undecidable problems about quantum automata
• The class of languages recognizable by 1-way quantum finite automata is not closed under union
• Characterizations of one-way general quantum finite automata