کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661582 | 1633436 | 2016 | 30 صفحه PDF | دانلود رایگان |
Using finite directed systems defined from “primitive” extension and amalgamation operations, we define an abstract notion of hierarchical decomposition that applies to a large family of classes of finite structures (tame classes). We prove that for any such class C that is uniformly hierarchical – in the sense that cofinally-many members of C have decompositions according to a functorial “program” – the theory TCTC of the generic structure is rosy. Conversely, we also show that for any tame class C, if TCTC is rosy, then C is uniformly hierarchical. Thus, the project of stratifying the complexity of computationally hard problems through parametrizing “width” notions – an important current in Finite Model Theory and Descriptive Complexity Theory – has a second face in Geometric Model Theory.
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 11, November 2016, Pages 1093–1122