hh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Semantics and expressiveness of ordered SOS
Eindhoven University of Technology, Den Dolech 2, NL-5612 AZ Eindhoven, The Netherlands.ORCID iD: 0000-0002-4869-6794
Imperial College London, UK.
Eindhoven University of Technology, Den Dolech 2, NL-5612 AZ Eindhoven, The Netherlands.
University of Leicester, UK.
2009 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 207, no 2, 85-119 p.Article in journal (Refereed) Published
Abstract [en]

Structured Operational Semantics (SOS) is a popular method for defining semantics by means of transition rules. An important feature of SOS rules isĀ negative premises, which are crucial in the definitions of such phenomena as priority mechanisms and time-outs. However, the inclusion of negative premises in SOS rules also introduces doubts as to the preferred meaning of SOS specifications.

Orderings on SOS rules were proposed by Phillips and Ulidowski as an alternative to negative premises. Apart from the definition of the semantics of positive GSOS rules with orderings, the meaning of more general types of SOS rules with orderings has not been studied hitherto. This paper presents several candidates for the meaning of general SOS rules with orderings and discusses their conformance to our intuition for such rules.

We take two general frameworks (rule formats) for SOS with negative premises and SOS with orderings, and present semantics-preserving translations between them with respect to our preferred notion of semantics. Thanks to our semantics-preserving translation, we take existing congruence meta-results for strong bisimilarity from the setting of SOS with negative premises into the setting of SOS with orderings. We further compare the expressiveness of rule formats for SOS with orderings and SOS with negative premises. The paper contains also many examples that illustrate the benefits of SOS with orderings and the properties of the presented definitions of meaning.

Place, publisher, year, edition, pages
Maryland Heights, USA: Academic Press, 2009. Vol. 207, no 2, 85-119 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:hh:diva-20505DOI: 10.1016/j.ic.2007.11.008Scopus ID: 2-s2.0-77949467060OAI: oai:DiVA.org:hh-20505DiVA: diva2:584676
Available from: 2013-01-09 Created: 2013-01-08 Last updated: 2014-11-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Mousavi, Mohammad Reza
In the same journal
Information and Computation
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 63 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf