Document Open Access Logo

Approximating Probabilistic Automata by Regular Languages

Authors Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

PDF

File

Thumbnail PDF
PDF
LIPIcs.CSL.2018.14.pdf
  • Filesize: 0.56 MB
  • 23 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
Keywords
  • Probabilistic Finite Automata
  • Regular Languages
  • Ambiguity

Metrics

Abstract

A probabilistic finite automaton (PFA) A is said to be regular-approximable with respect to (x,y), if there is a regular language that contains all words accepted by A with probability at least x+y, but does not contain any word accepted with probability at most x. We show that the problem of determining if a PFA A is regular-approximable with respect to (x,y) is not recursively enumerable. We then show that many tractable sub-classes of PFAs identified in the literature - hierarchical PFAs, polynomially ambiguous PFAs, and eventually weakly ergodic PFAs - are regular-approximable with respect to all (x,y). Establishing the regular-approximability of a PFA has the nice consequence that its value can be effectively approximated, and the emptiness problem can be decided under the assumption of isolation.

Cite As Get BibTex

Rohit Chadha, A. Prasad Sistla, and Mahesh Viswanathan. Approximating Probabilistic Automata by Regular Languages. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CSL.2018.14

Author Details

Rohit Chadha
  • University of Missouri, Columbia, USA
A. Prasad Sistla
  • University of Illinois, Chicago, Chicago, USA
Mahesh Viswanathan
  • University of Illinois, Urbana-Champaign, Urbana, USA

Funding

  • Chadha, Rohit: NSF CNS 1314338 and NSF CNS 1553548
  • Sistla, A. Prasad: NSF CNS 1314485 and NSF CCF 1564296
  • Viswanathan, Mahesh: NSF CSR 1422798 and NSF CPS 1329991

References

  1. C. Baier and M. Größer. Recognizing ω-regular languages with probabilistic automata. In 20th IEEE Symposium on Logic in Computer Science, pages 137-146, 2005. Google Scholar
  2. Y. Ben and A. P. Sistla. Model checking failure-prone open systems using probabilistic automata. In 13th International Symposium on Automated Technology for Verification and Analysis, volume 9364 of Lecture Notes in Computer Science, pages 148-165. Springer, 2015. Google Scholar
  3. A. Bertoni. The solution of problems relative to probabilistic automata in the frame of the formal languages theory. In GI Jahrestagung, pages 107-112, 1974. Google Scholar
  4. A. Bertoni. Mathematical methods of the theory of stochastic automata. In 3rd Symposium of Mathematical Foundations of Computer Science, volume 28 of Lecture Notes in Computer Science, pages 9-22. Springer, 1975. Google Scholar
  5. R. Chadha, A. P. Sistla, and M. Viswanathan. Probabilistic Büchi automata with non-extremal acceptance thresholds. In 11th International Conference on Verification, Model checking and Abstract Interpretation, pages 103-117, 2010. Google Scholar
  6. R. Chadha, A. P. Sistla, and M. Viswanathan. Power of randomization in automata on infinite strings. Logical Methods in Computer Science, 7(3):1-22, 2011. Google Scholar
  7. R. Chadha, A. P. Sistla, M. Viswanathan, and Y. Ben. Decidable and expressive classes of probabilistic automata. In 18th International Conference on Foundations of Software Science and Computation Structures, volume 9034 of Lecture Notes in Computer Science, pages 200-214. Springer, 2015. Google Scholar
  8. R. Chadha, A. Prasad Sistla, and M. Viswanathan. Emptiness under isolation and the value problem for hierarchical probabilistic automata. In Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, volume 10203 of Lecture Notes in Computer Science, pages 231-247, 2017. Google Scholar
  9. R. Chadha, A.P. Sistla, and M. Viswanathan. Power of randomization in automata on infinite strings. In 20th International Conference on Concurrency Theory, pages 229-243, 2009. Google Scholar
  10. R. Chadha, A.P. Sistla, and M. Viswanathan. Probabilistic automata with isolated cut-points. In 38th International Symposium on Mathematical Foundation of Computer Science, pages 254-265, 2013. Google Scholar
  11. A. Condon and R. J. Lipton. On the complexity of space bounded interactive proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 462-467, 1989. Google Scholar
  12. W. Czerwinski and S. Lasota. Regular separability of one counter automata. In 32nd IEEE Symposium on Logic in Computer Science, pages 1-12, 2017. Google Scholar
  13. L. Daviaud, M. Jurdzinski, R. Lazic, F. Mazowiecki, G. A. Pérez, and James Worrell. When is containment decidable for probabilistic automata? In 45th International Colloquium on Automata, Languages, and Programming, 2018. To appear. Google Scholar
  14. N. Fijalkow, H. Gimbert, E. Kelmendi, and Youssouf Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. Logical Methods in Computer Science, 11(2), 2015. Google Scholar
  15. N. Fijalkow, H. Gimbert, and Y. Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. In 27th IEEE Symposium on Logic in Computer Science, pages 295-304, 2012. Google Scholar
  16. N. Fijalkow, C. Riveros, and J. Worrell. Probabilistic automata of bounded ambiguity. In the International Conference on Concurrency Theory, pages 19:1-19:14, 2017. Google Scholar
  17. N. Fijalkow and M. Skrzypczak. Irregular behaviours for probabilistic automata. In Reachability Problems, pages 33-36, 2015. Google Scholar
  18. H. Gimbert and Y. Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In 37th International Colloquium on Automata, Languages and Programming, pages 527-538, 2010. Google Scholar
  19. J. Hajnal and M. S. Bartlett. Weak ergodicity in non-homogeneous markov chains. Mathematical proceedings of the Cambridge Philosophical Society, 54(02):233-246, 1958. Google Scholar
  20. O. H. Ibarra and B. Ravikumar. On sparseness, ambiguity and other decision problems for acceptors and transducers. In 3rd Annual Symposium on Theoretical Aspects of Computer Science, pages 171-179, 1986. Google Scholar
  21. G. Jacob. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoretical Computer Science, 5(2):183-204, 1977. Google Scholar
  22. A. Mandel and I. Simon. On finite semigroups of matrices. Theoretical Computer Science, 5(2):101-111, 1977. Google Scholar
  23. A. Paz. Definite and quasidefinite sets of stochastic matrices. Proceedings of the American Mathematical Society, 16(4):634-641, 1965. URL: http://www.jstor.org/stable/2033893.
  24. A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971. Google Scholar
  25. T. Place and M. Separation for dot-depth two. In 32nd IEEE Symposium on Logic in Computer Science, pages 1-12, 2017. Google Scholar
  26. M. O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. Google Scholar
  27. C. Reutenauer. Propriétés arithmétiques et topologiques de séries rationnelles en variables non commutatives, 1997. Thése troisiéme cycle, Université Paris VI. Google Scholar
  28. A. Weber and H. Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991. Google Scholar
  29. J. Wolfowitz. Products of indecomposable, aperiodic, stochastic matrices. Proceedings of the American Mathematical Society, 14(5):733-737, 1963. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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