Document Open Access Logo

Decision Questions for Probabilistic Automata on Small Alphabets

Authors Paul C. Bell , Pavel Semukhin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.15.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Paul C. Bell
  • Department of Computer Science, Liverpool John Moores University, UK
Pavel Semukhin
  • Department of Computer Science, University of Oxford, UK

Cite As Get BibTex

Paul C. Bell and Pavel Semukhin. Decision Questions for Probabilistic Automata on Small Alphabets. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.15

Abstract

We study the emptiness and λ-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and λ-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is over {0, 1}, we show they are in NP. In contrast to the Skolem-hardness of the λ-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with commuting transition matrices, we prove NP-hardness of the λ-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Computability
  • Theory of computation → Probabilistic computation
Keywords
  • Probabilistic finite automata
  • unary alphabet
  • emptiness problem
  • bounded ambiguity

Metrics

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

Related Versions

References

  1. S. Akshay, Timos Antonopoulos, Joël Ouaknine, and James Worrell. Reachability problems for Markov chains. Information Processing Letters, 115(2):155-158, 2015. Google Scholar
  2. Paul C. Bell. Polynomially ambiguous probabilistic automata on restricted languages. In International Colloquium on Automata, Languages, and Programming, number 105 in ICALP'19, pages 1-14, 2019. Google Scholar
  3. Paul C. Bell and P. Semukhin. Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs. In International Conference on Concurrency Theory, number 22 in CONCUR'20, pages 1-16, 2020. Google Scholar
  4. A. Bertoni, G. Mauri, and M. Torelli. Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata. In Automata, Languages and Programming, volume 52, pages 87-94, 1977. Google Scholar
  5. V. Blondel and V. Canterini. Undecidable problems for probabilistic automata of fixed dimension. Theory of Computing Systems, 36:231-245, 2003. Google Scholar
  6. V. D. Blondel and N. Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, pages 91-98, 2002. Google Scholar
  7. L. Daviaud, M. Jurdzinski, R. Lazic, F. Mazowiecki, G. A. Pérez, and J. Worrell. When is containment decidable for probabilistic automata? In International Colloquium on Automata, Languages, and Programming, number 121 in ICALP'18, pages 1-14, 2018. Google Scholar
  8. N. Fijalkow, C. Riveros, and J. Worrell. Probabilistic automata of bounded ambiguity. In 28th International Conference on Concurrency Theory (CONCUR), pages 19:1-19:14, 2017. Google Scholar
  9. S. Friedland. Matrices: Algebra, Analysis and Applications. World Scientific Publishing Company Pte Limited, 2015. URL: https://books.google.co.uk/books?id=y8fACwAAQBAJ.
  10. H. Gimbert and Y. Oualhadj. Probabilistic automata on finite words: decidable and undecidable problems. In International Colloquium on Automata, Languages and Programming (ICALP'10), volume 2, pages 527-538, 2010. Google Scholar
  11. V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. Skolem’s problem - on the border between decidability and undecidability. In TUCS Technical Report Number 683, 2005. Google Scholar
  12. M. Hirvensalo. Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages. SOFSEM 2007: Theory and Practice of Computer Science, Lecture Notes in Computer Science, 4362:309-319, 2007. Google Scholar
  13. R. A. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge University Press, 1991. Google Scholar
  14. O. Ibarra and B. Ravikumar. On sparseness, ambiguity and other decision problems for acceptors and transducers. In Proc. STACS 1986, volume 210, pages 171-179, 1986. Google Scholar
  15. S. C. Kleene. Representation of events in nerve nets and finite automata. Automata Studies, Annals of Mathematical Studies, 34, 1956. Google Scholar
  16. K. L. Manders and L. Adleman. NP-complete decision problems for binary quadratics. Journal of Computer and System Sciences, 16:168-184, 1978. Google Scholar
  17. J. Ouaknine and J. Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 366-379, SODA, 2014. Google Scholar
  18. A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971. Google Scholar
  19. M. O. Rabin. Probabilistic automata. Information and Control, 6:230-245, 1963. Google Scholar
  20. C. Reutenauer. Propertiétés arithmétiques et topologiques de séries rationnelles en variables non commutatives. Thèse troisième cycle, Université Paris VI, 1977. Google Scholar
  21. P. Turakainen. Generalized automata and stochastic languages. Proceedings of the American Mathematical Society, 21:303-309, 1969. Google Scholar
  22. N. K. Vereshchagin. The problem of appearance of a zero in a linear recurrence sequence (in russian). Mat. Zametki, 38(2), 1985. Google Scholar
  23. A. Weber and H. Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991. 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