Zestawienie i porównanie automatów probabilistycznych i kwantowych

• Autorzy: Siedlecka-Lamch O.

Warianty tytułu

EN

Summary and comparison of probabilistic and quantum automata

• Języki publikacji: PL

Abstrakty

PL

Większość systemów informatycznych można modelować z wykorzystaniem różnego rodzaju automatów skończonych: deterministycznych, niedeterministycznych, probabilistycznych itp. Automaty te można badać pod kątem osiągalności określonych stanów i dzięki temu sprawdzać, czy system może znaleźć się w stanie krytycznym, błędnym, niechcianym. Mamy również możliwość dokonania operacji minimalizacji automatów. Praktycznie ogranicza się to do znalezienia stanów nadmiarowych i nieosiągalnych – dzięki czemu mamy również sposobność zminimalizować oryginalny, modelowany system, zaoszczędzić na dokonywanych operacjach, pamięci, a nawet sprzęcie.

EN

Most IT systems can be modeled with the use of various types of finite automata: deterministic, non-deterministic, probabilistic, etc. These automatons can be tested for reachability of certain states and thus we can check whether the system can be in a critical, erroneous or unwanted state. We also have the ability to perform the operation of automata minimization. Practically, this is limited to finding redundant and unreachable states – so we also have the opportunity to minimize the original, modeled system, save on operations amount, memory, and even hardware.

Słowa kluczowe

PL

automat skończony; automat probabilistyczny; bisymulacja

EN

finite automata; probabilistic automata; bisimulation

• Wydawca: Oficyna Wydawnicza Europejskiej Uczelni
• Czasopismo: Studia i Materiały / Europejska Uczelnia Informatyczno-Ekonomiczna w Warszawie
• Rocznik: 2017
• Tom: Nr 1(13)
• Strony: 77--83
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Siedlecka-Lamch O.

• Politechnika Częstochowska, ul. J.H. Dąbrowskiego 69, 42-201 Częstochowa, Polska

Bibliografia

• [1] Aho A.V., Lam M.S., R. Sethi, Ullman J. D., Compilers: Principles, Techniques, and Tools (2nd Edition), Addison, Wesley 2006.
• [2] Ambainis, A., and Freivalds, R. 1-way quantum finite automata: strengths, weaknesses and generalizations. In FOCS ’98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (Washington, DC, USA, 1998), IEEE Computer Society, pp. 332–341, 1998.
• [3] Ambainis A., Beaudry M., Golovkins M., Kikusts A., Mercer M., Thrien D., Algebraic Results on Quantum Automata, Theory of Computing Systems, vol. 39, no. 1, pp. 165-188, 2006.
• [4] Gruska J., Quantum Computing, McGraw-Hill, 1999.
• [5] Kondacs A. and Watrous J., On the power of quantum finite state automata. In IEEE, Symposium on Foundations of Computer Science, pages 66-75, 1997.
• [6] Kryvyi S., Matveyeva L., Lukianova E., Siedlecka O., Ontology view on automata theory. International Journal Information Theories and Applications, 15(4):337-344, 2008.
• [7] Moore C., Crutchfield J. P., Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2):275-306, 2000.
• [8] Siedlecka-Lamch O., A Minimization Algorithm of 1-way Quantum Finite Automata, Metody Informatyki Stosowanej nr 4/2010 (25), str. 73-79, 2010.
• [9] Sokolova A., de Vink E.P., Probabilistic automata: System types, parallel composition and comparison. In Validation of Stochastic Systems: A Guide to Current Research, pages 1-43. LNCS 2925, 2004.