{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T23:11:05Z","timestamp":1684537865585},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5217,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1994,6]]},"abstract":"<jats:p>Long regressive sequences in well-quasi-ordered sets contain ascendingsubsequences of length<jats:italic>n<\/jats:italic>. The complexity of the corresponding function<jats:italic>H<\/jats:italic>(<jats:italic>n<\/jats:italic>) is studied in the Grzegorczyk-Wainer hierarchy. An extension to regressive canonical colourings is indicated.<\/jats:p>","DOI":"10.1017\/s0963548300001103","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:17:11Z","timestamp":1221218231000},"page":"177-190","source":"Crossref","is-referenced-by-count":0,"title":["A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies"],"prefix":"10.1017","volume":"3","author":[{"given":"Walter A.","family":"Deuber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Thumser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300001103_ref018","unstructured":"[18] Leeb K. Personal communications."},{"key":"S0963548300001103_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90063-5"},{"key":"S0963548300001103_ref027","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0963548300001103_ref013","first-page":"851","article-title":"Analyse combinatoire \u2013 Sur un th\u00e9or\u00e8me d'extension dans la th\u00e9orie des mots","volume":"266","author":"Jullien","year":"1968","journal-title":"C.R. Acad. Sci. Paris"},{"key":"S0963548300001103_ref031","doi-asserted-by":"publisher","DOI":"10.2307\/2272973"},{"key":"S0963548300001103_ref008","volume-title":"Rozprawy matematiczne","volume":"4","author":"Grzegorczyk","year":"1933"},{"key":"S0963548300001103_ref028","doi-asserted-by":"crossref","unstructured":"[28] Simpson S. G. (1987) Unprovable theorems and fast growing functions. In: Simpson S. G. (ed.) Logic and Combinatorics. Contemporary Mathematics 65, 359\u2013394.","DOI":"10.1090\/conm\/065\/891258"},{"key":"S0963548300001103_ref030","unstructured":"[30] Thumser W. (1992) On the well-order type of certain combinatorial structures, Bielefeld (manuscript, submitted)."},{"key":"S0963548300001103_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90040-6"},{"key":"S0963548300001103_ref009","volume-title":"Ramsey theory","author":"Graham","year":"1990"},{"key":"S0963548300001103_ref010","doi-asserted-by":"crossref","first-page":"45","DOI":"10.5486\/PMD.1967.14.1-4.06","article-title":"Eine kombinatorische Frage zahlentheoretischer Art","volume":"14","author":"Harzheim","year":"1967","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"S0963548300001103_ref017","unstructured":"[17] Leeb K. (1973) Vorlesungen \u00fcber Pascaltheorie. Arbeitsbericht des Instituts f\u00fcr mathematische Maschinen und Datenverarbeitung, Friedrich Alexander Universit\u00e4t Erlangen N\u00fcrnberg, Bd. 6 Nr. 7."},{"key":"S0963548300001103_ref004","first-page":"464","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s","year":"1935","journal-title":"Composito Math."},{"key":"S0963548300001103_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565428"},{"key":"S0963548300001103_ref001","volume-title":"Studies in Logic and the Foundations of Mathematics","volume":"106","author":"Erd\u0151os","year":"1984"},{"key":"S0963548300001103_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90074-1"},{"key":"S0963548300001103_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90346-4"},{"key":"S0963548300001103_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71130-3"},{"key":"S0963548300001103_ref019","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511666216.006"},{"key":"S0963548300001103_ref023","volume-title":"Forschungsinstitut fur Diskrete Mathematik","author":"Pr\u00f6mel","year":"1989"},{"key":"S0963548300001103_ref006","volume-title":"Vorlesungen \u00fcber Invariantentheorie, Hrsg. v. Geo. Kerschensteiner. 1. Bd. Determinanten (XI, 201S.)","author":"Gordan's","year":"1885"},{"key":"S0963548300001103_ref015","doi-asserted-by":"publisher","DOI":"10.2307\/2267457"},{"key":"S0963548300001103_ref026","volume-title":"Aspects of Ramsey Theory","author":"Pr\u00f6mel","year":"1993"},{"key":"S0963548300001103_ref003","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-25.4.249"},{"key":"S0963548300001103_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090170"},{"key":"S0963548300001103_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72905-8"},{"key":"S0963548300001103_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90120-0"},{"key":"S0963548300001103_ref012","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"S0963548300001103_ref029","volume-title":"Sonderforschungsbereich 343 \u201cDiskrete Strukturen in der Mathematik\u201d","author":"Thumser","year":"1989"},{"key":"S0963548300001103_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"S0963548300001103_ref025","volume-title":"Forschungsinstitut fur Diskrete Mathematik","author":"Pr\u00f6mel","year":"1989"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300001103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T22:55:44Z","timestamp":1684536944000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300001103\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["S0963548300001103"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300001103","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}