Bisimulation relation for selected types of probabilistic and quantum automata

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

Abstrakty

EN

The first step to make transitional systems more efficient is to minimize the number of their states. A bisimulation relation is a mathematical tool that helps in searching for equivalent systems, what is useful in the minimization of algorithms. For two transition systems bisimulation is a binary relation associating systems which behave in the same way in the sense that one system simulates the other and viceversa. The definition for classical systems is clear and simple, but what happens with nondeterministic, probabilistic and quantum systems? This will be the main topic of this article.

Słowa kluczowe

EN

bisimulation relation; probabilistic automata; quantum automata

PL

relacja bisymulacji; automat probabilistyczny; automat kwantowy

• Wydawca: Wydawnictwo Uniwersytetu Humanistyczno-Przyrodniczego im. Jana Długosza w Częstochowie
• Czasopismo: Scientific Issues of Jan Długosz University in Częstochowa. Mathematics
• Rocznik: 2011
• Tom: Vol. 16
• Strony: 135--140
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Siedlecka-Lamch O.

• Institute of Computer and Information Sciences Częstochowa University of Technology ul. Dąbrowskiego 69, 42-200 Częstochowa, Poland

Bibliografia

• [1] A. Ambainis, R. Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. In: 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society, pp. 332-341, 1998.
• [2] M. Hirvensalo. Quantum Computing, 2nd ed. Springer, Berlin 2003.
• [3] J.E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd ed. Addison-Wesley, Readling, Mass. 2001.
• [4] A. Kondacs, J. Watrous. On the power of quantum finite state automata. In: 38th Annual Symposium on Foundations of Computer Science, FOCS '97, October 19-22, 1997, Miami Beach, Florida, USA. IEEE Computer Society, pp. 66-75, 1997.
• [5] S. Krivoi, L. Matveyeva, Ye. Lukianova, O. Siedlecka. Ontology view on automata theory. International Journal "Information Theories and Applications", 15(4), 337-344, 2008.
• [6] C. Moore, J.P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2), 275-306, 2000.
• [7] M. Nielsen, Ch. Clausen. Bisimulation, games, and logic. In: Proceedings of the Colloquium in Honor of Arto Salomaa on Results and Trends in Theoretical Computer Science, pp. 289-306, Springer, London 1994.
• [8] O. Siedlecka. Minimizaction of reactive probabilistic automata. In: International Book Series Information Science and Computing–Algorithmic and Mathematical Foundations of the Artificial Intelligence, number 1, pp. 75-80. ITNEA, 2008.
• [9] O. Siedlecka-Lamch. A minimization algorithm of 1-way quantum finite automata. Metody Informatyki Stosowanej, 25(4), 73-79, 2010.
• [10] A. Sokolova, E.P. de Vink. Probabilistic automata: System types, parallel composition and comparison. In: Validation of Stochastic Systems: A Guide to Current Research, pp. 1-43. LNCS 2925, 2004.