کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875511 1441962 2018 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Polynomial-time algorithms for computing distances of fuzzy transition systems
ترجمه فارسی عنوان
الگوریتم زمان چندجملهای برای محاسبه فاصله سیستم های انتقال فازی
کلمات کلیدی
سیستم های انتقال فازی اتوماتای ​​فازی، شبه اولترامتریک، الگوریتم،
ترجمه چکیده
فاصله های رفتاری برای اندازه گیری شباهت دو حالت در یک سیستم انتقالی فازی (غیر انتهایی) در ادبیات اخیرا پیشنهاد شده است. چنین فاصله ای که به صورت شبه مؤثر در فضای حالت مدل تعریف می شود، یک آنالوگ کمی از تقریبا یکنواخت را فراهم می کند. در این مقاله، ما بر روی مساله محاسبه این فاصله ها تمرکز می کنیم. ما برای اولین بار تعریف شبه اولترامتریک را با معرفی تخفیف به طوری که فاکتور تخفیف برابر با 1 قطعه اصلی تعریف را گسترش می دهد. سپس الگوریتم های چندجملهای را برای محاسبه فاصله های رفتاری در هر دو حالت غیر تخفیف و تخفیف ارائه می دهیم. الگوریتم است که به شدت چندجملهای در مورد اول است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم زمان چندجملهای برای محاسبه فاصله سیستم های انتقال فازی
چکیده انگلیسی
Behaviour distances to measure the resemblance of two states in a (nondeterministic) fuzzy transition system have been proposed recently in literature. Such a distance, defined as a pseudo-ultrametric over the state space of the model, provides a quantitative analogue of bisimilarity. In this paper, we focus on the problem of computing these distances. We first extend the definition of the pseudo-ultrametric by introducing discount such that the discounting factor being equal to 1 captures the original definition. We then provide polynomial-time algorithms to calculate the behavioural distances, in both the non-discounted and the discounted setting. The algorithm is strongly polynomial in the former case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 727, 30 May 2018, Pages 24-36
نویسندگان
, , ,