Synthesizing advanced transaction models using the situation calculus

The situation calculus is a versatile logic for reasoning about actions and formalizing dynamic domains. Using the non-Markovian action theories formulated in the situation calculus, one can specify and reason about the effects of database actions under the constraints of the classical, flat database transactions, which constitute the state of the art in database systems. Classical transactions are characterized by the so-called ACID properties. With non-Markovian action theories, one can also specify, reason about, and even synthesize various extensions of the flat transaction model, generally called advanced transaction models (ATMs). In this paper, we show how to use non-Markovian theories of the situation calculus to specify and reason about the properties of ATMs. In these theories, one may refer to past states other than the previous one. ATMs are expressed as such non-Markovian theories using the situation calculus. We illustrate our method by specifying (and sometimes reasoning about the properties of) several classical models and known ATMs.     

A categorical framework for typing CCS-style process communication

Category theory has proved a useful tool in the study of type systems for sequential programming languages. Various approaches have been proposed to use categorical models to examine the type structures appropriate to concurrent systems. In this paper, we outline some of these approaches, such as interaction categories, and argue that they are not appropriate to model the handshake communication mechanism as used e.g. in CCS or the π-calculus. We propose an alternative general categorical framework for examining the type structure of such systems, and exhibit its categorical structure, which is similar to that of existing approaches. We then examine in detail an instance of this framework, based on a simple fragment of CCS. We prove that it is isomorphic to a syntactic category constructed from a process algebra similar to CCS, with a fusion operator, as in the fusion calculus. Thus, we make explicit some of the type structure implicitly present in such a process algebra.     

Language-Theoretic and Finite Relation Models for the (Full) Lambek Calculus

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus \({\mathbf {FL}}_\perp \). We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents (henceforth: \(\mathbf L \) and \(\mathbf L1 \)), thus solving a problem left open by Pentus (Ann Pure Appl Log 75:179–213, 1995).     

Behavioural equivalence in simulation modelling

Discrete event simulation has grown up as a practical technique for estimating the quantitative behaviour of systems, where direct measurement is undesirable or impractical. It is also used to understand the detailed functional behaviour of such systems. Its theory is largely that of experimental science, centering on statistical approaches to validation, rather than on the verification of detailed behaviour. On the other hand, much work has been done on understanding and proving functional properties of systems, using techniques of formal specification and concurrency modelling. This article presents an approach to understanding equivalence of behaviour of discrete event simulation models, using a technique from the concurrency world, Milner’s Calculus of Communicating Systems (CCS). This yields a significant advance over the main previous work, Schruben and Yücesan’s simulation graphs. CCS allows for the use of observational equivalence, which can capture a more flexible, behavioural notion of equivalence than the structural equivalence defined there.A common framework based on the process view of models is constructed, using a hierarchical graphical modelling language (Extended Activity Diagrams). This language is shown to map onto both the major constructs of the DEMOS discrete event simulation language and the corresponding CCS models. A graphically driven tool based on such a framework is presented, which generates both types of models. Using the CCS model, behavioural equivalences and differences in simulation models are demonstrated.     

Inductive situation calculus

Temporal reasoning has always been a major test case for knowledge representation formalisms. In this paper, we develop an inductive variant of the situation calculus in ID-logic, classical logic extended with inductive definitions. This logic has been proposed recently and is an extension of classical logic. It allows for a uniform representation of various forms of definitions, including monotone inductive definitions and non-monotone forms of inductive definitions such as iterated induction and induction over well-founded posets. We show that the role of such complex forms of definitions is not limited to mathematics but extends to commonsense knowledge representation. In the ID-logic axiomatization of the situation calculus, fluents and causality predicates are defined by simultaneous induction on the well-founded poset of situations. The inductive approach allows us to solve the ramification problem for the situation calculus in a uniform and modular way. Our solution is among the most general solutions for the ramification problem in the situation calculus. Using previously developed modularity techniques, we show that the basic variant of the inductive situation calculus without ramification rules is equivalent to Reiter-style situation calculus.     

Exploiting symmetry in the synthesis of supervisors for discreteevent systems

We investigate a method to exploit the symmetry inherent to many discrete-event systems in order to reduce the computational complexity of the supervisory control problem (SCP). We characterize symmetry using notions of group theory and derive conditions under which there exists a quotient (reduced) automaton representation for a language with, in general, a much smaller state space than the original minimal (in number of states) automaton representation for the language. We then propose an algorithm to synthesize a solution to the SCP which is similar to the classical one, but performed on reduced automata. Special attention is given to the particular case of systems whose models contain similar components. The approach is illustrated by an example of control of a small production line     

A power-set construction for reducing Büchi automata to non-determinism degree two

Büchi automata are finite automata that accept languages of infinitely long strings, so-called ω-languages. It is well known that, unlike in the finite-string case, deterministic and non-deterministic Büchi automata accept different ω-language classes, i.e., that determination of a non-deterministic Büchi automaton using the classical power-set construction will yield in general a deterministic Büchi automaton which accepts a superset of the ω-language accepted by the given non-deterministic automaton.In this paper, a power-set construction to a given Büchi automaton is presented, which reduces the degree of non-determinism of the automaton to at most two, meaning that to each state and input symbol, there exist at most two distinct successor states. The constructed Büchi automaton of non-determinism degree two and the given Büchi automaton of arbitrary non-determinism degree will accept the same ω-language.     

L2–L∞ fuzzy control for Markov jump systems with neutral time-delays

The L₂–L_∞ fuzzy control problem is considered for nonlinear stochastic Markov jump systems with neutral time-delays. By means of Takagi–Sugeno fuzzy models, the fuzzy controller systems and the overall closed-loop fuzzy dynamics are constructed. A sufficient condition is firstly established on the stochastic stability using stochastic Lyapunov–Krasovskii functional. Then in terms of linear matrix inequalities techniques, the sufficient conditions on the existence of mode-dependent state feedback L₂–L_∞ fuzzy controller are presented and proved respectively for constant and time varying case. Finally, the design problems are formulated as optimization algorithms. Simulation results are exploited to illustrate the effectiveness of the developed techniques.     

Special factors and the combinatorics of suffix and factor automata

The suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages L_SA and L_FA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.     

Synthesis of optimal discrete automaton-type systems in the case of multiple instantaneous switchings

A discrete system that models the operation of a dynamic finite state machine (automaton) with memory is considered. In distinction from the classical model of discrete time system, in which the states are changed (switched) at prescribed instants of time, automaton-type systems may change their states at arbitrary instants. Moreover, multiple instantaneous switchings are allowed. Furthermore, the choice of the instants when the automaton “fires” and the number of switchings at these instants are considered as control resources, and they are subject to optimization. Sufficient optimality conditions for such systems are proved. Equations for the optimal open-loop control and for the value (Bellman) function are derived. A method for the synthesis of the optimal control is proposed based on the construction of the value function as the lower envelope of a family of auxiliary functions (generators). Application of the proposed method is illustrated by examples.     

State-oriented Noninterference for CCS

We address the question of typing noninterference (NI) in the calculus CCS, in such a way that Milner's translation into CCS of a standard parallel imperative language preserves both an existing NI property and the associated type system. Recently, Focardi, Rossi and Sabelfeld have shown that a variant of Milner's translation, restricted to the sequential fragment of the language, maps a time-sensitive NI property to that of Persistent Bisimulation-based Non Deducibility on Compositions (PBNDC) on CCS. However, since CCS was not equipped with a type system, the question of whether the translation preserves types could not be addressed. We extend Focardi, Rossi and Sabelfeld's result by showing that a slightly simpler variant of Milner's translation preserves a time-insensitive NI property on the full parallel language, by mapping it again to PBNDC. As a by-product, we formalise a folklore result, namely that Milner's translation preserves a behavioural equivalence on programs. We present a simple type system ensuring PBNDC on CCS, inspired by existing type systems for the π-calculus. Unfortunately, this type system as it stands is too restrictive to grant the expected type preservation result. We sketch a solution to overcome this problem.     

A Calculus and logic of resources and processes

Recent advances in logics for reasoning about resources provide a new approach to compositional reasoning in interacting systems. We present a calculus of resources and processes, based on a development of Milner’s synchronous calculus of communication systems, SCCS, that uses an explicit model of resource. Our calculus models the co-evolution of resources and processes with synchronization constrained by the availability of resources. We provide a logical characterization, analogous to Hennessy–Milner logic’s characterization of bisimulation in CCS, of bisimulation between resource processes which is compositional in the concurrent and local structure of systems. An erratum to this article can be found at     

Two-way unary automata versus logarithmic space

We show that if L=NL (the classical logarithmic space classes), then each unary 2nfa (a two-way nondeterministic finite automaton) can be converted into an equivalent 2dfa (a deterministic two-way automaton), keeping the number of states polynomial. (Unlike other results of this kind, here the deterministic simulation is valid for inputs of all lengths, not only polynomially long ones.) This shows a connection between the standard logarithmic space complexity and the state complexity of two-way unary automata: it indicates that L could be separated from NL by proving a superpolynomial gap, in the number of states, for the conversion from unary 2nfas to 2dfa. Moreover, without any unproven assumptions, we show that each n-state unary 2nfa can be simulated by an equivalent 2ufa (an unambiguous 2nfa) with a polynomial number of states.     

Timed Wp-method: testing real-time systems

Real-time systems interact with their environment using time constrained input/output signals. Examples of real-time systems include patient monitoring systems, air traffic control systems, and telecommunication systems. For such systems, a functional misbehavior or a deviation from the specified time constraints may have catastrophic consequences. Therefore, ensuring the correctness of real-time systems becomes necessary. Two different techniques are usually used to cope with the correctness of a software system prior to its deployment, namely, verification and testing. In this paper, we address the issue of testing real-time software systems specified as a timed input output automaton (TIOA). TIOA is a variant of timed automaton. We introduce the syntax and semantics of TIOA. We present the potential faults that can be encountered in a timed system implementation. We study these different faults based on TIOA model and look at their effects on the execution of the system using the region graph. We present a method for generating timed test cases. This method is based on a state characterization technique and consists of the following three steps: First, we sample the region graph using a suitable granularity, in order to construct a subautomaton easily testable, called grid automaton. Then, we transform the grid automaton into a nondeterministic timed finite state machine (NTFSM). Finally, we adapt the generalized Wp-method to generate timed test cases from NTFSM. We assess the fault coverage of our test cases generation method and prove its ability to detect all the possible faults. Throughout the paper, we use examples to illustrate the various concepts and techniques used in our approach.     

Inclusion dynamics hybrid automata

Hybrid systems are dynamical systems with the ability to describe mixed discrete-continuous evolution of a wide range of systems. Consequently, at first glance, hybrid systems appear powerful but recalcitrant, neither yielding to analysis and reasoning through a purely continuous-time modeling as with systems of differential equations, nor open to inferential processes commonly used for discrete state-transition systems such as finite state automata. A convenient and popular model, called hybrid automata, was introduced to model them and has spurred much interest on its tractability as a tool for inference and model checking in a general setting. Intuitively, a hybrid automaton is simply a “finite-state” automaton with each state augmented by continuous variables, which evolve according to a set of well-defined continuous laws, each specified separately for each state. This article investigates both the notion of hybrid automaton and the model checking problem over such a structure. In particular, it relates first-order theories and analysis results on multivalued maps and reduces the bounded reachability problem for hybrid automata whose continuous laws are expressed by inclusions (x′f(x,t)) to a decidability problem for first-order formulæ over the reals. Furthermore, the paper introduces a class of hybrid automata for which the reachability problem can be decided and shows that the problem of deciding whether a hybrid automaton belongs to this class can be again decided using first-order formulæ over the reals. Despite the fact that the bisimulation quotient for this class of hybrid automata can be infinite, we show that our techniques permit effective model checking for a nontrivial fragment of CTL.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

The Saga of Synchronous Bus Arbiter: On Model Checking Quantitative Timing Properties of Synchronous Programs

Quantified Discrete-time Duration Calculus, (QDDC), is a form of interval temporal logic [14]. It is well suited to specify quantitative timing properties of synchronous systems. An automata theoretic decision procedure for QDDC allows converting a QDDC formula into a finite state automaton recognising precisely the models of the formula. The automaton can be used as a synchronous observer for model checking the property of a synchronous program. This theory has been implemented into a tool called DCVALID which permits model checking QDDC properties of synchronous programs written in Esterel, Verilog and SMV notations.In this paper, we consider two well-known synchronous bus arbiter circuits (programs) from the literature. We specify some complex quantitative properties of these arbiters, including their response time and loss time, using QDDC. We show how the tool DCVALID can be used to effectively model check these properties (with some surprising results).     

CSP is a retract of CCS

Automata theory provides two ways of defining an automaton: either by its transition system, defining its states and events, or by its language, the set of sequences (traces) of events in which it can engage. For many classes of automaton, these forms of definition have been proved equivalent. For example, there is a well-known isomorphism between regular languages and finite deterministic automata. This paper suggests that for (demonically) the non-deterministic automata (as treated in process algebra), the appropriate link between transition systems and languages may be a retraction rather than an isomorphism.A pair of automata, defined in the tradition of CCS by their transition systems, may be compared by a pre-ordering based on some kind of simulation or bisimulation, for example, weak, strong, or barbed. Automata defined in the tradition of CSP are naturally ordered by set inclusion of their languages (often called refinement); variations in ordering arise from different choices of basic event, including for example, refusals and divergences. In both cases, we characterise a theory by its underlying transition system and its choice of ordering. Our treatment is therefore wholly semantic, independent of the syntax and definition of operators of the calculus.We put forward a series of retractions relating the above-mentioned versions of CSP to their corresponding CCS transition models. A retraction is an injection that is (with respect to the chosen ordering) monotonic, increasing and idempotent (up to equivalence). It maps the nodes of a transition system of its source theory to those of a system that has been saturated by additional transitions. Each retraction will be defined by a transition rule, in the style of operational semantics; the proofs use the familiar technique of co-induction, often abbreviated by encoding in the relational calculus.The aim of this paper is to contribute to unification of theories of reactive system programming. More practical benefits may follow. For example, we justify a method to improve the efficiency of model checking based on simulation. Furthermore, we show how model checking of a transition network fits consistently with theorem-proving tools, which reason directly about specifications and designs that are expressed in terms of sets of sequences of observable events.     

Generic properties and control of linear structured systems: a survey

In this survey paper, we consider linear structured systems in state space form, where a linear system is structured when each entry of its matrices, like A,B,C and D, is either a fixed zero or a free parameter. The location of the fixed zeros in these matrices constitutes the structure of the system. Indeed a lot of man-made physical systems which admit a linear model are structured. A structured system is representative of a class of linear systems in the usual sense. It is of interest to investigate properties of structured systems which are true for almost any value of the free parameters, therefore also called generic properties. Interestingly, a lot of classical properties of linear systems can be studied in terms of genericity. Moreover, these generic properties can, in general, be checked by means of directed graphs that can be associated to a structured system in a natural way. We review here a number of results concerning generic properties of structured systems expressed in graph theoretic terms. By properties we mean here system-specific properties like controllability, the finite and infinite zero structure, and so on, as well as, solvability issues of certain classical control problems like disturbance rejection, input-output decoupling, and so on. In this paper, we do not try to be exhaustive but instead, by a selection of results, we would like to motivate the reader to appreciate what we consider as a wonderful modelling and analysis tool. We emphasize the fact that this modelling technique allows us to get a number of important results based on poor information on the system only. Moreover, the graph theoretic conditions are intuitive and are easy to check by hand for small systems and by means of well-known polynomially bounded combinatorial techniques for larger systems.     

Towards scalable synthesis of stochastic control systems

Formal synthesis approaches over stochastic systems have received significant attention in the past few years, in view of their ability to provide provably correct controllers for complex logical specifications in an automated fashion. Examples of complex specifications include properties expressed as formulae in linear temporal logic (LTL) or as automata on infinite strings. A general methodology to synthesize controllers for such properties resorts to symbolic models of the given stochastic systems. Symbolic models are finite abstractions of the given concrete systems with the property that a controller designed on the abstraction can be refined (or implemented) into a controller on the original system. Although the recent development of techniques for the construction of symbolic models has been quite encouraging, the general goal of formal synthesis over stochastic control systems is by no means solved. A fundamental issue with the existing techniques is the known “curse of dimensionality,” which is due to the need to discretize state and input sets. Such discretization generally results in an exponential complexity over the number of state and input variables in the concrete system. In this work we propose a novel abstraction technique for incrementally stable stochastic control systems, which does not require state-space discretization but only input set discretization, and that can be potentially more efficient (and thus scalable) than existing approaches. We elucidate the effectiveness of the proposed approach by synthesizing a schedule for the coordination of two traffic lights under some safety and fairness requirements for a road traffic model. Further we argue that this 5-dimensional linear stochastic control system cannot be studied with existing approaches based on state-space discretization due to the very large number of generated discrete states.