Finitely constrained classes of homogeneous directed graphs
Journal of Symbolic Logic 59 (1):124-139 (1994)
| Abstract | 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesSanjay 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.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads5 ( #160,204 of 548,999 )Recent downloads (6 months)1 ( #63,327 of 548,999 )How can I increase my downloads? |
My notes
Discussion
