2014 | OriginalPaper | Buchkapitel
On the Ramseyan Factorization Theorem
verfasst von : Shota Murakami, Takeshi Yamazaki, Keita Yokoyama
Erschienen in: Language, Life, Limits
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (
${\rm RF}^{s}_{k}$
), a Ramsey-type theorem used in automata theory. We prove that
${\rm RF}^s_k$
is equivalent to
${\rm RT}^2_2$
for all
s
,
k
≥ 2,
k
∈
ω
over
RCAo
. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.