کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661582 1633436 2016 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry
ترجمه فارسی عنوان
درباره (یکنواختی) تجزیه سلسله مراتبی ساختارهای محدود و هندسه مدل نظری
کلمات کلیدی
نظریه گلگون؛ ساختارهای محدود؛ کلاس Fraisse؛ هماهنگ سازی؛ تجزیه سلسله مراتبی؛ متا قضایای الگوریتمی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 11, November 2016, Pages 1093–1122
نویسندگان
,