Logic and Automata. History and Perspectives

دسته بندی: الگوریتم ها و ساختارهای داده
ویرایش:  
نویسندگان: Flum J.,  Grӓdel E.,  Wilke T. (eds.)  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 737 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 52 مگابایت 

قیمت کتاب (تومان) : 31,000

Издательство Amsterdam University Press, 2008, -737 pp. منطق ریاضی و نظریه خودکار دو رشته علمی با رابطه نزدیک هستند که نه تنها برای بسیاری از نتایج نظری اساسی است، بلکه همچنین اساس یک روش منسجم برای تأیید و ترکیب سیستم های محاسباتی را تشکیل می دهد. اگرچه هم نظریه اتوماتا و هم منطق ریاضی به تاریخ بسیار طولانی‌تری نگاه می‌کنند، اما در دهه 1960 از طریق کارهای بنیادی بوچی، الگوت، رابین و دیگران که معادل بیانی خودکارها را با سیستم‌های منطقی مانند مرتبه دوم مونادیک نشان دادند، گرد هم آمدند. منطق روی کلمات و درختان متناهی و نامتناهی. این امر امکان رسیدگی به مشخصات (جایی که ویژگی‌های سیستم جهانی بیان می‌شود) و پیاده‌سازی‌ها (که شامل تعریف گام‌های محلی به منظور برآورده کردن اهداف کلی تعیین‌شده در مشخصات است) در یک چارچوب واحد را می‌دهد. علاوه بر این، این چارچوب رویه‌های الگوریتمی را برای سؤالات اساسی مانند سازگاری مشخصات یا صحت پیاده‌سازی ارائه می‌دهد. از طریق روش بررسی مدل، ارتباط بین تئوری اتوماتا و منطق در واقع مبنای روش های تأیید کارآمد با کاربردهای مقیاس صنعتی شده است.
ولفگانگ توماس یکی از دانشمندان پیشرو در منطق و نظریه خودکار است. او این حوزه علمی را نه تنها از طریق بسیاری از نتایج عمیق و زیبا، بلکه از طریق توانایی خود در کنار هم قرار دادن رشته های مختلف تحقیقاتی، ارائه ترکیبی قانع کننده از آنها و اشاره به جهت های جدید و امیدوارکننده شکل داده است. برای یک نسل کامل از دانشمندان در این زمینه، از جمله اکثر همکاران این جلد، آموزش‌ها و بررسی‌های او در مورد تئوری خودکار، نظریه و منطق زبان، فعالیت‌های او به‌عنوان معلم، و مشارکت‌های شفاف او در کنفرانس‌ها و بحث‌های غیررسمی، ارائه شده است. فوق العاده تاثیرگذار بوده است اکنون به مناسبت شصتمین سالگرد تولد ولفگانگ توماس برای ارائه یک تور افق در نظریه و منطق اتوماتا استفاده می کنیم. بیست مقاله گردآوری شده در این مجلد که توسط کارشناسان حوزه مربوطه به دعوت ویراستاران نوشته شده است، بسیاری از جنبه های مختلف منطق و نظریه خودکار را پوشش می دهد. آنها بر ارتباط تئوری و منطق اتوماتا با سایر رشته‌ها مانند نظریه پیچیدگی، بازی‌ها، الگوریتم‌ها و نظریه نیمه‌گروهی تأکید می‌کنند و بر اهمیت آن‌ها برای کاربردهای مدرن در علوم رایانه مانند سنتز و تأیید سیستم‌های واکنشی تأکید می‌کنند. این جلد تحولات علمی مدرن را در یک چشم انداز تاریخی قرار می دهد و نشان می دهد که چگونه آنها در بیش از چهل سال تئوری خودکار و منطق ریاضی ریشه دارند. شاید مهم‌تر از آن، نویسندگان دیدگاه‌های رایج اتوماتا و روش‌های مبتنی بر منطق را در حوزه‌های مختلف علوم رایانه ارائه و مورد بحث قرار دهند. درباره پیچیدگی توپولوژیکی زبان‌های درختی
کنترل کننده های غیر قطعی فرآیندهای غیر قطعی
قابلیت دسترسی در فرآیندهای تصمیم گیری پاداش مارکوف زمان پیوسته
نظریه های منطقی و عملیات سازگار
جبر جنگل
خودکار و نیمه گروه هایی که کلمات بی نهایت را تشخیص می دهند
قطعی گرامرهای گراف
عملیات گراف قابل تعریف بدون کمیت با حفظ قابلیت تشخیص
زبانهای قابل تعریف مرتبه اول
توابع پیچیدگی مبتنی بر ماتریس و زبانهای تصویر قابل تشخیص
استفاده از بهینه Blackwell: اولویت بازیهای میانگین سود به عنوان محدودیت‌های بازی‌های چند تخفیف
منطق، نمودارها و الگوریتم‌ها
منطق‌ها و بازی‌های غیرمعمول نقطه ثابت
خودکار جهانی
خودکار درختی از بالا به پایین قطعی: گذشته، حال ، و آینده
صفحه بیانی وجود منطق های مونادیک روی کلمات، درختان، تصاویر و نمودارها
استراتژی های ساختاریافته در بازی ها روی نمودارها
شمارش در درختان
کمیت سازهای مدولار
خودکار: از منطق تا الگوریتم

Издательство Amsterdam University Press, 2008, -737 pp. Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. Although both automata theory and mathematical logic look back to a much longer history, they have come together in the 1960s through the fundamental work of Büchi, Elgot, Rabin and others who showed the expressive equivalence of automata with logical systems such as monadic second-order logic on finite and infinite words and trees. This allowed the handling of specifications (where global system properties are stated) and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specification) in a single framework. Moreover this framework offered algorithmic procedures for essential questions such as the consistency of the specifications or the correctness of implementations. Through the methodology of model-checking the connection between automata theory and logic has indeed become the basis of efficient verification methods with industrial scale applications.
Wolfgang Thomas is one of the leading scientists in logic and automata theory. He has shaped this scientific area, not only through many deep and beautiful results, but also through his ability to bring together different research threads, to provide a convincing synthesis of them, and to point out new and promising directions. For a whole generation of scientists in the field, including most of the collaborators of this volume, his tutorials and surveys on automata theory, language theory and logic, his activities as a teacher, and his lucid contributions at conferences and in informal discussions, have been extremely influential. We now take the occasion of the 60th birthday of Wolfgang Thomas to present a tour d’horizon on automata theory and logic. The twenty papers assembled in this volume, written by experts of the respective area upon invitation by the editors, cover many different facets of logic and automata theory. They emphasize the connections of automata theory and logic to other disciplines such as complexity theory, games, algorithms, and semigroup theory and stress their importance for modern applications in computer science such as the synthesis and verification of reactive systems. The volume puts modern scientific developments into a historical perspective, and shows how they are rooted in more than forty years of automata theory and mathematical logic. Perhaps even more importantly, the authors present and discuss current perspectives of automata and logic based methodologies in different areas of computer science. On the topological complexity of tree languages
Nondeterministic controllers of nondeterministic processes
Reachability in continuous-time Markov reward decision processes
Logical theories and compatible operations
Forest algebras
Automata and semigroups recognizing infinite words
Deterministic graph grammars
Quantifier-free definable graph operations preserving recognizability
First-order definable languages
Matrix-based complexity functions and recognizable picture languages
Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games
Logic, graphs, and algorithms
Non-regular fixed-point logics and games
The universal automaton
Deterministic top-down tree automata: past, present, and future
Expressive power of monadic logics on words, trees, pictures, and graphs
Structured strategies in games on graphs
Counting in trees
Modular quantifiers
Automata: from logics to algorithms