|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4661582||1344845||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