Hierarchy of Asynchronous Automata
| Autor: | Rémi Morin |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
Block cellular automaton
Theoretical computer science General Computer Science Computer science Concurrency Timed automaton ω-automaton Petri net distributed system Mobile automaton Theoretical Computer Science Stochastic cellular automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES shared memory Deterministic automaton Asynchronous (cellular) automaton (asynchronous) transition system concurrency Mazurkiewicz traces Asynchronous cellular automaton Computer Science::Formal Languages and Automata Theory Computer Science(all) |
| Zdroj: | Electronic Notes in Theoretical Computer Science. 28:22-39 |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/s1571-0661(05)80628-0 |
| Popis: | We study a natural notion of communication structure associated with asynchronous automata: we characterize which transition systems are isomorphic to an asynchronous automaton w.r.t. a given communication structure. For that, we present an algorithm to split global states into local states of communicating processes, similar to the regional technique for the synthesis problem of Petri nets. Our main result is an axiomatic criterion for the communication structures which decompose the same class of transition systems; this allows us to characterize and compare several particular classes of asynchronous automata. An immediate corollary of this study is a generic extension of Zielonka's theorem. We finally apply this method to asynchronous automata which describe systems of processes that communicate through shared memories. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect