Combinatorics on Traces

موازی سازی یا همزمانی یکی از مفاهیم اساسی در علوم کامپیوتر است. اما با وجود اهمیت آن، روش‌های نظری برای مدیریت همزمانی هنوز به اندازه کافی توسعه نیافته‌اند. این جلد مطالعه جامعی از نظریه ردیابی Mazurkiewicz از دیدگاه جبری-ترکیبی ارائه می دهد. این نظریه به عنوان یک ابزار مهم برای یک درمان ریاضی دقیق سیستم های همزمان شناخته شده است. این جلد چندین حوزه تحقیقاتی مختلف را پوشش می‌دهد و نه تنها نتایج شناخته شده را در بر می‌گیرد، بلکه شامل نتایج جدید مختلفی است که در هیچ جای دیگری منتشر نشده است. فصل 1 مفاهیم اساسی را معرفی می کند. فصل 2 مسیر مستقیمی را به توصیف اوچمانسکی از زبان‌های ردیابی قابل تشخیص و تئوری Zielonka در مورد خودکارهای ناهمزمان می‌دهد. فصل 3 تئوری آثار را در شبکه های پتری اعمال می کند. نوعی مورفیسم بین شبکه ها معرفی شده است که مفهوم همگام سازی را تعمیم می دهد. فصل 4 یک پل جدید بین تئوری بازنویسی رشته و سری های قدرت رسمی ارائه می دهد. فصل 5 مقدمه ای بر یک نظریه ترکیبی بازنویسی روی ردیابی است که می تواند به عنوان یک حساب انتزاعی برای تبدیل فرآیندهای همزمان استفاده شود.

Parallelism or concurrency is one of the fundamental concepts in computer science. But in spite of its importance, theoretical methods to handle concurrency are not yet sufficiently developed. This volume presents a comprehensive study of Mazurkiewicz' trace theory from an algebraic-combinatorial point of view. This theory is recognized as an important tool for a rigorous mathematical treatment of concurrent systems. The volume covers several different research areas, and contains not only known results but also various new results published nowhere else. Chapter 1 introduces basic concepts. Chapter 2 gives a straight path to Ochmanski's characterization of recognizable trace languages and to Zielonka's theory of asynchronous automata. Chapter 3 applies the theory of traces to Petri nets. A kind of morphism between nets is introduced which generalizes the concept of synchronization. Chapter 4 provides a new bridge between the theory of string rewriting and formal power series. Chapter 5 is an introduction to a combinatorial theory of rewriting on traces which can be used as an abstract calculus for transforming concurrent processes.