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. © 2013 Springer-Verlag.
Quantum finite automata and linear context-free languages: a decidable problem / Alberto, Bertoni; Christian, Choffrut; D'ALESSANDRO, Flavio. - STAMPA. - 7907 LNCS:(2013), pp. 82-93. (Intervento presentato al convegno 17th International Conference on Developments in Language Theory, DLT 2013 tenutosi a Marne-la-Vallee; France) [10.1007/978-3-642-38771-5_9].
Quantum finite automata and linear context-free languages: a decidable problem
D'ALESSANDRO, Flavio
2013
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. © 2013 Springer-Verlag.| File | Dimensione | Formato | |
|---|---|---|---|
|
Bertoni_Quantum_2013.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
424.41 kB
Formato
Adobe PDF
|
424.41 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
