تجزیه ‌و تحلیل الگوریتم‌ های خطی ‌سازی ساختار‌های اشراف چندگانه: در جستجوی یک تعمیم نظری

ادغام موازی در ساخت همپایگی، منجر به اشتقاق ساختاری می‌شود که دربرگیرنده‌ رابطه‌ متقارن دوسویه است. در رابطه‌ متقارن مذکور، یک عنصر اشراف چندگانه می‌شود و در بین دو بند همپایه به اشتراک گذاشته‌ می‌شود. در این حالت، عنصر مشترک֯ دو گره مادر خواهد داشت و طبیعتاً خطی‌سازیِ ساختارهای مشتق از ادغام موازی که دارای اشراف چندگانه هستند با مشکل مواجه خواهد شد. هدف از این پژوهش واکاوی و کالبدشکافی الگوریتم‌هایی بود که تاکنون در ادبیات مربوطه جهت مرتفع‌شدن چالش خطی‌سازی ساختارهای اشراف چندگانه مطرح گردیده‌اند. به‌طور‌مشخص، در این پژوهش محتوای الگوریتم‌های ارائه‌شده در خصوص خطی‌سازی ساختار اشراف چندگانه به‌صورت کیفی و با بهره‌گیری از ابزارهای گراف و (نظریه) مجموعه تحلیل شد. رویکردهای تجربی و محاسباتی کمّی موجود در رابطه با موجودیت این نوع از ساختار نشان داد که ساختار اشراف چندگانه پیش از اینکه مشخصاً محصول ادغام موازی باشد، برایند طبیعی عملکرد ادغام در فضای کاری است. در ادامۀ تحلیل، جهت پرتوافکنی بر عملکرد و ماهیت ادغام در فضای کاری، مبحث ترتیب‌گذاری بر ادغام مجموعه‌ای مطرح شد تا از این منظر بخشی از خطی‌سازی، در نحو محض رقم بخورد.

analyzing the linearization algorithms of multidominant structures: in search of a theoretical generalization

parallel merge generates a structure that contains a double symmetric relation, in which the shared object has two mother nodes. naturally, the linearization of multidominant structures derived from parallel merge will face challenges. the purpose of this study was to analyze and dissect the algorithms that have been proposed in the relevant literature to address the challenge of the linearization of multidominant structures. specifically, in this research, the content of the proposed algorithms regarding linearization of multidominant structure was qualitatively examined using graph and set notations. the empirical and computational quantitative approaches, in relation to the existence of this type of structure, showed that multidominant structure was the natural result of the function of merge in the workspace rather than the consequences of parallel merge. to shed light on the performance of merge in the workspace, putting order into set merge was raised. hence, part of the linearization took place in narrow syntax.