کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873858 1440708 2018 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Checking dynamic consistency of conditional hyper temporal networks via mean payoff games
ترجمه فارسی عنوان
بررسی یکپارچگی پویا از شبکه های غیرمستقیم شرطی از طریق بازی های متوسط ​​بازپرداخت
کلمات کلیدی
شبکه های موقت مشروط، سازگاری پویا، بازی های متوسط ​​بازپرداخت شبکه های زمانبندی ساده شبکه های طولانی مدت زمان انفرادی زمان پاسخ،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Conditional Simple Temporal Network (CSTN ) is a constraint-based graph formalism for conditional temporal planning, which may be viewed as an extension of Simple Temporal Networks. Recently, STN s have been generalized into Hyper Temporal Networks (HyTN s), by considering weighted directed hypergraphs where each hyperarc models a disjunctive temporal constraint. We introduce the Conditional Hyper Temporal Network (CHyTN) model, a natural extension and generalization of both CSTN s and HyTN s, obtained by blending them together. We show that deciding whether a given CSTN is dynamically-consistent is coNP-hard, and that deciding whether a given CHyTN is dynamically-consistent is PSPACE-hard. Next, we offer the first deterministic (pseudo) singly-exponential time algorithm for checking DC in CHyTNs and CSTN s. To analyze the computational complexity of the proposed algorithm, we introduce a refined notion of DC, named ϵ-DC, presenting a sharp lower bounding analysis on the critical value of the reaction time where a conditional temporal network transits from being, to not being, dynamically-consistent.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 3, April 2018, Pages 348-374
نویسندگان
, ,