Accepting splicing systems with permitting and forbidding words

In this paper we propose a generalization of the accepting splicing systems introduced in Mitrana et al. (Theor Comput Sci 411:2414–2422, 2010). More precisely, the input word is accepted as soon as a permitting word is obtained provided that no forbidding word has been obtained so far, otherwise it is rejected. Note that in the new variant of accepting splicing system the input word is rejected if either no permitting word is ever generated (like in Mitrana et al. in Theor Comput Sci 411:2414–2422, 2010) or a forbidding word has been generated and no permitting word had been generated before. We investigate the computational power of the new variants of accepting splicing systems and the interrelationships among them. We show that the new condition strictly increases the computational power of accepting splicing systems. Although there are regular languages that cannot be accepted by any of the splicing systems considered here, the new variants can accept non-regular and even non-context-free languages, a situation that is not very common in the case of (extended) finite splicing systems without additional restrictions. We also show that the smallest class of languages out of the four classes defined by accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediately derived from the proof of this result.     

On a generalization of Christoffel words: epichristoffel words

Sturmian sequences are well-known as the ones having minimal complexity over a 2-letter alphabet. They are also the balanced sequences over a 2-letter alphabet and the sequences describing discrete lines. They are famous and have been extensively studied since the 18th century. One of the extensions of these sequences over a k-letter alphabet, with k≥3, is the episturmian sequences, which generalizes a construction of Sturmian sequences using the palindromic closure operation. There exists a finite version of the Sturmian sequences called the Christoffel words. They have been known since the works of Christoffel and have interested many mathematicians. In this paper, we introduce a generalization of Christoffel words for an alphabet with 3 letters or more, using the episturmian morphisms. We call them the epichristoffel words. We define this new class of finite words and show how some of the properties of the Christoffel words can be generalized naturally or not for this class.     

Almost ASAP semantics: from timed models to timed implementations

In this paper, we introduce a parametric semantics for timed controllers called the Almost ASAP (as soon as possible) semantics. This semantics is a relaxation of the usual ASAP semantics (also called the maximal progress semantics) which is a mathematical idealization that cannot be implemented by any physical device no matter how fast it is. On the contrary, any correct Almost ASAP controller can be implemented by a program on a hardware if this hardware is fast enough. We study the properties of this semantics and show how it can be analyzed using the tool HyTech. A preliminary and short version of this paper appeared in the Proceedings of the 7th International Workshop on Hybrid Systems: Computation and Control (HSCC 2004), Lecture Notes in Computer Science, vol 2993, pp 296–310. This work was supported by the FRFC project ``Centre Fédéré en Vérification' funded by the Belgian National Science Fundation (FNRS) under grant nr 2.4530.02. Research fellow supported by the Belgian National Science Fundation (FNRS). Received November 2004 Revised April 2005 and May 2005 Accepted May 2005 by M. J. Butler     

Dream chip 1: a timed priority queue

Real-time programs often need a time-tagged priority queue that must be updated on the tick of a clock. A prime example of such a queue is a list of filter coefficients that must be changed on a given sample clock. A single chip that manages a time-tagged priority queue is proposed. The queue connects either to a static random access memory (SRAM) or directly to a digital signal processor (DSP) microprocessor. The SRAM would be part of the address space of a DSP microprocessor executing digital filter code     

Verifying data refinements using a model checker

In this paper, we consider how refinements between state-based specifications (e.g., written in Z) can be checked by use of a model checker. Specifically, we are interested in the verification of downward and upward simulations which are the standard approach to verifying refinements in state-based notations. We show how downward and upward simulations can be checked using existing temporal logic model checkers.In particular, we show how the branching time temporal logic CTL can be used to encode the standard simulation conditions. We do this for both a blocking, or guarded, interpretation of operations (often used when specifying reactive systems) as well as the more common non-blocking interpretation of operations used in many state-based specification languages (for modelling sequential systems). The approach is general enough to use with any state-based specification language, and we illustrate how refinements between Z specifications can be checked using the SAL CTL model checker using a small example.     

A case-study in timed refinement: a mine pump

A specification and top-level refinement of a simple mine pump control system, as well as a proof of correctness of the refinement, are presented as an example of the application of a formal method for the development of time-based systems. The overall approach makes use of a refinement calculus for timed systems, similar to the refinement calculi for sequential programs. The specification makes use of topologically continuous functions of time to describe both analog and discrete properties of both the system and its refinements. The basic building block of specifications is a specification statement that gives a clear separation between the specification of the assumptions that the system may make about the environment in which it is to be placed, and the effect the system is guaranteed to achieve if placed in such an environment. The top-level refinement of the system is developed by application of refinement laws that allow design decisions to be made, local state to be introduced, and the decomposition of systems into pipelined and/or parallel processes     

TIC: A timed calculus

TIC is a timed algebraic calculus which combines ideas from asynchronous and synchronous calculi. Time is introduced by assigning explicit time restrictions to the events of an asynchronous calculus. The semantics is defined in an operational way. Interleaving of behaviours is defined in such a way that a proper merge of events in time is achieved. Weak timed bisimulation is also defined. Examples are presented to show the applicability of the calculus to the study of timed behaviours.This work was partially supported by CICYT under the TIC program (MEDAS project)     

Cognitive-bias toward gaming-related words and disinhibition in World of Warcraft gamers

This study investigated cognitive biases toward gaming-related words and differences in cognitive performance among twelve World of Warcraft players (WWP) and thirty non-players (NP). We measured response to valenced common English and WoW jargon words using a computer-based go/no-go task. Sometimes positive valence words were the targets for the ‘go’ response, with negative-valence words as the distracters, sometimes the reverse. Target discrimination (d′) and response disinhibition (C) were calculated using a signal detection analysis. Based on questionnaire responses, there were no differences between groups in depression, anxiety, smoking or drinking, but WWP reported significantly more screen and gaming time (17.31 h/week versus 4.12 among NP). WWP had faster reaction time (RT) and better discrimination of targets from distracters (high d′) but also showed higher disinhibition (low C). WWP also showed cognitive-bias toward game-related words in the form of higher d′ for WoW jargon than common English and more disinhibition to positive-valence WoW jargon. Similar to past studies which have found alcoholics to have cognitive biases toward alcohol-related words, WWP who play frequently showed cognitive biases toward words related to the World of Warcraft game.     

Analysis of Zeno behaviors in a class of hybrid systems

This note investigates conditions for existence of Zeno behaviors (where a system undergoes an unbounded number of discrete transitions in a finite length of time) in a class of hybrid systems. Zeno behavior occurs, for example, when a controller unsuccessfully attempts to satisfy an invariance specification by switching the system among different configurations faster and faster. Two types of Zeno systems are investigated: (1) strongly Zeno systems where all runs of the system are Zeno and (2) (weakly) Zeno systems where only some runs of the system are Zeno. For constant-rate and bounded-rate hybrid systems and some nonlinear generalizations, necessary and sufficient conditions for both Zenoness and strong Zenoness are derived. The analysis is based on studying the trajectory set of a certain "equivalent" continuous-time system that is associated with the dynamic equations of the hybrid system. The relation between the possibility of existence of Zeno behaviors in a system and the problem of existence of non-Zeno safety controllers (that keep the system in a specified region of its operating space) is also examined. It is shown that in certain Zeno systems, a minimally-interventive safety controller may not exist, even if a safety controller exists, disproving a conjecture made earlier in the literature.     

Tightening the contract refinements of a system architecture

Contract-based design is an emerging paradigm for correct-by-construction hierarchical systems: components are associated with assumptions and guarantees expressed as formal properties; the architecture is analyzed by verifying that each contract of composite components is correctly refined by the contracts of its subcomponents. The approach is very efficient, because the overall correctness proof is decomposed into proofs local to each component. However, the process for the contract specification and refinement is quite expensive because the requirements are formalised into formal properties, where part of the complexity is delegated to the designer, who has the burden of specifying the contracts. Typical problems include understanding which contracts are necessary, and how they can be simplified without breaking the correctness of the refinement and other refinements in case some subcontracts are shared. In this paper, we tackle these problems by proposing a technique to understand and simplify the contract refinements of a system architecture during the development process for the contract specification and refinement. The technique, called tightening, is based on parameter synthesis. The idea is to generate a set of parametric proof obligations, where each parameter evaluation corresponds to a variant of the original(s) contract refinement(s), and to search for tighter variants of the contracts that still ensure the correctness of the refinement(s). We cast this approach in the OCRA framework, where contracts are expressed with LTL formulas, and we evaluate its performance and effectiveness on a number of benchmarks.     

The long way toward multivariate predictive control of flotation processes

Flotation processes are very complex, and after more than one hundred years of history, there are few reports on applications of novel techniques in monitoring and control of flotation units, circuits and global plants. On the other hand, the successful application of multivariate predictive control on other processes is well known. In this paper, an analysis on how the characteristics of flotation processes, the quality of measurements of key variables, and the general lack of realistic dynamic models, are delaying the appropriate use of predictive control. In this context, the applications of multivariate statistics, such as PCA, to model the relationship between operating data for on-line diagnosis and fault detection and to build causal models are discussed. Also the use of PLS models to predict target variables for control purposes, is presented. Results, obtained at pilot and industrial scales, are discussed, introducing new ideas on how to obtain more valuable information from the usual available operating data of the plant, and particularly from froth images.     

Program families: Program construction by context independent refinements

The concept of program families is a generalisation of the conventional stepwise refinement paradigm. We formalise program families by allowing Hoare-triplets to be parameterized. Next we derive a simple calculus to develop programs which are known a priori to be correct with respect to explicitly formulated pre- and postconditions.

Program families deal with at least two important problems of conventional refinement steps, i.e. program families are not context dependent and they apply just as well to top-down decomposition as to the bottom-up or middle-out approach. It turns out that the meaning of a pseudostatement in the context of program families is quite different from its meaning in the conventional refinement process.

A couple of examples illustrate the technique: the 1000 primes problem, a palindrome filter and a sorting routine.

The discussion relates program families to Morgan's refinement calculus, Knuth' literate programming and Soloway's programming plans.     

A resource allocation problem on timed marked graphs: a decomposition approach

In complex man-made environments discrete event dynamic systems are frequently encountered, and a timed marked graph is widely accepted as a convenient tool to describe systems of this kind. We consider trade-offs of cost and performance on such a system. First we formulate an optimization problem and transform it into a mixed integer linear programming problem. To improve computational efficiency, we decompose the problem into two phases. In phase one we determine the optimal number of each resource to be adopted in the system, and in phase two we optimize the distribution of these resources over the system. Phase one is solved very quickly and approximately by the dominance relaxation through a binary search procedure. This also gives the estimate of error bounds. An illustrative example shows an application to a jobshop optimization problem, and numerical experiments are carried out for some sample problems.     

Automated analysis of timed security: a case study on web privacy

This paper presents a case study on an automated analysis of real-time security models. The case study on a web system (originally proposed by Felten and Schneider) is presented that shows a timing attack on the privacy of browser users. Three different approaches are followed: LH-Timed Automata (analyzed using the model checker HyTech), finite-state automata (analyzed using the model checker NuSMV), and process algebras (analyzed using the model checker CWB-NC ). A comparative analysis of these three approaches is given.     

Testing from a stochastic timed system with a fault model

In this paper we present a method for testing a system against a non-deterministic stochastic finite state machine. As usual, we assume that the functional behaviour of the system under test (SUT) is deterministic but we allow the timing to be non-deterministic. We extend the state counting method of deriving tests, adapting it to the presence of temporal requirements represented by means of random variables. The notion of conformance is introduced using an implementation relation considering temporal aspects and the limitations imposed by a black-box framework. We propose a new group of implementation relations and an algorithm for generating a test suite that determines the conformance of a deterministic SUT with respect to a non-deterministic specification. We show how previous work on testing from stochastic systems can be encoded into the framework presented in this paper as an instantiation of our parameterized implementation relation. In this setting, we use a notion of conformance up to a given confidence level.     

Modeling a real-time multitasking system in a timed PQ net

A system is described that integrates timed Petri nets and queueing networks to model complex, real-time systems. It includes a graphical modeling tool, called TPQN, a textual specification language, called TPQL, and a simulator, called TPQS. TPQN's capabilities are illustrated by a performance analysis of a real-time, multitasking scheduler that had been previously implemented on top of SunOS on a Sun-3 workstation. A simulation package has been developed for TPQN that allows the behavior of various complicated systems under a designated queueing network topology to be studied before the system is implemented     

Generation of three-atom singlet state in a bimodal cavity via quantum Zeno dynamics

We propose an efficient scheme for generation of three-atom singlet state in a bimodal cavity based on quantum Zeno dynamics and the large detuning condition. The influence of decoherence induced by cavity decay and atomic spontaneous emission is also discussed by numerical calculation. The advantages of the scheme are that the initial input states of atoms are not entangled and the fidelity is insensitive to cavity decay and atomic spontaneous emission due to no exciting the cavity fields during the whole evolution and the large detuning condition.