A minimization algorithm of 1-way quantum finite automata

• Autorzy: Siedlecka-Lamch O.
• Języki publikacji: EN

Abstrakty

EN

A minimization of finite automata is important for designing of computer's hardware and software. A finite automata can be a model of any system with finite number of states. A limitation of number of states will save resources and time. In this article 1-way quantum finite automata is presented. We describe its characteristics, behaviour and languages accepted by it. This type of automata can be in future exploited to design and checking the behaviour of quantum systems, in lexical anaiyzer of a compiler, that will be used on quantum computers, or in verification systems. Also in this case Iimitation of states will save resources. The article holds formulated definition of indistinguishableness relation for 1-way quantum finite automata, on base of which minimization algorithm was created. Additionally, the algorithm 's complexity analysis and example of behaviour is holded.

Słowa kluczowe

EN

theory of computation; computation by abstract devices; models of computation; automata; mathematical logic and formal lanquages; quantum automata; 1-way quantum finite automata; minimization algorithm; indistinguishableness relation

PL

teoria obliczeń; obliczenia przez urządzenia abstrakcyjne; model obliczeniowy; automat; logika matematyczna i języki formalne; 1-kwantowy model automatów skończonych; algorytm minimalizacji

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 4 (24)
• Strony: 73--79
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Siedlecka-Lamch O.

• Institute of Computer and Information Sciences, Częstochowa University of Technology, Częstochowa

Bibliografia

• [l] A.Y. Aho, M.S. Lam, R. Sethi, J. D. Ullan, 2006, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison Wesley.
• [2] A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer, D. Therien, 2006, Algebraic Results on Quantum Automata. Theory of Computing Systems, vol. 39, no. l, pp. 165-188.
• [3] A. Ambainis, R.F. Bonner, R. Freivalds, A. Kikusts, 1999, Probabilities to Accept Languages by Quantum Finite Automata, COCOON, Lecture Notes in Computer Science, vol. 1627, pp. 174-183.
• [4] A. Ambainis, R. FreivaJds, 1998, 1-way quantum finite automata: strengths, weaknesses and generalizations, FOCS '98: Proceedings of the 39th ASFCS, IEEE, Washington, DC, USA, pp. 332-341.
• [5] A. Ambainis, A. Kikusts, 2001, Exact Results for Accepting Probabilities of QuantumAutomata, MFCS, Lecture Notes in Computer Science, Springer-Verlag, vol. 2136, pp. 135-147.
• [6] A. Ambainis, A. Kikusts, M. Valdats, 2001, On the Class of Languages Recognizable by 1- Way Quantum Finite Automata, STACS, Lecture Notes in Computer Science, Springer, vol. 2010, pp. 75-86.
• [7] J .A. Brzozowski, 1962, Canonical Regular Expressions and Minimal State Graphs for Definite Events, Proceedings of the SMTA, Polytechnic Press of the Polytechnic Institute of Brooklyn, vol. 12, pp. 529-561.
• [8] J. Gruska, 1999, Quantum Computing; McGraw-Hill.
• [9] J .E. Hopcroft, 1971, An n log n algorithm for minimiting the states in a finite automaton, The Theory of Machines and Computations, Academic Press, pp. 189-196.
• [10] J.E. Hopcroft, R. Motwani, J.D. Ullman, 2000, Introduction to Automata Theory, Languages, and Computation (2nd Edition), Addison Wesley.
• [11] A. Kondacs. J. Watrous, 1997, On the Power of Quantum Finite State Automata, IEEE Symposium on Foundations of Computer Science, pp. 66--75.
• [12] S. K.ryvyi, L. Matveyeva, E. Lukianowa, O. Siedlecka, 2008, Ontology View on Automata Theary, Intern. Journ. Information and Applications, vol. 15, no. 4, pp. 337-344.
• [13] C. Moore, J.P. Crutchiield, 2000, Quantum automata and quantum grammars, Theoretical Computer Science, vol. 237, no. 1-2, pp. 275-306.