David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 59 (1):124-139 (1994)
Given a finite relational language L is there an algorithm that, given two finite sets A and B of structures in the language, determines how many homogeneous L structures there are omitting every structure in B and embedding every structure in A? For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether QΓ, the class of finite tournaments omitting every tournament in Γ, is well-quasi-order? First, we give a nonconstructive proof of the existence of an algorithm for the case in which Γ 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. The case in which Γ consists of two tournaments is also discussed
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Sanjay Jain & Arun Sharma (1997). The Structure of Intrinsic Complexity of Learning. Journal of Symbolic Logic 62 (4):1187-1201.
Thomas C. Brown (1979). Canonical Simplification of Finite Objects, Well Quasi-Ordered by Tree Embedding. Dept. Of Computer Science, University of Illinois at Urbana-Champaign.
H. Andréka, I. Hodkinson & I. Németi (1999). Finite Algebras of Relations Are Representable on Finite Sets. Journal of Symbolic Logic 64 (1):243-267.
Peter Turney (1989). The Architecture of Complexity: A New Blueprint. Synthese 79 (3):515 - 542.
Ross Willard (2000). A Finite Basis Theorem for Residually Finite, Congruence Meet-Semidistributive Varieties. Journal of Symbolic Logic 65 (1):187-200.
Tamara Lakins Hummel (1994). Effective Versions of Ramsey's Theorem: Avoiding the Cone Above 0'. Journal of Symbolic Logic 59 (4):1301-1325.
Gregory Cherlin & Niandong Shi (2001). Forbidden Subgraphs and Forbidden Substructures. Journal of Symbolic Logic 66 (3):1342-1352.
Stanley Burris (1984). Model Companions for Finitely Generated Universal Horn Classes. Journal of Symbolic Logic 49 (1):68-74.
J. C. E. Dekker (1981). Twilight Graphs. Journal of Symbolic Logic 46 (3):539-571.
Miklos Ajtai & Ronald Fagin (1990). Reachability is Harder for Directed Than for Undirected Finite Graphs. Journal of Symbolic Logic 55 (1):113-150.
Added to index2009-01-28
Total downloads5 ( #178,823 of 1,089,155 )
Recent downloads (6 months)1 ( #69,735 of 1,089,155 )
How can I increase my downloads?