A structured operational semantics for UML-statecharts

The Unified Modeling Language (UML) has gained wide acceptance in very short time because of its variety of well-known and intuitive graphical notations. However, this comes at the price of an unprecise and incomplete semantics definition. This insufficiency concerns single UML diagram notations on their own as well as their integration. In this paper, we focus on the notation of UML-statecharts. Starting with a precise textual syntax definition, we develop a precise structured operational semantics (SOS) for UML-statecharts. Besides the support of interlevel transitions and in contrast to related work, our semantics definition supports characteristic UML-statechart features like the history mechanism as well as entry and exit actions. Initial submission: 19 February 2002 / Revised submission: 28 October 2002 Published online: 2 December 2002     

A security flow control algorithm and its denotational semantics correctness proof

We derive a security flow control algorithm for message-based, modular systems and prove the algorithm correct. The development is noteworthy because it is completely rigorous: the flow control algorithm is derived as an abstract interpretation of the denotational semantics of the programming language for the modular system, and the correctness proof is a proof by logical relations of the congruence between the denotational semantics and its abstract interpretation. Effectiveness is also addressed: we give conditions under which an abstract interpretation can be computed as a traditional iterative data flow analysis, and we prove that our security flow control algorithm satisfies the conditions. We also show that symbolic expressions (that is, data flow values that contain unknowns) can be used in a convergent, iterative analysis. An important consequence of the latter result is that the security flow control algorithm can analyse individual modules in a system for well formedness and later can link the analyses to obtain an analysis of the entire system.     

A practical approach to implementing real-time semantics

This paper investigates implementations of process algebras which are suitable for modeling concurrent real-time systems. It suggests an approach for efficiently implementing real-time semantics using dynamic priorities. For this purpose a process algebra with dynamic priority is defined, whose semantics corresponds one-to-one to traditional real-time semantics. The advantage of the dynamic-priority approach is that it drastically reduces the state-space sizes of the systems in question while preserving all properties of their functional and real-time behavior. The utility of the technique is demonstrated by a case study that deals with the formal modeling and verification of several aspects of the widely-used SCSI-2 bus-protocol. The case study is carried out in the Concurrency Workbench of North Carolina, an automated verification tool in which the process algebra with dynamic priority is implemented. It turns out that the state space of the bus-protocol model is about an order of magnitude smaller than the one resulting from real-time semantics. The accuracy of the model is proved by applying model checking for verifying several mandatory properties of the bus protocol. This revised version was published online in June 2006 with corrections to the Cover Date.     

A rewriting logic approach to operational semantics

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, continuation-based semantics, and the chemical abstract machine. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

Multilevel structured program designs and correctness proving

A mathematical model of a program specification and design language is considered. A system of axioms is proposed for proving formulas interpreted as assertions of logical consistency of specifications. The results provide a mathematical foundation for the development of MSPD tools.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 98–107, September–October, 1991.     

A structured approach to language design

This report is an attempt at systematizing a set of ground rules for high-level language design. It recommends the use of a hierarchical semantic model schema. HGL, in a step by step, top-down approach imposing more and more structure on the language components as the design becomes solidified. The approach is demonstrated by showing the stepwise design of the high-level language, GRAAL. The method recommended is divided into three major phases. The first is an informal one. The second is encoding the language components into a very high-level model. This high-level design allows a redesign of language components before they have been specified at too detailed a level. The third phase is to design the compiler in HGL using the final language design.     

A structured approach to program optimization

Software engineering should provide software engineers with methodologies and tools suitable for use in that small number of applications where efficiency is really important. In order to do that, the optimization process should be a clearly visible phase of the software lifecycle (regardless of the particular software development paradigm adopted), so that it can be regulated, securing the production of good quality and efficient software. With this in mind, the author suggests an approach to program optimization based on a paradigm, a method, some principles and guidelines, and some well-known techniques     

From static output feedback to structured robust static output feedback: A survey

This paper reviews the vast literature on static output feedback design for linear time-invariant systems including classical results and recent developments. In particular, we focus on static output feedback synthesis with performance specifications, structured static output feedback, and robustness. The paper provides a comprehensive review on existing design approaches including iterative linear matrix inequalities heuristics, linear matrix inequalities with rank constraints, methods with decoupled Lyapunov matrices, and non-Lyapunov-based approaches. We describe the main difficulties of dealing with static output feedback design and summarize the main features, advantages, and limitations of existing design methods.     

Reflect: A practical approach to web semantics

To date, adding semantic capabilities to web content usually requires considerable server-side re-engineering, thus only a tiny fraction of all web content currently has semantic annotations. Recently, we announced Reflect (http://reflect.ws), a free service that takes a more practical approach: Reflect uses augmented browsing to allow end-users to add systematic semantic annotations to any web-page in real-time, typically within seconds. In this paper we describe the tagging process in detail and show how further entity types can be added to Reflect; we also describe how publishers and content providers can access Reflect programmatically using SOAP, REST (HTTP post), and JavaScript. Usage of Reflect has grown rapidly within the life sciences, and while currently only genes, protein and small molecule names are tagged, we plan to soon expand the scope to include a much broader range of terms (e.g., Wikipedia entries). The popularity of Reflect demonstrates the use and feasibility of letting end-users decide how and when to add semantic annotations. Ultimately, ‘semantics is in the eye of the end-user’, hence we believe end-user approaches such as Reflect will become increasingly important in semantic web technologies.     

Axiomatic approach to total correctness of programs

Summary We present here an axiomatic approach which enables one to prove by formal methods that his program is totally correct (i.e., it terminates and is logically correct—does what it is supposed to do). The approach is similar to Hoare's approach [3] for proving that a program is partially correct (i.e., that whenever it terminates it produces correct results). Our extension to Hoare's method lies in the possibility of proving both correctness and termination by one unified formalism. One can choose to prove total correctness by a single step, or by incremental proof steps, each step establishing more properties of the program.     

Methods for specifying static semantics

The formal specification of a programming language involves the specification of three types of rules: syntax, static semantics and semantics. Various methods have been proposed for specifying the static semantic rules of programming languages, but as yet no method has received general acceptance. This paper looks at several different specification techniques and attempts to isolate the basic mechanisms used by each of them and explain the pattern of development of specification techniques for static semantics.     

An elementary and unified approach to program correctness

We present through the algorithmic language DHL (Dijkstra-Hehner language), a practical approach to a simple first order theory based on calculational logic, unifying Hoare and Dijkstra’s iterative style of programming with Hehner’s recursive predicative programming theory, getting the “best of the two worlds” and without having to recur in any way to higher-order approaches such as predicate transformers, Hoare logic, fixed-point or relational theory.     

Learning the semantics of structured data sources

Information sources such as relational databases, spreadsheets, XML, JSON, and Web APIs contain a tremendous amount of structured data that can be leveraged to build and augment knowledge graphs. However, they rarely provide a semantic model to describe their contents. Semantic models of data sources represent the implicit meaning of the data by specifying the concepts and the relationships within the data. Such models are the key ingredients to automatically publish the data into knowledge graphs. Manually modeling the semantics of data sources requires significant effort and expertise, and although desirable, building these models automatically is a challenging problem. Most of the related work focuses on semantic annotation of the data fields (source attributes). However, constructing a semantic model that explicitly describes the relationships between the attributes in addition to their semantic types is critical.We present a novel approach that exploits the knowledge from a domain ontology and the semantic models of previously modeled sources to automatically learn a rich semantic model for a new source. This model represents the semantics of the new source in terms of the concepts and relationships defined by the domain ontology. Given some sample data from the new source, we leverage the knowledge in the domain ontology and the known semantic models to construct a weighted graph that represents the space of plausible semantic models for the new source. Then, we compute the top k candidate semantic models and suggest to the user a ranked list of the semantic models for the new source. The approach takes into account user corrections to learn more accurate semantic models on future data sources. Our evaluation shows that our method generates expressive semantic models for data sources and services with minimal user input. These precise models make it possible to automatically integrate the data across sources and provide rich support for source discovery and service composition. They also make it possible to automatically publish semantic data into knowledge graphs.     

A Standard Model—Theoretic Approach to Operational Semmantics of Recursiv Programs

In this paper we try to introduce a new approach to operational semantics of recursive programs by using ideas in the“priority method”which is a fundamental tool in Recursion Theory.In lieu of modelling partial functions by introducing undefined values in a traditional approach,we shall define a priority derivation tree for every term,and by respecting thr rule“attacking the subtem of the highest priority first”we define transition relations,computation sequences etc.directly based on a standard interpretation whic includes no undefined value in its domain,Finally,we prove that our new approach generates the same opeational semantics as the traditional one.It is also pointed out that we can use our strategy oto refute a claim of Loeckx and Sieber that the opperational semantics of recursive programs cannot be built based on predicate logic.     

Teaching programming: A spiral approach to syntax and semantics

Coupling the recently proposed syntactic/semantic model of programmer behavior [1] with classic educational psychological theories yields new insights to teaching programming to novices. These new insights should make programming education more natural to students. alleviate “computer shock” (the analog of “math anxiety” [2]) and promote the development of widespread “computer literacy”.The spiral approach is the parallel acquisition of syntactic and semantic knowledge in a sequence which provokes student interest by using meaningful examples, builds on previous knowledge, is in harmony with the student's cognitive skills, provides reinforcement of recently acquired material and develops confidence through successful accomplishment of increasingly difficult tasks. The relationship of structured programming and flowcharts to the spiral approach is discussed.     

Towards the correctness and consistency of update semantics insemantic database schema

Discusses a paradigm and prototype system for the design-time expression, checking and automatic implementation of the semantics of database updates. Enforcement rules are viewed as the implementation of constraints and are specified, checked for consistency, and then finally mapped to object-oriented code during database design. A classification of enforcement rule types is provided as a basis for these design activities, and the general strategy for specification, analysis and implementation of these rules within a semantic modeling paradigm is discussed. SORAC (Semantics, Objects, Relationships And Constraints), a prototype database design system of the University of Rhode Island, is also described     

Nondeterministic flowchart programs with recursive procedures: semantics and correctness I

In this paper, we study some aspects of the semantics of nondeterministic flowchart programs with recursive procedures. In the first part of this work we provide the operational semantics of programs using the concept of an execution tree. We propose a new definition of the semantics of a non-deterministic recursive program as a mapping from the input domain to the set of execution trees determined by the program. Using this new concept, we prove that every nondeterministic flowchart program with recursive procedures can be unfolded into a semantically equivalent infinite pure flowchart (without procedures). This result is applied in the second part of this work to prove the soundness of an inductive assertion method which is also complete with a finite number of assertions (contrary to De Bakker and Meertens's method [11]).