تقرير
Undecidability of MM-QFAs Language Equivalence Problem
| العنوان: | Undecidability of MM-QFAs Language Equivalence Problem |
|---|---|
| المؤلفون: | Lin, Tianrong |
| سنة النشر: | 2013 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science, F.1.1, F.4.3 |
| الوصف: | Let $L_{>\lambda}(\mathcal{A})$ and $L_{\geq\lambda}(\mathcal{A})$ be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)}) $\mathcal{A}$ with strict and non-strict cut-point $\lambda$, respectively. We consider the language equivalence problem and show the following 1. both strict and non-strict language equivalence are undecidable; 2. we provide an another proof of the undecidability of non-strict and strict emptiness of MM-QFA and EQFA, and then reducing the language equivalence problem to emptiness problem; 3. lastly, we obtain some other properties which can be derived from the above results. Comment: This paper has been withdrawn since the topic is boring |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1308.3301 |
| رقم الأكسشن: | edsarx.1308.3301 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |