Constructive Analysis of S1S and Büchi Automata
share
We study S1S and Büchi automata in the constructive type theory of the Coq proof assistant. For UP semantics (ultimately periodic sequences), we verify Büchi's translation of formulas to automata and thereby establish decidability of S1S constructively. For AS semantics (all sequences), we verify Büchi's translation assuming that sequences over finite semigroups have Ramseyan factorisations (RF). Assuming RF, UP semantics and AS semantics agree. RF is a consequence of Ramsey's theorem and implies the infinite pigeonhole principle, which is known to be unprovable constructively. We show that each of the following properties holds for UP semantics but is equivalent to RF for AS semantics: excluded middle of formula satisfaction, excluded middle of automaton acceptance, and existence of complement automata.
READ FULL TEXT