publication . Conference object . Preprint . 2015

Distinguishing Hidden Markov Chains

Stefan Kiefer; A. Prasad Sistla;
Open Access
  • Published: 08 Jul 2015
  • Publisher: ACM Press
  • Country: United Kingdom
Comment: This is the full version of a LICS'16 paper
Persistent Identifiers
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Formal Languages and Automata Theory, Hidden Markov model, Exponential growth, Runtime verification, Mathematical model, Time complexity, Markov process, symbols.namesake, symbols, Algorithm, Signal processing, Computer science, Probabilistic logic
Funded by
NSF| TWC: Medium: Collaborative: Automated Formal Analysis of Security Protocols with Private Coin Tosses
  • Funder: National Science Foundation (NSF)
  • Project Code: 1314485
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computer and Network Systems
NSF| SHF: Small: Static and Dynamic Techniques for Correctness of Probabilistic Systems
  • Funder: National Science Foundation (NSF)
  • Project Code: 1319754
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
28 references, page 1 of 2

[1] P. Ailliot, C. Thompson, and P. Thomson. Space-time modelling of precipitation by using a hidden Markov model and censored Gaussian distributions. Journal of the Royal Statistical Society, 58(3):405-426, 2009.

[2] M. Alexandersson, S. Cawley, and L. Pachter. SLAM: Cross-species gene finding and alignment with a generalized pair hidden Markov model. Genome Research, 13:469-502, 2003. [OpenAIRE]

[3] R. Alur, C. Courcoubetis, and M. Yannakakis. Distinguishing tests for nondeterministic and probabilistic machines. In Proceedings of STOC, pages 363-372. ACM, 1995. [OpenAIRE]

[4] C. Baier, J. Klein, S. Klu¨ppelholz, and S. Ma¨rcker. Computing conditional probabilities in Markovian models efficiently. In Proceedings of TACAS, volume 8413 of LNCS, pages 515-530, 2014.

[5] N. Bertrand, S. Haddad, and E. Lefaucheux. Accurate approximate diagnosability of stochastic systems. In Proceedings of LATA, pages 549-561, 2016.

[6] F.-S. Chen, C.-M. Fu, and C.-L. Huang. Hand gesture recognition using a real-time tracking method and hidden Markov models. Image and Vision Computing, 21(8):745-758, 2003.

[7] T. Chen and S. Kiefer. On the total variation distance of labelled Markov chains. In Proceedings of CSL-LICS, pages 33:1-33:10, 2014.

[8] G. Churchill. Stochastic models for heterogeneous DNA sequences. Bulletin of Mathematical Biology, 51(1):79-94, 1989.

[9] M. Crouse, R. Nowak, and R. Baraniuk. Wavelet-based statistical signal processing using hidden Markov models. IEEE Transactions on Signal Processing, 46(4):886-902, April 1998. [OpenAIRE]

[10] L. Doyen, T. Henzinger, and J.-F. Raskin. Equivalence of labeled Markov chains. International Journal of Foundations of Computer Science, 19(3):549-563, 2008.

[11] R. Durbin. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.

[12] S. Eddy. What is a hidden Markov model? Nature Biotechnology, 22(10):1315-1316, October 2004.

[13] A. Fraser. Hidden Markov Models and Dynamical Systems. Society for Industrial and Applied Mathematics, 2008.

[14] J. Gough, K. Karplus, R. Hughey, and C. Chothia. Assignment of homology to genome sequences using a library of hidden Markov models that represent all proteins of known structure. Journal of Molecular Biology, 313(4):903-919, 2001. [OpenAIRE]

[15] H. Ito, S.-I. Amari, and K. Kobayashi. Identifiability of hidden Markov information sources and their minimum degrees of freedom. IEEE Transactions on Information Theory, 38(2):324-333, March 1992.

28 references, page 1 of 2
Any information missing or wrong?Report an Issue