Document Open Access Logo

Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs

Authors Paul C. Bell , Pavel Semukhin

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.22.pdf
  • Filesize: 0.52 MB
  • 16 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

Acknowledgements

We thank the referees for their careful reading of this manuscript and helpful comments.

Cite AsGet BibTex

Paul C. Bell and Pavel Semukhin. Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CONCUR.2020.22

Abstract

We show the surprising result that the cutpoint isolation problem is decidable for probabilistic finite automata where input words are taken from a letter-bounded context-free language. A context-free language ℒ is letter-bounded when ℒ ⊆ a₁^* a₂^* ⋯ a_𝓁^* for some finite 𝓁 > 0 where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related 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
  • cutpoint isolation problem
  • letter-bounded context-free languages

Metrics

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

Related Versions

References

  1. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, second edition, 2006. Google Scholar
  2. P. C. Bell, S. Chen, and L. M. Jackson. Freeness properties of weighted and probabilistic automata over bounded languages. Information and Computation, 269, 2019. Google Scholar
  3. P. C. Bell, V. Halava, and M. Hirvensalo. Decision problems for probabilistic finite automata on bounded languages. Fundamenta Informaticae, 123(1):1-14, 2012. Google Scholar
  4. Paul C. Bell. Polynomially ambiguous probabilistic automata on restricted languages. In International Colloquium on Automata, Languages, and Programming (ICALP'19), volume 132 of LIPIcs, pages 105:1-105:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.105.
  5. 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
  6. V. Blondel and V. Canterini. Undecidable problems for probabilistic automata of fixed dimension. Theory of Computing Systems, 36:231-245, 2003. Google Scholar
  7. Jin-yi Cai. Computing Jordan normal forms exactly for commuting matrices in polynomial time. Int. J. Found. Comput. Sci., 5(3/4):293-302, 1994. URL: https://doi.org/10.1142/S0129054194000165.
  8. Henri Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993. URL: https://doi.org/10.1007/978-3-662-02945-9.
  9. 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 (ICALP'18), volume 107 of LIPIcs, pages 121:1-121:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.121.
  10. 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
  11. S. Friedland. Matrices: Algebra, Analysis and Applications. World Scientific Publishing Company Pte Limited, 2015. URL: https://books.google.co.uk/books?id=y8fACwAAQBAJ.
  12. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. New York, NY, USA, 1979. Google Scholar
  13. 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
  14. S. Ginsburg. The Mathematical Theory of Context Free Languages. McGraw-Hill, 1966. Google Scholar
  15. Seymour Ginsburg and Edwin Spanier. Semigroups, Presburger formulas, and languages. Pacific journal of Mathematics, 16(2):285-296, 1966. Google Scholar
  16. O. Goldreich. On promise problems: a survey. In Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254-290. Springer-Verlag, 2006. Google Scholar
  17. 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
  18. 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
  19. M. Mignotte. Some useful bounds. In Computer algebra, pages 259-263. Springer, Vienna, 1983. Google Scholar
  20. V. Y. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12):97-138, 1996. URL: https://doi.org/10.1016/0898-1221(96)00080-6.
  21. R. J. Parikh. On context-free languages. Journal of the ACM (JACM), 13(4):570-581, 1966. Google Scholar
  22. A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971. Google Scholar
  23. M. O. Rabin. Probabilistic automata. Information and Control, 6:230-245, 1963. Google Scholar
  24. J. C. Rosales and P. A. García-Sánchez. Numerical semigroups, volume 20 of Developments in Mathematics. Springer, New York, 2009. URL: https://doi.org/10.1007/978-1-4419-0160-6.
  25. P. Turakainen. Generalized automata and stochastic languages. Proceedings of the American Mathematical Society, 21:303-309, 1969. Google Scholar
  26. 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 Imprint Privacy Contact