Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

Publications on labelled Markov chains

  • D. Chistikov, A. Murawski, D. Purser. Asymmetric distances for approximate differential privacy. CONCUR 2019. [DROPS]
  • D. Chistikov, A. Murawski, D. Purser. Bisimilarity distances for approximate differential privacy. ATVA 2018. [arXiv]

    A pair of states in a labelled Markov chain can be bisimilar or not bisimilar. We extend this equivalence relation to a distance function which upper-bounds the δ parameter in approximate differential privacy.

  • D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell. On rationality of nonnegative matrix factorization. SODA 2017. Further version in SIAM Journal on Applied Algebra and Geometry (2017). [doi]

    We find a matrix for which the nonnegative rank over the reals and over the rationals are different. Consequently, state minimization of hidden Markov models may require irrational probabilities.

  • D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell. On restricted nonnegative matrix factorization. ICALP’16. [DROPS] [arXiv]

    There exists a pair of 3D polytopes with rational vertices, one inside the other, such that every intermediate polytope with 5 vertices must have a vertex with an irrational coordinate.