سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

[ 42 | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]


عنوان مقاله:تجزیه و تحلیل کامل پیچیدگی پارامتر های برنامه ریزی محدود
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره):81 (7)
سال انتشار:November 2015
شماره صفحات: 131113321311-1332
نشانگر دیجیتالی شیء:[ 10.1016/j.jcss.2015.04.002 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Journal Of Computer And System Sciences »
  4. A complete parameterized complexity analysis of bounded planning

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 34.230.84.215

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

خلاصه مقاله، نویسندگان و کلمات کلیدی

A Complete Parameterized Complexity Analysis Of Bounded Planning


مقاله: تجزیه و تحلیل کامل پیچیدگی پارامتر های برنامه ریزی محدود

نويسند‌گان:


خلاصه مقاله:


The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter “length of the solution plan.” We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Bäckström and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not.


مشکل برنامه ریزی گزاره مشکل دشوار محاسباتی، که حتی تحت محدودیت های نحوی و ساختاری قوی سخت باقی مانده است. با توجه به سختی آن را طبیعی می شود به مطالعه برنامه ریزی در زمینه پیچیدگی پارامتر. در این مقاله ما کار بر روی پیچیدگی پارامتر های برنامه ریزی با توجه به پارامتر آغاز شده توسط داونی، همکاران و Stege ادامه "طول طرح راه حل است." ما با ارائه یک طبقه بندی کامل از پیچیدگی پارامتر از مشکل برنامه ریزی در دو از ترین محدودیت برجسته نحوی، به عنوان مثال، به اصطلاح محدودیت بارها معرفی شده توسط Bäckström و Nebel و محدودیت در تعداد پیش شرط و اثرات به عنوان Bylander معرفی شده است. ما همچنین مشخص است که از در نظر گرفته ثابت پارامتر مشکلات رام اعتراف یک هسته چند جمله ای و که نمی کنند.


كلمات كليدي:

Complexity of automated planning, Kernelization, Parameterized complexity
پیچیدگی برنامه ریزی خودکار, Kernelization, پیچیدگی پارامتر


موضوعات:

Computational Theory and Mathematics, Computer Networks and Communications, Applied Mathematics, Theoretical Computer Science



[ ]

فهرست مقالات مرتبط و مشابه

  1. Cesati, M., Wareham, H.T. (2017) 'Parameterized complexity analysis in robot motion planning', 1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, Institute of Electrical and Electronics Engineers (IEEE), pp:0-0
  2. Bäckström, Christer, Jonsson, Peter, Ordyniak, Sebastian, Szeider, Stefan (2013) 'Parameterized Complexity and Kernel Bounds for Hard Planning Problems', Lecture Notes in Computer Science, Springer Nature, pp:13-24
  3. Namjoshi, Kedar S. (2017) 'Symmetry and Completeness in the Analysis of Parameterized Systems', Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp:299-313
  4. Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T. (1995) 'Parameterized complexity analysis in computational biology', Bioinformatics, Oxford University Press (OUP), pp:49-57
  5. Mathieson, Luke (2010) 'The parameterized complexity of editing graphs for bounded degeneracy', Theoretical Computer Science, Elsevier BV, pp:3181-3187
  6. Dvořák, Pavel, Knop, Dušan (2018) 'Parameterized Complexity of Length-bounded Cuts and Multicuts', Algorithmica, Springer Nature, pp:-
  7. Chen, Y., Flum, J., Grohe, M. (2017) 'Bounded nondeterminism and alternation in parameterized complexity theory', 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., Institute of Electrical and Electronics Engineers (IEEE), pp:0-0
  8. Clarke, Edmund, Kroening, Daniel, Ouaknine, Joël, Strichman, Ofer (2004) 'Completeness and Complexity of Bounded Model Checking', Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp:85-96
  9. Elberfeld, Michael , Stockhusen, Christoph , Tantau, Till (2014) 'On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness', Algorithmica, Springer Science + Business Media, pp:661-701
  10. Witteveen, Jouke, Torenvliet, Leen (2016) 'Fixed-parameter decidability: Extending parameterized complexity analysis', Mathematical Logic Quarterly, Wiley-Blackwell, pp:596-607

 

برگشت به بالا
× 🎁
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×