Document Open Access Logo

Thin MSO with a Probabilistic Path Quantifier

Author Mikolaj Bojanczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.96.pdf
  • Filesize: 424 kB
  • 13 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk

Cite As Get BibTex

Mikolaj Bojanczyk. Thin MSO with a Probabilistic Path Quantifier. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 96:1-96:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.96

Abstract

This paper is about a variant of MSO on infinite trees where: 

- there is a quantifier "zero probability of choosing a path pi in 2^{omega} which makes omega(pi) true"; 

- the monadic quantifiers range over sets with countable topological closure.

We introduce an automaton model, and show that it captures the logic.

Subject Classification

Keywords
  • Automata
  • mso
  • infinite trees
  • probabilistic temporal logics

Metrics

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

References

  1. Christel Baier, Marcus Größer, and Nathalie Bertrand. Probabilistic ω-automata. J. ACM, 59(1):1, 2012. URL: http://dx.doi.org/10.1145/2108242.2108243.
  2. Vince Bárány, Łukasz Kaiser, and Alexander Rabinovich. Cardinality quantifiers in MLO over trees. In Proc. of CSL, 2009. Google Scholar
  3. Mikolaj Bojanczyk. U. ACM SIGLOG News, 2(4):2-15, 2015. Google Scholar
  4. Tomás; Brázdil, Vojtech Forejt, Jan Kretínský, and Antonín Kucera. The satisfiability problem for probabilistic CTL. In Proc. of LICS, pages 391-402, 2008. Google Scholar
  5. Julius R. Büchi. On a decision method in restricted second-order arithmetic. In Proc. 1960 Int. Congr. for Logic, Methodology and Philosophy of Science, pages 1-11, 1962. Google Scholar
  6. Arnaud Carayol, Axel Haddad, and Olivier Serre. Randomization in automata on infinite trees. ACM Trans. Comput. Log., 15(3):24:1-24:33, 2014. URL: http://dx.doi.org/10.1145/2629336.
  7. Thomas Colcombet. Regular cost functions, part I: logic and algebra over words. Logical Methods in Computer Science, 9(3), 2013. URL: http://dx.doi.org/10.2168/LMCS-9(3:3)2013.
  8. Daniel Lehmann and Saharon Shelah. Reasoning with time and chance. Information and Control, 53(3):165-1983, 1982. Google Scholar
  9. Henryk Michalewski and Matteo Mio. Baire category quantifier in monadic second order logic. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pages 362-374, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_29.
  10. Henryk Michalewski and Matteo Mio. Measure quantifier in monadic second order logic. In Logical Foundations of Computer Science - International Symposium, LFCS 2016, Deerfield Beach, FL, USA, January 4-7, 2016. Proceedings, pages 267-282, 2016. URL: http://dx.doi.org/10.1007/978-3-319-27683-0_19.
  11. Michael O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of American Mathematical Society, 141:1-35, 1969. Google Scholar
  12. Alexander Rabinovich. On decidability of monadic logic of order over the naturals extended by monadic predicates. Inf. Comput., 205(6):870-889, 2007. URL: http://dx.doi.org/10.1016/j.ic.2006.12.004.
  13. Sergiu Hart Micha Sharir. Probabilistic propositional temporal logics. Information and Control, 70(2-3):97-155, 1986. 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