Time and Petri Nets

در نگاه اول مفاهیم زمان و شبکه‌های پتری کاملاً متضاد هستند: در حالی که زمان وقوع رویدادها را در یک سیستم تعیین می‌کند، شبکه‌های پتری کلاسیک روابط علی خود را در نظر می‌گیرند و رویدادها را به عنوان سیستم‌های همزمان نشان می‌دهند. اما اگر نگاه دقیق‌تری به نحوه درهم تنیده شدن زمان و علیت بیندازیم، متوجه می‌شویم که راه‌های ممکن زیادی وجود دارد که در آن زمان و شبکه‌های پتری با هم تعامل دارند. این کتاب نگاهی دقیق‌تر به سه شبکه پتری وابسته به زمان دارد: شبکه‌های پتری زمان، شبکه‌های پتری زمان‌دار، و شبکه‌های پتری با پنجره‌های زمانی.

نویسنده ابتدا شبکه‌های پتری کلاسیک و ویژگی‌های اساسی آنها را توضیح می‌دهد. سپس سهم محوری کتاب معرفی الگوریتم‌های مختلف است که به ما امکان تجزیه و تحلیل شبکه‌های پتری وابسته به زمان را می‌دهد. برای شبکه‌های پتری تایم، نویسنده الگوریتمی ارائه می‌کند که معادل رفتاری شبکه‌ای را ثابت می‌کند که در آن زمان یک بار با اعداد واقعی و یک بار با اعداد طبیعی طراحی می‌شود، بنابراین می‌توانیم فضای حالت را کاهش دهیم و حالت‌های صحیح را منحصراً در نظر بگیریم. برای شبکه‌های پتری زمان‌بندی شده، نویسنده دو معادله حالت وابسته به زمان را معرفی می‌کند که شرایط کافی را برای غیرقابل دسترس بودن حالت‌ها فراهم می‌کند، و همچنین یک تبدیل محلی برای تبدیل این شبکه‌ها به شبکه‌های پتری زمان تعریف می‌کند. در نهایت، او نشان می‌دهد که شبکه‌های پتری با پنجره‌های زمانی، این توانایی را دارند که هر دنباله انتقالی را که در شبکه شلیک می‌شود، با حذف محدودیت‌های زمانی متوجه شوند.

این کلاس‌های شبکه‌های پتری وابسته به زمان نشان می‌دهند که زمان به تنهایی تغییری در تغییر نمی‌کند. قدرت شبکه پتری، در واقع ممکن است از زمان برای شلیک اجباری استفاده شود یا نباشد. برای شبکه‌های پتری تایم و شبکه‌های پتری زمان‌بندی شده می‌توان گفت که تورینگ قدرتمند هستند و بنابراین از تورهای پتری کلاسیک قدرتمندتر هستند، زیرا اجبار به شلیک در برخی از زمان‌ها وجود دارد. در مقابل، شبکه‌های پتری با پنجره‌های زمانی هیچ اجباری برای شلیک ندارند، قدرت بیان آن‌ها کمتر از ماشین‌های تورینگ است.

این کتاب از سخنرانی‌های پیشرفته مشتق شده است و متن با مثال‌ها و نمونه‌ها پشتیبانی می‌شود. تمرینات برای دوره های تحصیلات تکمیلی در علوم کامپیوتر، ریاضیات، مهندسی و رشته های مرتبط و به عنوان مرجعی برای محققان مناسب است.

At first glance the concepts of time and of Petri nets are quite contrary: while time determines the occurrences of events in a system, classic Petri nets consider their causal relationships and they represent events as concurrent systems. But if we take a closer look at how time and causality are intertwined we realize that there are many possible ways in which time and Petri nets interact. This book takes a closer look at three time-dependent Petri nets: Time Petri nets, Timed Petri nets, and Petri nets with time windows.

The author first explains classic Petri nets and their fundamental properties. Then the pivotal contribution of the book is the introduction of different algorithms that allow us to analyze time-dependent Petri nets. For Time Petri nets, the author presents an algorithm that proves the behavioral equivalence of a net where time is designed once with real and once with natural numbers, so we can reduce the state space and consider the integer states exclusively. For Timed Petri nets, the author introduces two time-dependent state equations, providing a sufficient condition for the non-reachability of states, and she also defines a local transformation for converting these nets into Time Petri nets. Finally, she shows that Petri nets with time-windows have the ability to realize every transition sequence fired in the net omitting time restrictions.

These classes of time-dependent Petri nets show that time alone does not change the power of a Petri net, in fact time may or may not be used to force firing. For Time Petri nets and Timed Petri nets we can say that they are Turing-powerful, and thus more powerful than classic Petri nets, because there is a compulsion to fire at some point in time. By contrast, Petri nets with time-windows have no compulsion to fire, their expressiveness power is less than that of Turing-machines.

This book derives from advanced lectures, and the text is supported throughout with examples and exercises. It is suitable for graduate courses in computer science, mathematics, engineering, and related disciplines, and as a reference for researchers.