Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
73--79
Opis fizyczny
Bibliogr. 13 poz., rys.
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPS3-0018-0078