Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A hierarchy of compositional models of I/O-Automata
RISE - Research Institutes of Sweden, ICT, SICS.
1991 (engelsk)Rapport (Annet vitenskapelig)
Abstract [en]

A semantic model of computer systems is compositional if it adequately represents the behavior of the modeled systems in a context of other systems. A compositional model is thus a good basis for specifying and reasoning about systems in a modular fashion. I/O-automata is a class of communicating system which can represent several types of asyncronously communicating systems, such as message-passing distributed systems, systems with broadcast communication, and systems with shared variables. In contrast to many other classes of communicating systems (e.g. in CCS or CSP), semantic models based only on traces(sequences of communication events) can in a compositional way represent safety, liveness and many other proportiesd of I/O-automata. In this paper, we investigate which semantic models of I/O-automata are compositional, and which are not. The investigation is confined to models based on traces. We study a number of trace-based semantical models of I/O-automata, which differ in their capability to represent safety, liveness, termination, and divergence properties. The defined models can be naturally ordered into a hierarchy, according to how much information they convey about the modeled systems. The main contribution of the paper is an investigation of whether there are other compositional models between adjacent compositional models in our hierarchy. Surprisingly enough, we can prove that for several pairs of adjacent models in the hierarchy, the gap between the two models contains no other compositional model. For instance, the nonexistence of a compositional model in the gap between a model that represents safety properties and a model that represents liveness properties means that liveness properties cannot be only partially represented if compositionality is desired. We indicate how our results can be applied to derive results about full abstraction.

sted, utgiver, år, opplag, sider
Kista, Sweden: Swedish Institute of Computer Science , 1991, 1. , s. 28
Serie
SICS Research Report, ISSN 0283-3638 ; R91:04
HSV kategori
Identifikatorer
URN: urn:nbn:se:ri:diva-22172OAI: oai:DiVA.org:ri-22172DiVA, id: diva2:1041715
Merknad

An extended abstract of this research report has appeared under the same title in the Proceedings of the Symposium on mathematical Foundations of Computer Science, Banska Bystrica, Czeckoslovakia, Aug. 1990. published as vol. 452 of Lecture notes in Computer Science, Springer Verlag, pp347-354.

Tilgjengelig fra: 2016-10-31 Laget: 2016-10-31 Sist oppdatert: 2018-02-07bibliografisk kontrollert

Open Access i DiVA

fulltekst(3530 kB)67 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 3530 kBChecksum SHA-512
0034c6ba04d95c7eab077c3fec46c2c008fb8acd43f22910f13a97980e49aad19871e497bd02a7a263af3e2466e4c92bc387782e61525cd8c74845e6c34a9004
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 67 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 19 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
v. 2.41.0