Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, ON, Canada, July 22-25, 2013. Proceedings

این کتاب مجموعه مقالات داوری پانزدهمین کارگاه بین‌المللی پیچیدگی توصیفی سیستم‌های رسمی، DCFS 2013 است که در لندن، ON، کانادا، در ژوئیه 2013 برگزار شد. و از بین 46 مورد ارسالی انتخاب شد.
موضوعات تحت پوشش خودکار، دستور زبان، زبان و سایر سیستم های رسمی هستند. حالت های مختلف عملیات و اقدامات پیچیدگی؛ سیستم های همکاری؛ مختصر بودن توصیف اشیاء، پدیده های حالت انفجار مانند؛ پیچیدگی مدار توابع بولی و اقدامات مرتبط. پیچیدگی اندازه و پیچیدگی ساختاری سیستم های رسمی؛ مبادله بین مدل های محاسباتی و نحوه عملکرد. کاربردهای سیستم های رسمی؛ به عنوان مثال در تست نرم افزار و سخت افزار، در سیستم های گفتگو، در مدل سازی سیستم ها یا در مدل سازی زبان های طبیعی؛ و محدودیت های پیچیدگی آنها؛ اندازه یا پیچیدگی ساختاری سیستم‌های رسمی برای مدل‌سازی زبان‌های طبیعی؛ جنبه های پیچیدگی مربوط به ترکیبیات کلمات؛ پیچیدگی توصیفی در محیط های محدود به منابع یا ساختار. پیچیدگی ساختاری مرتبط با پیچیدگی توصیفی. مرزهای بین تصمیم پذیری و تصمیم ناپذیری؛ جهانی بودن و برگشت پذیری؛ معماری های با انگیزه طبیعت (الهام گرفته از زیستی) و مدل های غیر متعارف محاسبات. پیچیدگی کلموگروف-چایتین، اطلاعات الگوریتمی.

This book constitutes the refereed proceedings of the 15th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2013, held in London, ON, Canada, in July 2013. The 22 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 46 submissions.
The topics covered are automata, grammars, languages and other formal systems; various modes of operations and complexity measures; co-operating systems; succinctness of description of objects, state-explosion-like phenomena; circuit complexity of Boolean functions and related measures; size complexity and structural complexity of formal systems; trade-offs between computational models and mode of operation; applications of formal systems; for instance in software and hardware testing, in dialogue systems, in systems modeling or in modeling natural languages; and their complexity constraints; size or structural complexity of formal systems for modeling natural languages; complexity aspects related to the combinatorics of words; descriptional complexity in resource-bounded or structure-bounded environments; structural complexity as related to descriptional complexity; frontiers between decidability and undecidability; universality and reversibility; nature-motivated (bio-inspired) architectures and unconventional models of computing; Kolmogorov-Chaitin complexity, algorithmic information.