S2S (mathematics)

In mathematics, S2S is the monadic second order theory with two successors. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969.[1]

  1. ^ Rabin, Michael (1969). "Decidability of second-order theories and automata on infinite trees" (PDF). Transactions of the American Mathematical Society. 141.