On the Ramseyan factorization theorem

Shota Murakami; Takeshi Yamazaki; Keita Yokoyama

doi:10.1007/978-3-319-08019-2_33

On the Ramseyan factorization theorem

Shota Murakami, Takeshi Yamazaki, Keita Yokoyama

SCI - Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

Abstract

We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (RF_k^s), a Ramsey-type theorem used in automata theory. We prove that RF_k^s is equivalent to RT₂² for all s,k ≥ 2, k ∈ ω over RCA ₀. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.

Original language	English
Title of host publication	Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings
Publisher	Springer Verlag
Pages	324-332
Number of pages	9
ISBN (Print)	9783319080185
DOIs	https://doi.org/10.1007/978-3-319-08019-2_33
Publication status	Published - 2014
Event	10th Conference on Computability in Europe, CiE 2014 - Budapest, Hungary Duration: 2014 Jun 23 → 2014 Jun 27

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8493 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Conference on Computability in Europe, CiE 2014
Country/Territory	Hungary
City	Budapest
Period	14/6/23 → 14/6/27

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-08019-2_33

Cite this

Murakami, S., Yamazaki, T., & Yokoyama, K. (2014). On the Ramseyan factorization theorem. In Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings (pp. 324-332). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8493 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08019-2_33

On the Ramseyan factorization theorem. / Murakami, Shota; Yamazaki, Takeshi ; Yokoyama, Keita.

Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings. Springer Verlag, 2014. p. 324-332 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8493 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Murakami, S, Yamazaki, T & Yokoyama, K 2014, On the Ramseyan factorization theorem. in Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8493 LNCS, Springer Verlag, pp. 324-332, 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, 14/6/23. https://doi.org/10.1007/978-3-319-08019-2_33

Murakami S, Yamazaki T , Yokoyama K. On the Ramseyan factorization theorem. In Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings. Springer Verlag. 2014. p. 324-332. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08019-2_33

@inproceedings{9bd84b34ddf743bfb002c4c53759a7c8,

title = "On the Ramseyan factorization theorem",

abstract = "We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (RFks), a Ramsey-type theorem used in automata theory. We prove that RFks is equivalent to RT22 for all s,k ≥ 2, k ∈ ω over RCA 0. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.",

author = "Shota Murakami and Takeshi Yamazaki and Keita Yokoyama",

year = "2014",

doi = "10.1007/978-3-319-08019-2_33",

language = "English",

isbn = "9783319080185",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "324--332",

booktitle = "Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings",

note = "10th Conference on Computability in Europe, CiE 2014 ; Conference date: 23-06-2014 Through 27-06-2014",

}

TY - GEN

T1 - On the Ramseyan factorization theorem

AU - Murakami, Shota

AU - Yamazaki, Takeshi

AU - Yokoyama, Keita

PY - 2014

Y1 - 2014

N2 - We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (RFks), a Ramsey-type theorem used in automata theory. We prove that RFks is equivalent to RT22 for all s,k ≥ 2, k ∈ ω over RCA 0. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.

AB - We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (RFks), a Ramsey-type theorem used in automata theory. We prove that RFks is equivalent to RT22 for all s,k ≥ 2, k ∈ ω over RCA 0. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.

UR - http://www.scopus.com/inward/record.url?scp=84903594978&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903594978&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08019-2_33

DO - 10.1007/978-3-319-08019-2_33

M3 - Conference contribution

AN - SCOPUS:84903594978

SN - 9783319080185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 324

EP - 332

BT - Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Proceedings

PB - Springer Verlag

T2 - 10th Conference on Computability in Europe, CiE 2014

Y2 - 23 June 2014 through 27 June 2014

ER -

On the Ramseyan factorization theorem

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this