Order-independence of vector-based transition systems
2010 (English)In: Proceedings 10th International Conference on Application of Concurrency to System Design (ACSD’10, Braga, Portugal, June 21-25, 2010), Los Alamitos, Calif.: IEEE Computer Society, 2010, p. 115-123Conference paper, Published paper (Refereed)
Abstract [en]
Semantics of many specification languages, particularly those used in the domain of hardware, is described in terms of vector-based transition systems. In such a transition system, each macro-step transition is labeled by a vector of inputs. When performing a macro-step, several inputs may potentially change. Each macro-step can thus be decomposed in a number of micro-steps, taking one input change at a time into account. This is akin to an interleaving semantics, where a concurrent step is represented by an interleaving of its constituting components. We present abstract criteria on vector-based transition systems, which guarantee that the next state computation is independent of the order in which these micro-steps are executed. If our abstract criteria are satisfied by the semantic definition of a certain specification, then its state-space generation or exploration algorithm needs to only consider one representative among all possible permutations of such micro-steps. We demonstrate the applicability of our abstract criteria to the specification of transistor netlists. © 2010 IEEE.
Place, publisher, year, edition, pages
Los Alamitos, Calif.: IEEE Computer Society, 2010. p. 115-123
Series
International Conference on Application of Concurrency to System Design. Proceedings, ISSN 1550-4808
Keyword [en]
Interleaving semantics, Micro-steps, State-space generation, Step transitions, Transition system, Vector-based
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hh:diva-20521DOI: 10.1109/ACSD.2010.24Scopus ID: 2-s2.0-77957558045ISBN: 978-076954066-5 OAI: oai:DiVA.org:hh-20521DiVA, id: diva2:584488
Conference
The 10th International Conference on Application of Concurrency to System Design
2013-01-092013-01-082018-01-11Bibliographically approved