Quantum finite automata and linear context-free languages: a decidable problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2013
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929390998257664 |
|---|---|
| author | Bertoni, A. Choffrut, Ch. D'Alessandro, F. |
| author_facet | Bertoni, A. Choffrut, Ch. D'Alessandro, F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1303_2967 |
| institution | arXiv |
| publishDate | 2013 |
| record_format | arxiv |
| spellingShingle | Quantum finite automata and linear context-free languages: a decidable problem Bertoni, A. Choffrut, Ch. D'Alessandro, F. Formal Languages and Automata Theory 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. |
| title | Quantum finite automata and linear context-free languages: a decidable problem |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/1303.2967 |