On the intersection problem for quantum finite automata

DOI10.1016/J.TCS.2025.115454MaRDI QIDQ6930231zbMATH OpenFDO

Authors Andrea Benso, Flavio D'Alessandro, Paolo Papi

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115454

zbMATH Keywords

algebraic groupscontext-free languagesdecidabilitymatrix semigroupsquantum automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Cites work

• Algorithms in real algebraic geometry
• Automata and quantum computing
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Decidable and Undecidable Problems about Quantum Automata
• Derivation-bounded languages
• Grammatical characterizations of NPDAs and VPDAs with counters
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 47220 (Why is no real title available?)
• scientific article; zbMATH DE number 3504469 (Why is no real title available?)
• scientific article; zbMATH DE number 3572058 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2016138 (Why is no real title available?)
• scientific article; zbMATH DE number 2040892 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• On bounded rational trace languages
• On strongest algebraic program invariants
• On the computation of the Zariski closure of finitely generated groups of matrices
• On the decidability of semigroup freeness.
• On the decidability of the intersection problem for quantum automata and context-free languages
• On the index of a context-free grammar and language
• Partial algorithm problems for context free languages
• Polynomial Invariants for Affine Programs
• Quantum automata and algebraic groups
• Quantum automata and quantum grammars
• Quantum computing.
• Quantum finite automata and linear context-free languages: a decidable problem
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Simple matrix languages
• Techniques for showing the decidability of the boundedness problem of language acceptors
• The characterization of nonexpansive grammars by rational power series
• The growth function of context-free languages
• Toric varieties from cyclic matrix semigroups
• Transductions des langages de Chomsky

Cited in

(1)

• On some decision problems on quantum automata

This page was built for publication: On the intersection problem for quantum finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930231)