You are not logged in |
joint work with Mikołaj Bojańczyk and Michał Skrzypczak
- Speaker(s)
- Edon Kelmendi
- Affiliation
- Uniwersytet Warszawski
- Date
- Oct. 3, 2018, 2:15 p.m.
- Room
- room 5050
- Title in Polish
- MSO+∇ is undecidable
- Seminar
- Seminar Automata Theory
We consider an extension of monadic second order logic on the infinite binary tree with a probabilistic path quantifier called ∇.
Intuitively this quantifier means "the set of branches that satisfy a formula has probability 1".
The probability measure that we use is the coin-tossing measure,
i.e. we generate a random branch by starting at the root, tossing a coin and proceeding to the left or right child according to the result of the coin toss, and so on.
By adding this quantifier we get a logic that properly extends MSO.
There is a weak variant that is decidable but the full logic is not.
In this talk we will sketch the undecidability proof.
There is a weak variant that is decidable but the full logic is not.
In this talk we will sketch the undecidability proof.
This is joint work with Mikołaj Bojańczyk and Michał Skrzypczak.
