Document Open Access Logo

The Big-O Problem for Labelled Markov Chains and Weighted Automata

Authors Dmitry Chistikov , Stefan Kiefer, Andrzej S. Murawski, David Purser

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.41.pdf
  • Filesize: 0.71 MB
  • 19 pages

Document Identifiers

Author Details

Dmitry Chistikov
  • Centre for Discrete Mathematics and its Applications (DIMAP) and Department of Computer Science, University of Warwick, Coventry, UK
Stefan Kiefer
  • Department of Computer Science, University of Oxford, UK
Andrzej S. Murawski
  • Department of Computer Science, University of Oxford, UK
David Purser
  • Centre for Discrete Mathematics and its Applications (DIMAP) and, Department of Computer Science, University of Warwick, Coventry, UK
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Chistikov, Dmitry: Supported in part by the Royal Society International Exchanges scheme (IEC\R2\170123).
  • Kiefer, Stefan: Supported by a Royal Society Research Fellowship.
  • Murawski, Andrzej S.: Supported by a Royal Society Leverhulme Trust Senior Research Fellowship and the International Exchanges Scheme (IE161701).
  • Purser, David: Supported by the UK EPSRC Centre for Doctoral Training in Urban Science (EP/L016400/1) and in part by the Royal Society International Exchanges scheme (IEC\R2\170123).

Acknowledgements

The authors would like to thank to Engel Lefaucheux, Joël Ouaknine, and James Worrell for discussions during the development of this work.

Cite As Get BibTex

Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, and David Purser. The Big-O Problem for Labelled Markov Chains and Weighted Automata. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) 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(ε).

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
Keywords
  • weighted automata
  • labelled Markov chains
  • probabilistic systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? In ATVA, volume 6996 of Lecture Notes in Computer Science, pages 482-491. Springer, 2011. Google Scholar
  2. Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, and James Worrell. O-minimal invariants for linear loops. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 114:1-114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.114.
  3. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and computation in mathematics. Springer, 2nd edition, 2006. Google Scholar
  4. Konstantinos Chatzikokolakis, Daniel Gebler, Catuscia Palamidessi, and Lili Xu. Generalized Bisimulation Metrics. In Paolo Baldan and Daniele Gorla, editors, CONCUR 2014 - Concurrency Theory - 25th International Conference, CONCUR 2014, volume 8704 of Lecture Notes in Computer Science, pages 32-46. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44584-6_4.
  5. Taolue Chen and Stefan Kiefer. On the total variation distance of labelled Markov chains. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS 2014, pages 33:1-33:10. ACM, 2014. URL: https://doi.org/10.1145/2603088.2603099.
  6. Dmitry Chistikov, Andrzej S. Murawski, and David Purser. Asymmetric distances for approximate differential privacy. In Wan Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory, CONCUR 2019, volume 140 of LIPIcs, pages 10:1-10:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2019.10.
  7. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the Skolem problem for continuous linear dynamical systems. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 100:1-100:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.100.
  8. Thomas Colcombet. Unambiguity in automata theory. In Jeffrey O. Shallit and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, volume 9118 of Lecture Notes in Computer Science, pages 3-18. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19225-3_1.
  9. Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. Pérez, and James Worrell. When is containment decidable for probabilistic automata? In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 121:1-121:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.121.
  10. C. Dehnert, S. Junges, J.-P. Katoen, and M. Volk. A Storm is coming: A modern probabilistic model checker. In Proceedings of Computer Aided Verification (CAV), pages 592-600. Springer, 2017. Google Scholar
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. URL: https://doi.org/10.1007/11681878_14.
  12. Nathanaël Fijalkow. Undecidability results for probabilistic automata. SIGLOG News, 4(4):10-17, 2017. URL: https://dl.acm.org/citation.cfm?id=3157833.
  13. Shmuel Friedland and Hans Schneider. The growth of powers of a nonnegative matrix. SIAM J. Matrix Analysis Applications, 1(2):185-200, 1980. URL: https://doi.org/10.1137/0601022.
  14. Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey Shallit. Finding the growth rate of a regular or context-free language in polynomial time. Int. J. Found. Comput. Sci., 21(4):597-618, 2010. URL: https://doi.org/10.1142/S0129054110007441.
  15. Hugo Gimbert and Youssouf Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, volume 6199 of Lecture Notes in Computer Science, pages 527-538. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14162-1_44.
  16. Seymour Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, 1966. Google Scholar
  17. Seymour Ginsburg and Edwin H Spanier. Bounded algol-like languages. Transactions of the American Mathematical Society, 113(2):333-368, 1964. Google Scholar
  18. Cheng-Chao Huang, Jing-Cao Li, Ming Xu, and Zhi-Bin Li. Positive root isolation for poly-powers by exclusion and differentiation. Journal of Symbolic Computation, 85:148-169, 2018. 41th International Symposium on Symbolic and Alge-braic Computation (ISSAC’16). URL: https://doi.org/10.1016/j.jsc.2017.07.007.
  19. Stefan Kiefer. On computing the total variation distance of hidden Markov models. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 130:1-130:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.130.
  20. Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, Björn Wachter, and James Worrell. On the Complexity of Equivalence and Minimisation for Q-weighted Automata. Logical Methods in Computer Science, 9(1), 2013. URL: https://doi.org/10.2168/LMCS-9(1:8)2013.
  21. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation, 4:405-425, 1994. Google Scholar
  22. M. Kwiatkowska, G. Norman, and D. Parker. PRISM 4.0: Verification of probabilistic real-time systems. In Proceedings of Computer Aided Verification (CAV), volume 6806 of LNCS, pages 585-591. Springer, 2011. Google Scholar
  23. Serge Lang. Introduction to transcendental numbers. Addison-Wesley Pub. Co., 1966. Google Scholar
  24. Angus Macintyre and Alex J Wilkie. On the decidability of the real exponential field, 1996. Google Scholar
  25. Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani. On decidability of time-bounded reachability in CTMDPs. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 133:1-133:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.133.
  26. David Mestel. Quantifying information flow in interactive systems. In 32nd IEEE Computer Security Foundations Symposium, CSF 2019, Hoboken, NJ, USA, June 25-28, 2019, pages 414-427. IEEE, 2019. URL: https://doi.org/10.1109/CSF.2019.00035.
  27. David Mestel. Widths of Regular and Context-Free Languages. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.49.
  28. Albert R. Meyer and Larry J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th Annual Symposium on Switching and Automata Theory, College Park, Maryland, USA, October 25-27, 1972, pages 125-129. IEEE Computer Society, 1972. Google Scholar
  29. Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 366-379. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.27.
  30. Rohit J Parikh. On context-free languages. Journal of the ACM (JACM), 13(4):570-581, 1966. Google Scholar
  31. Azaria Paz. Introduction to probabilistic automata. Academic Press, 2014. Google Scholar
  32. Bjorn Poonen. Hilbert’s tenth problem over rings of number-theoretic interest. Note from the lecture at the Arizona Winter School on "Number Theory and Logic", 2003. URL: https://math.mit.edu/~poonen/papers/aws2003.pdf.
  33. Hans Schneider. The influence of the marked reduced graph of a nonnegative matrix on the Jordan form and on related properties: A survey. Linear Algebra and its Applications, 84:161-189, 1986. Google Scholar
  34. Marcel Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245-270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X.
  35. Bruno Sericola. Markov chains: theory and applications. John Wiley & Sons, 2013. Google Scholar
  36. Adam D. Smith. Efficient, Differentially Private Point Estimators. CoRR, abs/0809.4794, 2008. URL: http://arxiv.org/abs/0809.4794.
  37. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, and H. Raymond Strong, editors, Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 1973, pages 1-9. ACM, 1973. URL: https://doi.org/10.1145/800125.804029.
  38. Wen-Guey Tzeng. A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput., 21(2):216-227, 1992. URL: https://doi.org/10.1137/0221017.
  39. Wen-Guey Tzeng. On path equivalence of nondeterministic finite automata. Inf. Process. Lett., 58(1):43-46, 1996. URL: https://doi.org/10.1016/0020-0190(96)00039-7.
  40. Michel Waldschmidt. Diophantine Approximation on Linear Algebraic Groups, volume 326 of Grundlehren der mathematischen Wissenschaften (A Series of Comprehensive Studies in Mathematics). Springer, Berlin, Heidelberg, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact