کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949727 1440204 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
New transience bounds for max-plus linear systems
ترجمه فارسی عنوان
محدوده های جدید ترافیکی برای سیستم های خطی حداکثر
ترجمه چکیده
سیستم های حداکثر به صورت خطی رفتار انواع مختلفی از سیستم های پیچیده را توصیف می کنند. شناخته شده است که این سیستم ها پس از یک مرحله گذار اولیه، رفتار دوره ای را نشان می دهند. ارزیابی طول این فاز گذرا اطلاعات مهمی را در مورد اندازه گیری پیچیدگی های این سیستم ها فراهم می کند و در طراحی سیستم نیز بسیار مهم است. ما پارامترهای مربوطه را در یک نمایشگر گرافیکی این سیستم ها شناسایی می کنیم و پیشنهاد می کنیم یک استراتژی مدولار برای بدست آوردن مرزهای بالایی جدید در طول فاز گذرا ایجاد کنیم. با این کار، ما اولین کسانی هستیم که محدودیتهای تداوم و بالقوه تسریع زیرمجموعه را ارائه می دهد. ما از محدودیت های ما برای استخراج نتایج پیچیده جدید، به ویژه در محاسبات توزیع استفاده می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Linear max-plus systems describe the behavior of a large variety of complex systems. It is known that these systems show a periodic behavior after an initial transient phase. Assessment of the length of this transient phase provides important information on complexity measures of such systems, and so is crucial in system design. We identify relevant parameters in a graph representation of these systems and propose a modular strategy to derive new upper bounds on the length of the transient phase. By that we are the first to give asymptotically tight and potentially subquadratic transience bounds. We use our bounds to derive new complexity results, in particular in distributed computing.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 83-99
نویسندگان
, , ,