Chistikov, Dmitry ;
Kiefer, Stefan ;
Murawski, Andrzej S. ;
Purser, David
The BigO Problem for Labelled Markov Chains and Weighted Automata
Abstract
Given two weighted automata, we consider the problem of whether one is bigO of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second.
We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is bigO of another, the problem of finding or approximating the associated constant is also undecidable.
Our positive results show that the bigO problem is polynomialtime solvable for unambiguous automata, coNPcomplete for unlabelled weighted automata (i.e., when the alphabet is a single character) and decidable, subject to Schanuel’s conjecture, when the language is bounded (i.e., a subset of w_1^* … w_m^* for some finite words w_1,… ,w_m).
On labelled Markov chains, the problem can be restated as a ratio total variation distance, which, instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem is related to εdifferential privacy, for which the optimal constant of the bigO notation is exactly exp(ε).
BibTeX  Entry
@InProceedings{chistikov_et_al:LIPIcs:2020:12853,
author = {Dmitry Chistikov and Stefan Kiefer and Andrzej S. Murawski and David Purser},
title = {{The BigO Problem for Labelled Markov Chains and Weighted Automata}},
booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)},
pages = {41:141:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771603},
ISSN = {18688969},
year = {2020},
volume = {171},
editor = {Igor Konnov and Laura Kov{\'a}cs},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12853},
URN = {urn:nbn:de:0030drops128534},
doi = {10.4230/LIPIcs.CONCUR.2020.41},
annote = {Keywords: weighted automata, labelled Markov chains, probabilistic systems}
}
26.08.2020
Keywords: 

weighted automata, labelled Markov chains, probabilistic systems 
Seminar: 

31st International Conference on Concurrency Theory (CONCUR 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 