This paper continues the study of measure-once finite quantum automata building on work by Bertoni et al. and Blondel et al. We investigate conditions ensuring 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 decidable whether or not they have a nonempty intersection
Quantum Automata and Languages of Finite Index / Benso, Andrea; D'Alessandro, Flavio; Papi, Paolo. - 15050:(2024), pp. 88-103. (Intervento presentato al convegno RP 2024, Reachability Problems tenutosi a TU Technical University, Vienna, Austria) [10.1007/978-3-031-72621-7].
Quantum Automata and Languages of Finite Index
Flavio D'Alessandro
;Paolo Papi
2024
Abstract
This paper continues the study of measure-once finite quantum automata building on work by Bertoni et al. and Blondel et al. We investigate conditions ensuring 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 decidable whether or not they have a nonempty intersectionI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
