Quantum finite automata and linear context-free languages: a decidable problem

DOI10.1007/978-3-642-38771-5_9MaRDI QIDQ5300831zbMATH OpenOpenAlexFDO

Authors Flavio D'Alessandro, Alberto Bertoni, Christian Choffrut

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.2967

zbMATH Keywords

algebraic groupscontext-free languagesdecidabilityquantum automata

Mathematics Subject Classification ID

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

Abstract: We consider the so-called measure once finite quantum automata model introduced by Moore and Crutchfield in 2000. We show that given a language recognized by such a device and a linear context-free language, it is recursively decidable whether or not they have a nonempty intersection. This extends a result of Blondel et al. which can be interpreted as solving the problem with the free monoid in place of the family of linear context-free languages.

Recommendations

• On the decidability of the intersection problem for quantum automata and context-free languages
• Decidable and Undecidable Problems about Quantum Automata
• Implementation and Application of Automata
• Characterizations of 1-Way Quantum Finite Automata
• scientific article; zbMATH DE number 1688355

Cited in

(9)

• On injectivity of quantum finite automata
• Undecidability on quantum finite automata
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• A decision procedure for well-formed linear quantum cellular automata
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• On the decidability of the intersection problem for quantum automata and context-free languages
• Decidable and Undecidable Problems about Quantum Automata
• On the intersection problem for quantum finite automata

This page was built for publication: Quantum finite automata and linear context-free languages: a decidable problem

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