@inbook{Michalewski2016,
    Abstract = {We study the extension of Monadic Second Order logic with the ``for almost all'' quantifier {\$}{\$}{\backslash}forall ^{\{}=1{\}}{\$}{\$} whose meaning is, informally, that {\$}{\$}{\backslash}forall ^{\{}=1{\}}X.{\backslash}phi (X){\$}{\$} holds if {\$}{\$}{\backslash}phi (X){\$}{\$} holds almost surely for a randomly chosen X. We prove that the theory of {\$}{\$}{\backslash}mathrm {\{}MSO{\}}+{\backslash}forall ^{\{}=1{\}}{\$}{\$} is undecidable both when interpreted on {\$}{\$}({\backslash}omega ,<){\$}{\$} and the full binary tree. We then identify a fragment of {\$}{\$}{\backslash}mathrm {\{}MSO{\}}+{\backslash}forall ^{\{}=1{\}}{\$}{\$} , denoted by {\$}{\$}{\backslash}mathrm {\{}MSO{\}}+{\backslash}forall ^{\{}=1{\}}{\\_}{\backslash}pi {\$}{\$} , and reduce some interesting problems in computer science and mathematical logic to the decision problem of {\$}{\$}{\backslash}mathrm {\{}MSO{\}}+ {\backslash}forall ^{\{}=1{\}}{\\_}{\backslash}pi {\$}{\$} . The question of whether {\$}{\$}{\backslash}mathrm {\{}MSO{\}}+{\backslash}forall ^{\{}=1{\}}{\\_}{\backslash}pi {\$}{\$} is decidable is left open.},
    Address = {Cham},
    Author = {Michalewski, Henryk and Mio, Matteo},
    BookTitle = {Logical Foundations of Computer Science: International Symposium, LFCS 2016, Deerfield Beach, FL, USA, January 4-7, 2016. Proceedings},
    Editor = {Artemov, Sergei and Nerode, Anil},
    ISBN = {978-3-319-27683-0},
    Pages = {267--282},
    Publisher = {Springer International Publishing},
    Title = {Measure Quantifier in Monadic Second Order Logic},
    URL = {https://doi.org/10.1007/978-3-319-27683-0\_19},
    Year = {2016},
    bdsk-url-1 = {https://doi.org/10.1007/978-3-319-27683-0\_19},
    bdsk-url-2 = {http://dx.doi.org/10.1007/978-3-319-27683-0\_19},
    date-added = {2017-07-29 09:34:16 +0000},
    date-modified = {2017-07-29 09:34:16 +0000},
    doi = {10.1007/978-3-319-27683-0_19}
}

@inbook{Michalewski2016, Abstract = {We study the extension of Monadic Second Order logic with the ``for almost all'' quantifier {\$}{\$}{\backslash}forall ^{{}=1{}}{\$}{\$} whose meaning is, informally, that {\$}{\$}{\backslash}forall ^{{}=1{}}X.{\backslash}phi (X){\$}{\$} holds if {\$}{\$}{\backslash}phi (X){\$}{\$} holds almost surely for a randomly chosen X. We prove that the theory of {\$}{\$}{\backslash}mathrm {{}MSO{}}+{\backslash}forall ^{{}=1{}}{\$}{\$} is undecidable both when interpreted on {\$}{\$}({\backslash}omega ,<){\$}{\$} and the full binary tree. We then identify a fragment of {\$}{\$}{\backslash}mathrm {{}MSO{}}+{\backslash}forall ^{{}=1{}}{\$}{\$} , denoted by {\$}{\$}{\backslash}mathrm {{}MSO{}}+{\backslash}forall ^{{}=1{}}{\}{\backslash}pi {\$}{\$} , and reduce some interesting problems in computer science and mathematical logic to the decision problem of {\$}{\$}{\backslash}mathrm {{}MSO{}}+ {\backslash}forall ^{{}=1{}}{\}{\backslash}pi {\$}{\$} . The question of whether {\$}{\$}{\backslash}mathrm {{}MSO{}}+{\backslash}forall ^{{}=1{}}{\_}{\backslash}pi {\$}{\$} is decidable is left open.}, Address = {Cham}, Author = {Michalewski, Henryk and Mio, Matteo}, BookTitle = {Logical Foundations of Computer Science: International Symposium, LFCS 2016, Deerfield Beach, FL, USA, January 4-7, 2016. Proceedings}, Editor = {Artemov, Sergei and Nerode, Anil}, ISBN = {978-3-319-27683-0}, Pages = {267--282}, Publisher = {Springer International Publishing}, Title = {Measure Quantifier in Monadic Second Order Logic}, URL = {https://doi.org/10.1007/978-3-319-27683-0_19}, Year = {2016}, bdsk-url-1 = {https://doi.org/10.1007/978-3-319-27683-0_19}, bdsk-url-2 = {http://dx.doi.org/10.1007/978-3-319-27683-0_19}, date-added = {2017-07-29 09:34:16 +0000}, date-modified = {2017-07-29 09:34:16 +0000}, doi = {10.1007/978-3-319-27683-0_19} }