{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T09:06:56Z","timestamp":1751879216375},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7316,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a finite relational language <jats:italic>L<\/jats:italic> is there an algorithm that, given two finite sets <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200020284_inline1\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200020284_inline2\" \/> of structures in the language, determines how many homogeneous <jats:italic>L<\/jats:italic> structures there are omitting every structure in <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200020284_inline2\" \/> and embedding every structure in <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200020284_inline1\" \/>?<\/jats:p><jats:p>For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments \u0393, determines whether <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200020284_inline3\" \/><jats:sub>\u0393<\/jats:sub>, the class of finite tournaments omitting every tournament in \u0393. is well-quasi-order?<\/jats:p><jats:p>First, we give a nonconstructive proof of the existence of an algorithm for the case in which \u0393 consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere.<\/jats:p><jats:p>The case in which \u0393 consists of two tournaments is also discussed.<\/jats:p>","DOI":"10.2307\/2275255","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:51:08Z","timestamp":1146941468000},"page":"124-139","source":"Crossref","is-referenced-by-count":13,"title":["Finitely constrained classes of homogeneous directed graphs"],"prefix":"10.1017","volume":"59","author":[{"given":"Brenda J.","family":"Latka","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200020284_ref001","volume-title":"Combinatorics","author":"Bollob\u00e1s","year":"1986"},{"key":"S0022481200020284_ref009","first-page":"494","volume":"37","author":"Henson","year":"1972","journal-title":"Countable homogeneous relational systems and categorical theories"},{"key":"S0022481200020284_ref007","first-page":"3","volume-title":"Contemporary Mathematics","volume":"131","author":"Cherlin","year":"1992"},{"key":"S0022481200020284_ref002","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.410"},{"key":"S0022481200020284_ref003","unstructured":"Cherlin Gregory , Homogeneous directed graphs II, graphs embedding I\u221e , submitted."},{"key":"S0022481200020284_ref005","first-page":"67","volume-title":"Logic Colloquium 1985","author":"Cherlin","year":"1987"},{"key":"S0022481200020284_ref006","first-page":"231","article-title":"Homogeneous tournaments revisited","volume":"256","author":"Cherlin","year":"1988","journal-title":"Geometria Dedkatae"},{"key":"S0022481200020284_ref010","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"S0022481200020284_ref008","first-page":"361","article-title":"Sur l'extension aux relations de quelques properiet\u00e9s des ordres","volume":"71","author":"Fraiss\u00e9","year":"1954","journal-title":"Annates Scientifiques de l'\u00c9cole Normale Superi\u00e9ure"},{"key":"S0022481200020284_ref011","first-page":"210","article-title":"Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200020284_ref012","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0743728-1"},{"key":"S0022481200020284_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760647"},{"key":"S0022481200020284_ref014","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100003844"},{"key":"S0022481200020284_ref004","unstructured":"Cherlin Gregory , Homogeneous directed graphs II, graphs omitting I\u221e , submitted."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200020284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T15:16:18Z","timestamp":1557933378000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200020284\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["S0022481200020284"],"URL":"https:\/\/doi.org\/10.2307\/2275255","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}