# Publications on labelled Markov chains

**D. Chistikov, S. Kiefer, A. Murawski, D. Purser. The big-O problem.**Logical Methods in Computer Science (2022). [doi]Given two weighted automata (or labelled Markov chains), is there a constant

*c*such that the weight of every word in the first automaton is at most*c*times its weight in the second?

**D. Chistikov, S. Kiefer, A. Murawski, D. Purser. The big-O problem for labelled Markov chains and weighted automata.**CONCUR 2020. [DROPS] Extended version in Logical Methods in Computer Science (2022).

**D. Chistikov, A. Murawski, D. Purser. Asymmetric distances for approximate differential privacy.**CONCUR 2019. [DROPS]We measure distances between states in labelled Markov chains in the spirit of bisimilarity relation. It turns out that

*asymmetric*distance functions are, in some sense, better.

**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.