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 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.
On the decidability of the intersection problem for quantum automata and context-free languages / A., Bertoni; C., Choffrut; D'Alessandro, Flavio. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - STAMPA. - 25:(2014), pp. 1065-1081. [10.1142/S0129054114400243]
On the decidability of the intersection problem for quantum automata and context-free languages
D'ALESSANDRO, Flavio
2014
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.