The Library
The big-O problem for labelled markov chains and weighted automata
Tools
Tools
Tools
Chistikov, Dmitry, Kiefer, Stefan, Murawski, Andrzej S. and Purser, David (2020) The big-O problem for labelled markov chains and weighted automata. In: 31st International Conference on Concurrency Theory (CONCUR 2020), 1-4 Sep 2020. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 171 41:1-41:19. ISBN 9783959771603. doi:10.4230/LIPIcs.CONCUR.2020.41 ISSN 1868-8969.
|
PDF
WRAP-The-big-O-problem-labelled-markov-chains-weighted-automata-Purser-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (725Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.CONCUR.2020.41
Abstract
Given two weighted automata, we consider the problem of whether one is big-O 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 big-O of another, the problem of finding or approximating the associated constant is also undecidable. Our positive results show that the big-O problem is polynomial-time solvable for unambiguous automata, coNP-complete 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 big-O notation is exactly exp(ε).
| Item Type: | Conference Item (Paper) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
|||||||||||||||
| Library of Congress Subject Headings (LCSH): | Machine theory -- Mathematical models, Computer logic, Markov processes, Mathematical statistics, Probabilities | |||||||||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||||||||
| ISBN: | 9783959771603 | |||||||||||||||
| ISSN: | 1868-8969 | |||||||||||||||
| Official Date: | 26 August 2020 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 171 | |||||||||||||||
| Page Range: | 41:1-41:19 | |||||||||||||||
| DOI: | 10.4230/LIPIcs.CONCUR.2020.41 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
| Date of first compliant deposit: | 13 May 2020 | |||||||||||||||
| Date of first compliant Open Access: | 16 July 2020 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||
| Title of Event: | 31st International Conference on Concurrency Theory (CONCUR 2020) | |||||||||||||||
| Type of Event: | Conference | |||||||||||||||
| Date(s) of Event: | 1-4 Sep 2020 | |||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
