A comparative study of two formal semantics of the SIGNAL language

SIGNAL is a part of the synchronous languages family, which are broadly used in the design of safety-critical real-time systems such as avionics, space systems, and nuclear power plants. There exist several semantics for SIGNAL, such as denotational semantics based on traces (called trace semantics), denotational semantics based on tags (called tagged model semantics), operational semantics presented by structural style through an inductive definition of the set of possible transitions, operational semantics defined by synchronous transition systems (STS), etc. However, there is little research about the equivalence between these semantics. In this work, we would like to prove the equivalence between the trace semantics and the tagged model semantics, to get a determined and precise semantics of the SIGNAL language. These two semantics have several different definitions respectively, we select appropriate ones and mechanize them in the Coq platform, the Coq expressions of the abstract syntax of SIGNAL and the two semantics domains, i.e., the trace model and the tagged model, are also given. The distance between these two semantics discourages a direct proof of equivalence. Instead, we transformthem to an intermediate model, which mixes the features of both the trace semantics and the tagged model semantics. Finally, we get a determined and precise semantics of SIGNAL.     

Towards a verified compiler prototype for the synchronous language SIGNAL

SIGNAL belongs to the synchronous languages family which are widely used in the design of safety-critical real-time systems such as avionics, space systems, and nuclear power plants. This paper reports a compiler prototype for SIGNAL. Compared with the existing SIGNAL compiler, we propose a new intermediate representation (named S-CGA, a variant of clocked guarded actions), to integrate more synchronous programs into our compiler prototype in the future. The front-end of the compiler, i.e., the translation from SIGNAL to S-CGA, is presented. As well, the proof of semantics preservation is mechanized in the theorem prover Coq. Moreover, we present the back-end of the compiler, including sequential code generation and multithreaded code generation with time-predictable properties. With the rising importance of multi-core processors in safetycritical embedded systems or cyber-physical systems (CPS), there is a growing need for model-driven generation of multithreaded code and thus mapping on multi-core. We propose a time-predictable multi-core architecture model in architecture analysis and design language (AADL), and map the multi-threaded code to this model.     

Equivalence of formal semantics definition methods

There are numerous methods of formally defining the semantics of computer languages. Each method has been designed to fulfil a different purpose. For example, some have been designed to make reasoning about languages as easy as possible; others have been designed to be accessible to a large audience and some have been designed to ease implementation of languages. Given two semantics definitions of a language written using two separate semantics definition methods, we must be able to show that the two are in fact equivalent. If we cannot do this then we either have an error in one of the semantics definitions, or more seriously we have a problem with the semantics definition methods themselves.Three methods of defining the semantics of computer languages have been considered, i.e. Denotational Semantics, Structural Operational Semantics and Action Semantics. An equivalence between these three is shown for a specific example language by first defining its semantics using each of the three definition methods. The proof of the equivalence is then constructed by selecting pairs of the semantics definitions and showing that they define the same language.A full version of this paper can be accessed via our web page http://www.cs.man.ac.uk/fmethods/ facj.html     

A formal semantics for debugging synchronous message passing-based concurrent programs

In this paper, we propose a semantic framework to debug synchronous message passing-based con- current programs, which are increasingly useful as parallel computing and distributed systems become more and more pervasive. We first design a concurrent programming language model to uniformly represent exist- ing concurrent programming languages. Compared to sequential programming languages, this model contains communication statements, i.e., sending and receiving statements, and a concurrent structure to represent com- munication and concurrency. We then propose a debugging process consisting of a tracing and a locating procedure. The tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating bugs. We provide for the tracing procedure a struc- tural operational semantics to represent synchronous communication and concurrency. The locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure, generates a fix equation, and tries to fix the bug by solving the fix equation. We also propose a structural operational semantics for the locating procedure. We supply two examples to test our proposed operational semantics.     

Translational Semantics for a Conceptual Level Query Language

A conceptual level database language for the entity relationship (ER) model implicitly contains integrities basic to ER concepts and special retrieval semantics for inheritances of attributes and relationships.Prolog,which belongs to the logical and physical level,cannot be used as a foundation to directly define the database language.It is shown how Prolog can be enhanced to understand the concepts of entities,relationships,attributes and is-a relationships.The enhanced Prolog is then used as a foundation to define the semantics of a database query language for the ER model.The three basic functions of model specification,updates and retrievals are defined.     

Towards a simple and safe Objective Caml compiling framework for the synchronous language SIGNAL

This paper presents a simple and safe compiler, called MinSIGNAL, from a subset of the synchronous dataflow language SIGNAL to C, as well as its existing enhancements. The compiler follows a modular architecture, and can be seen as a sequence of source-to-source transformations applied to an intermediate representation which is named Synchronous Clocked Guarded Actions (S-CGA) and translation to sequential imperative code. Objective Caml (OCaml) is used for the implementation of MinSIGNAL. As a modern functional language, OCaml is adapted to symbolic computation and so, particularly suitable for compiler design and implementation of formal analysis tools. In particular, the safety of its type checking allows to skip some verification that would be mandatory with other languages. Additionally, this work is a basis for the formal verification of the compilation of SIGNAL with a theorem prover such as Coq.     

自然语言语义理解在反垃圾邮件中的应用

在分析了基于统计的垃圾邮件分类中关键词的语义缺失问题后,提出将基于本体的自然语言语义理解应用于反垃圾邮件中,以解决关键词的语义问题。经过对垃圾邮件的特征进行分析,设计了关键词驱动的句法分析及基于本体的语义推理,在一定程度上解决了邮件过滤过程中词和句子的语义缺失,为垃圾邮件过滤提供了有益的探索。     

A process oriented semantics of the PRAM-language FORK

The parallel language FORK [1], based on a scalable shared memory model, is a PASCAL-like language with some additional parallel constructs. A PRAM (Parallel Random Access Machine) algorithm can be expressed on a high level of abstraction as a FORK program which is translated into efficient PRAM code guaranteeing theoretically predicted runtimes.

In this paper, we concentrate on those features of the language FORK related to parallelism, such as the group concept, a shared memory access and synchronous or asynchronous execution. We present a trace-based denotational interleaving semantics where processes describe synchronous computations. Processes are created or deleted dynamically and run asynchronously. Interleaving rules reflect the underlying CRCW (concurrent-read-concurrent-write) PRAM model.     

A formal semantics of nested atomic sections with thread escape

The multi-core trend is widening the gap between programming languages and hardware. Taking parallelism into account in the programs is necessary to improve performance. Unfortunately, current mainstream programming languages fail to provide suitable abstractions to do so. The most common pattern relies on the use of mutexes to ensure mutual exclusion between concurrent accesses to a shared memory. However, this model is error-prone and scales poorly by lack of modularity. Recent research proposes atomic sections as an alternative. The user simply delimits portions of code that should be free from interference. The responsibility for ensuring interference freedom is left either to the compiler or to the run-time system.In order to provide enough modularity, it is necessary that both atomic sections could be nested and threads could be forked inside an atomic section. In this paper we focus on the semantics of programming languages providing these features. More precisely, without being tied to a specific programming language, we consider program traces satisfying some basic well-formedness conditions. Our main contribution is the precise definition of atomicity, well-synchronisation and the proof that the latter implies the strong form of the former. A formalisation of our results in the Coq proof assistant is described.     

Strong equivalence of logic programs under the infinite-valued semantics

We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued semantics [P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441-467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics.     

A semantics of introspection in a reflective prototype-based language

In Malenfant et al. [19], we have described a reflective model for a prototype-based language based on thelookup o apply reflective introspection protocol. In this paper, we augment our previous protocol by converting it to handle continuations reified as first-class objects. First-class continuations provide much more control over the current computation; during the introspection phase fired by message sending, they make it possible not only to change the behavior of the program for that message but also for the entire future computation. In this paper, we provide this introspection protocol with a formal semantics. This result is obtained by exhibiting a mapping from program configurations to priority rewrite systems (PRS) as well as a mapping from message expressions to ground first-order terms used to query the PRS. Other advantages of this approach are: to ensure the termination of the introspection using the smallest set of formally justified conditions and to provide a clear declarative account of this reflective protocol. The PRS also appears as a meta-level to the base language, independent of the implementation, but from which we derive fundamental clues to obtain an efficient language processor. By our new model, we finally highlight the link between reflection in object-oriented languages and the one originally proposed by 3-Lisp [24], although object-orientation provides reusability to reflection, making it easier to use.     

A formal semantics of SMIL: a web standard to describe multimedia documents

This paper presents a formal semantics of a subset of SMIL2.0: a W3C recommendation to describe interactive multimedia documents on the Web. This work has been used during the design of this standard to improve its consistency. It is also intended to help SMIL developers to understand the specification. Doing so, it will contribute to increase SMIL chances of success in achieving the interoperability goal and, thus, its impact on the new information society.     

A Constructor-Based EI-Model Semantics of EI-CTRS

This paper investigates the semantics of conditional term rewriting systems with negation (denoted by EI-CTRS),called constructor-based EI-model semantics.The introduction of “≠” in EI-CTRS make EI-CTRS more difficult to study.This is in part because of a failure of EI-CTRS to guarantee that there exist least Herbrand models in classical logical point of views.The key idea of EI-model is to explain that t≠s” means that the two concepts represented by t and s respectively actually belong to distinguished basic concepts represented by two constructor-ground terms.We define the concept of EI-model,and show that there exist least Herbrand EI-models for EI-satisfiable EI-CTRS.From algebraic and logic point of view,we show that there are very strong reasons for regarding the least Herbrand EI-models as the intended semantics of EI-CTRS.According to fixpoint theory,we develop a method to construct least Herbrand EI-models in a bottom-up manner.Moreover,we discuss soundness and completeness of EI-rewrite for EI-model semantics.     

The Structure and Semantics of an Object-Oriented Logic Programming Language: SCKE

The development of the object-oriented paradigm has suffered from the lack of any generally accepted formal foundations for its semantic definition.To address this issue,we propose the development of the logic-based semantics of the object-oriented paradigm.By combining the logic-with the object-oriented paradigm of computing first,this paper discusses formally the semantics of a quite purely object-oriented logic paradigm in terms of proof theory,model theory and fixpoint theory from the viewpoint of logic.The operational and declarative semantics is given.And then the correspondence between soundness and completeness has been discussed formally.     

On the use of formal methods to model and verify neuronal archetypes

Having a formal model of neural networks can greatly help in understanding and verifying their properties, behavior, and response to external factors such as disease and medicine. In this paper, we adopt a formal model to represent neurons, some neuronal graphs, and their composition. Some specific neuronal graphs are known for having biologically relevant structures and behaviors and we call them archetypes. These archetypes are supposed to be the basis of typical instances of neuronal information processing. In this paper we study six fundamental archetypes (simple series, series with multiple outputs, parallel composition, negative loop, inhibition of a behavior, and contralateral inhibition), and we consider two ways to couple two archetypes: (i) connecting the output(s) of the first archetype to the input(s) of the second archetype and (ii) nesting the first archetype within the second one. We report and compare two key approaches to the formal modeling and verification of the proposed neuronal archetypes and some selected couplings. The first approach exploits the synchronous programming language Lustre to encode archetypes and their couplings, and to express properties concerning their dynamic behavior. These properties are verified thanks to the use of model checkers. The second approach relies on a theorem prover, the Coq Proof Assistant, to prove dynamic properties of neurons and archetypes.     

A linguistic ontology of space for natural language processing

We present a detailed semantics for linguistic spatial expressions supportive of computational processing that draws substantially on the principles and tools of ontological engineering and formal ontology. We cover language concerned with space, actions in space and spatial relationships and develop an ontological organization that relates such expressions to general classes of fixed semantic import. The result is given as an extension of a linguistic ontology, the Generalized Upper Model, an organization which has been used for over a decade in natural language processing applications. We describe the general nature and features of this ontology and show how we have extended it for working particularly with space. Treaitng the semantics of natural language expressions concerning space in this way offers a substantial simplification of the general problem of relating natural spatial language to its contextualized interpretation. Example specifications based on natural language examples are presented, as well as an evaluation of the ontology's coverage, consistency, predictive power, and applicability.     

A descriptive semantics of modelling process catering for whole product parametric

To date, the entire product parametric technology has made great progress to significantly improve product design efficiency. However, the technology uses an established modelling process, which makes it very difficult to adapt to changing product requirements. A method that can be customised for the whole machine is discussed in this paper; this method is intended to increase the adaptability of the entire product parametric technology. First, a frame model concept is proposed based on an analysis of a large number of product modelling processes. Second, a semantic model for describing the modelling process is proposed, and its instantiation is studied. Next, according to the semantics of the modelling process, a product parametric modelling system is established. Finally, based on an examination of the electronic module modelling, it was found that modelling efficiency increased significantly.     

Polychronous automata and their use for formal validation of AADL models

This paper investigates how state diagrams can be best represented in the polychronous model of computation (MoC) and proposes to use this model for code validation of behavior specifications in architecture analysis & design language (AADL). In this relational MoC, the basic objects are signals, which are related through dataflow equations. Signals are associated with logical clocks, which provide the capability to describe systems in which components obey multiple clock rates. We propose a model of finite-state automata, called polychronous automata, which is based on clock relationships. A specificity of this model is that an automaton is submitted to clock constraints, which allows one to specify a wide range of control-related configurations, being either reactive or restrictive with respect to their control environment. A semantic model is defined for these polychronous automata, which relies on boolean algebra of clocks. Based on a previously defined modeling method for AADL software architectures using the polychronous MoC, the proposed model is used as a formal model for the AADL behavior annex. This is illustrated with a case study involving an adaptive cruise control system.     

Intuitionistic Logic as the Implement of Incremental Model Construction for Natural Language

The process of understanding natural language can be viewed as the process of model construction.This paper,employing Kripke frame for intuitionistic logic semantics as the implement of model construction for natural language,introduces a method of incremental model constuction.