Comparing Degrees of Non-Determinism in Expression Evaluation

Hayes, Ian J.; Burns, Alan; Dongol, Brijesh; Jones, Cliff B.
June 2013
Computer Journal;Jun2013, Vol. 56 Issue 6, p741
Academic Journal
Expression evaluation in programming languages is normally assumed to be deterministic; however, if an expression involves variables that are being modified by the environment of the process during its evaluation, the result of the evaluation can be non-deterministic. Two common scenarios in which this occurs are concurrent programs within which processes share variables and real-time programs that interact to monitor and/or control their environment. In these contexts, although any particular evaluation of an expression gives a single result, there is a range of possible values that could be returned depending on the relative timing between modification of a variable by the environment and its access within the expression evaluation. To compare the semantics of non-deterministic expression evaluation, one can use the set of possible values the expression evaluation could return. This paper formalizes three approaches to non-deterministic expression evaluation, highlights their commonalities and differences, shows the relationships between the approaches and explores conditions under which they coincide. Modal operators representing that a predicate holds for all possible evaluations and for some possible evaluation are associated with each of the evaluation approaches, and the properties and relationships between these operators are investigated. Furthermore, a link is made to a new notation used in reasoning about interference.


Related Articles

  • The SL Synchronous Language. Boussinot, Frédéric; de Simone, Robert // IEEE Transactions on Software Engineering;Apr96, Vol. 22 Issue 4, p256 

    We present SL, a new programming language of the synchronous reactive family in which hypotheses about signal presence/absence are disallowed. One can decide that a signal is absent during an instant only at the end of this instant, and so reaction to this absence is delayed to the next instant....

  • Application of advanced programming concepts in metamodelling. Berg, Henning; Møller.-Pedersen, Birger; Krogdahl, Stein // Norsk Informatikkonferanse;2011, Issue 21-23, p207 

    Programming languages provide users with a rich palette of advanced mechanisms. Languages for metamodelling, on the other hand, usually provide simple mechanisms for making class models, i.e. classes with relations like specialisation, composition and associations. A metamodel defines the syntax...

  • Removing Cycles in Esterel Programs. Lukoschus, Jan; von Hanxleden, Reinhard // EURASIP Journal on Embedded Systems;2007 Special Issue 6, p1 

    Esterel belongs to the family of synchronous programming languages, which are affected by cyclic signal dependencies. This prohibits a static scheduling, limiting the choice of available compilation techniques for programs with such cycles. This work proposes an algorithm that, given a...

  • Derived types in semantic association discovery. J�msen, Janne; Niemi, Timo; J�rvelin, Kalervo // Journal of Intelligent Information Systems;Oct2010, Vol. 35 Issue 2, p213 

    Semantic associations are direct or indirect linkages between two entities that are construed from existing associations among entities. In this paper we extend our previous query language approach for discovering semantic associations with an ability to retrieve semantic associations that,...

  • A Semantic Approach to Virtual World Standards. Burden, David // IEEE Internet Computing;Nov2011, Vol. 15 Issue 6, p40 

    Three main approaches exist for virtual world standardization: interoperability, infrastructure, and semantic markup languages. Most standards efforts to date have concentrated on virtual worlds' graphical aspects rather than their semantic content. Here, the author uses an example audio-only...

  • Model Checking Multi-Agent Systems. Bourahla, Mustapha; Benmohamed, Mohamed // Informatica (03505596);Jun2005, Vol. 29 Issue 2, p189 

    Multi-agent systems are increasingly complex, and the problem of their verification and validation is acquiring increasing importance. In this paper we show how a well known and effective verification technique, model checking, can be generalized to deal with multi-agent systems. This paper...

  • Problem frame semantics for software development. Hall, Jon G.; Rapanotti, Lucia; Jackson, Michael // Software & Systems Modeling;May2005, Vol. 4 Issue 2, p189 

    This paper presents a framework for understanding Problem Frames that locates them within the Requirements Engineering model of Zave and Jackson, and its subsequent formalization in the Reference Model of Gunter et al. It distinguishes between problem frames, context diagrams and problem...

  • Testing for refinement in Circus. Cavalcanti, Ana; Gaudel, Marie-Claude // Acta Informatica;Mar2011, Vol. 48 Issue 2, p97 

    Circus combines constructs to define complex data operations and interactions; it integrates Z and CSP, and, distinctively, it is a language for refinement that can describe programs as well as specification and design models. The semantics is based on the unifying theories of programming (UTP)....

  • A Collaborative Svstem Software Solution for Modeling Business Flows Based on Automated Semantic Web Service Composition. SMEUREANU, Ion; DIOŞTEANU, Andreea // Informatica Economica;2009, Vol. 13 Issue 2, p32 

    Nowadays, business interoperability is one of the key factors for assuring competitive advantage for the participant business partners. In order to implement business cooperation, scalable, distributed and portable collaborative systems have to be implemented. This article presents some of the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics