کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4661582 1344845 2016 30 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry
ترجمه فارسی عنوان
درباره (یکنواختی) تجزیه سلسله مراتبی ساختارهای محدود و هندسه مدل نظری
کلمات کلیدی
نظریه گلگون؛ ساختارهای محدود؛ کلاس Fraisse؛ هماهنگ سازی؛ تجزیه سلسله مراتبی؛ متا قضایای الگوریتمی
03C45; 03C13; 03D15; 03B70Rosy theories; Finite structures; Fraisse classes; Coordinatization; Hierarchical decomposition; Algorithmic meta-theorems
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

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
نویسندگان
,