# Constructive Analysis of S1S and Büchi Automata

## Moritz Lichter and Gert Smolka

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.

We provide a Coq development formalising all results (version from 19th Apr 18) and the full version of the paper. The full paper is hyperlinked with the Coq development for browsing.

The Coq sources were compiled using Coq 8.7.2 (March 2018).