• DocumentCode
    626311
  • Title

    Forcing MSO on Infinite Words in Weak MSO

  • Author

    Riba, Colin

  • Author_Institution
    LIP, Univ. de Lyon, Lyon, France
  • fYear
    2013
  • fDate
    25-28 June 2013
  • Firstpage
    448
  • Lastpage
    457
  • Abstract
    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.
  • Keywords
    approximation theory; deterministic automata; formal languages; topology; McNaughton theorem; Ramseyan factorization; WMSO; axiom; bounded segment; deterministic Rabin automata; equivalence; forcing MSO; forcing condition; forcing-based interpretation; generic filter approximation; infinite omega word; infinite words modulo satisfaction; model-theoretic argument; monadic second-order logic; nondeterministic Buchi automata; point-free topology; quantifier depth; syntactic interpretation; topological point; weak MSO; Additives; Approximation methods; Automata; Merging; Standards; Topology;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science (LICS), 2013 28th Annual IEEE/ACM Symposium on
  • Conference_Location
    New Orleans, LA
  • ISSN
    1043-6871
  • Print_ISBN
    978-1-4799-0413-6
  • Type

    conf

  • DOI
    10.1109/LICS.2013.51
  • Filename
    6571577