کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430729 | 688133 | 2012 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Another approach to the equivalence of measure-many one-way quantum finite automata and its application Another approach to the equivalence of measure-many one-way quantum finite automata and its application](/preview/png/430729.png)
In this paper, we present a much simpler, direct and elegant approach to the equivalence problem of measure many one-way quantum finite automata (MM-1QFAs). The approach is essentially generalized from the work of Carlyle [J.W. Carlyle, Reduced forms for stochastic sequential machines, J. Math. Anal. Appl. 7 (1963) 167–175]. Namely, we reduce the equivalence problem of MM-1QFAs to that of two (initial) vectors. As an application of the approach, we utilize it to address the equivalence problem of enhanced one-way quantum finite automata (E-1QFAs) introduced by Nayak [A. Nayak, Optimal lower bounds for quantum automata and random access codes, in: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 369–376]. We prove that two E-1QFAs A1A1 and A2A2 over Σ are equivalence if and only if they are n12+n22−1-equivalent where n1n1 and n2n2 are the numbers of states in A1A1 and A2A2, respectively. As an important consequence, we obtain that it is decidable whether or not L(A1)=L(A2)L(A1)=L(A2) where L(A)⊆Σ⁎L(A)⊆Σ⁎ denotes the set recognizable by MM-1QFA AA (or by E-1QFA AA) with cutpoint (or with non-strict cutpoint). This also extends a theorem of Eilenberg.
► We present a much simple approach to the equivalence of measure-many one-way quantum finite automata (MM-1QFAs).
► We utilize the approach to address the equivalence problem of Enhanced one-way quantum finite automata (E-1QFAs).
► We generalize a theorem of Eilenberg to MM-1QFAs and E-1QFAs.
Journal: Journal of Computer and System Sciences - Volume 78, Issue 3, May 2012, Pages 807–821