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.
2014
quantum automata; context-free languages; algebraic varieties; decidability
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/780385
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact