The Meaning of Ordered SOS

MohammadReza Mousavi, Iain Phillips, Michel Reniers and Irek UlidowskiProceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'06), Kolkata, India, volume 4337 of Lecture Notes in Computer Science, Springer-Verlag, pages 334-345, December 2006.

Abstract

Structured Operational Semantics (SOS) is a popular method for defining semantics by means of transition rules. An important feature of transition rules, or simply SOS rules, are negative premises, which are crucial in the definitions of such phenomena as priority mechanisms and time-outs. Orderings on SOS rules were proposed by Phillips and Ulidowski as an alternative to negative premises. The meaning of general types of SOS rules with orderings has not been studied hitherto. This paper presents satisfactory ways of giving a meaning to general SOS rules with orderings. We also give semantics-preserving transformations between the two paradigms, namely, SOS with negative premises and SOS with orderings.

(Paper in .pdf format,     in .ps format)

@InProceedings{MousaviFSTTCS06,
    author      = "Mousavi, MohammadReza and Phillips, Iain C.C. and Reniers, Michel A. and Ulidowski, Irek",
    title       = "The Meaning of Ordered SOS",
    booktitle   = "Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'06)",
    series      = "Lecture Notes in Computer Science",
    editor      = "Arun-Kumar, S. and Garg, N.",
    pages       = "334--345",
    volume      = "4337",
    address     = "Kolkata, India",
    publisher  = "Springer-Verlag",
    year        = "2006"
}

Back to Publications Page