PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

On effective algorithms solving regularity of Markov chains

Treść / Zawartość
Identyfikatory
Warianty tytułu
PL
Efektywne algorytmy rozstrzygania regularności łańcuchów Markowa
Języki publikacji
EN
Abstrakty
EN
We propose algorithms deciding whether a Markov chain with an n_n transition matrix M is regular. The lowest complexity of such an algorithm can be not greater than O(n 3 ) and we argue that it cannot be essentially diminished.
PL
W pracy proponujemy algorytmy rozstrzygające regularność łańcuchów Markowa o macierzy przejść rozmiaru n x n. Najniższa złożoność takiego algorytmu może być nie większa niż O(n 3 i podana jest argumentacja, że nie można jej istotnie obniżyć.
Rocznik
Tom
Strony
5--25
Opis fizyczny
Bibliogr. 13 poz.
Twórcy
autor
autor
  • Polish-Japanese Academy of Information Technology, Warsaw, Poland
autor
  • Faculty of Computer Science, Bialystok University of Technology, Bialystok, Poland
Bibliografia
  • [1] Aho A.V., Hopcroft J.E., Ullman J.D.: Design and Analysis of Computer Algorithms, Addison-Vesley, 1981.
  • [2] Cormen T., Leiserson C., Riverst R., Stein C.: Introduction to Algorithms, Massachusetts Institute of Technology, 2001.
  • [3] Dańko A., Da´nko W.: Improving Pseudo-Random Generators, International Conference on Biometrics and Kansei Engineering 24-28 June, Cieszyn, Poland, pp. 163-166, 2009.
  • [4] Dańko W.: The Set of Probabilistic Algorithmic Formulas Valid in a Finite Structure is Decidable with Respect to Its Diagram, Fundamenta Informaticae, vol. 19 (3-4), pp. 417-431, 1993.
  • [5] Feller W.: An Introduction to Probability Theory and Its Applications, John Wiley and Sons, Inc., New York, London, 1961.
  • [6] Josifescu M.: Finite Markov Processes and Their Applications, JohnWiley and Sons, New York, London 1988.
  • [7] Kubik L., Krupowicz A.: Introduction to Probability Theory and Its Applications, PWN, Warszawa, 1982, (in Polish).
  • [8] Mirkowska G., Salwicki A.: Algorithmic Logic, D.Reidel Publ. Co. & PWN, Warsaw, 1987.
  • [9] Modica G., Poggiolini L.: A First Course in Probability and Markov Chains, John Wiley and Sons, 2013.
  • [10] Mora´s K.: Markov Chains. Analysis of Regular Chains, bachelor thesis, Bialystok University of Technology, 2015, (in Polish).
  • [11] Ross S. M.: Introduction to Probability Models Academic Press, 2003.
  • [12] Rubino G., Sericola B.: Markov Chains and Dependability Theory, Cambridge University Press, 2014.
  • [13] Snell Laurie J.: Introduction to Probability, Random House Inc., New York, 1988.
Uwagi
PL
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f2bae4de-7891-4004-8103-d29cc3093b94
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.