Personal tools
You are here: Home Events LFCS seminar by Dr. Utz-Uwe Haus (ETH)

LFCS seminar by Dr. Utz-Uwe Haus (ETH)

— filed under:

Monotone Boolean Functions in Systems Biology

What
  • Upcoming events
When Apr 30, 2014
from 11:00 AM to 12:00 PM
Where IF 2.33
Contact Name Ilias Diakonikolas
Add event to calendar vCal
iCal

We propose a forcing-based interpretation of monadic second-order
logic (MSO) on infinite (omega) words in Weak MSO (WMSO). The
interpretation is purely syntactic.

We show that a formula with parameters is true in MSO if and only
if its interpretation is true in WMSO. We also show that a closed
formula is true in MSO if and only if its interpretation is provable
under some axioms which hold for WMSO, but without axiomatizing it.

We use model-theoretic arguments. Our approach is inspired from
point-free topology: infinite words, seen as topological points,
are approximated by filters of bounded segments. We devise forcing
conditions such that the corresponding generic filters approximate
Ramseyan factorizations of infinite words modulo satisfaction of
formulas of a given quantifier depth.

Our interpretation parallels some approaches to McNaughton's
Theorem (equivalence between non-deterministic B├╝chi automata and
deterministic Rabin automata) but the obtained formulas do not
describe deterministic automata.

Document Actions