On the polynomial dynamic system approach to software development

1IntroductionReactivesystemsareregardedessentialintheareaofcomputerscience[1].Quiteafewapproacheshavebeenproposedtodevelopreactivesystems,includingthestatemateapproach[2],thetemporal-logicapproach[3],thesynchronousapproach[4],amongoth-ers[5,6].Usually,thepropertiesofthereactivesoftwareunderdevelopmentarecheckedaposteriori(aftersoftwaredesignorevensoftwareimplementation)usingpropertyveri-ficationand/orsimulationtechniquessuchasthetemporal-logicapproach[7]andtheSmoochesapproach[5].However,thisi…     

增量式软件设计方法的条件

增量式设计方法是软件开发中常用的一种设计方法,但是对其进行形式化研究的并不多。论文研究用多项式动态系统方法开发软件时是否可以用增量式设计方法。首先通过一个反例说明并不是在任何情况下都可以用增量式设计方法,然后通过定义软件需求的继承性,得到增量式软件设计的一个充分条件：当已经设计的软件需求具有继承性时,可以对新的软件需求采用增量式设计。     

一种基于监控理论的软件设计方法:状态性质变换方法

基于把离散事件系统监控理论用于软件设计的思想,本文中对软件设计的状态性质变换方法作了详细的讨论,给定一个系统,其每一个状态的性质都是确定的,当提出软件需求时,常常是对系统状态的性质提出需求,为设计出满足需求的系统,可以首先按照是否满足该性质对系统状态进行分类,再对不满足该性质的状态控制其可控事件的发生从而改变其性质使之满足要求的性质。本文将这种方法用于软件需求是不变性或可达性时的软件设计问题,通过和已有文献中结论的比较,显示了这种设计思想的广泛适用性和优点,也验证了软件控制论这一思想的可行性。     

种基于监控理论的软件设计方法：状态性质变换方法

基于把离散事件系统监控理论用于软件设计的思想,本文中对软件设计的状态性质变换方法作了详细的讨论. 给定一个系统,其每一个状态的性质都是确定的. 当提出软件需求时,常常是对系统状态的性质提出需求.为设计出满足需求的系统,可以首先按照是否满足该性质对系统状态进行分类,再对不满足该性质的状态控制其可控事件的发生从而改变其性质使之满足要求的性质.本文将这种方法用于软件需求是不变性或可达性时的软件设计问题,通过和已有文献中结论的比较,显示了这种设计思想的广泛适用性和优点,也验证了软件控制论这一思想的可行性.     

A temporal logic approach to discrete event control for the safety canonical class

This paper presents a temporal logic formulation of discrete event control which forms a new theoretical basis for control analysis and synthesis of a class of discrete event systems (DES). Based on the formulation, a basic supervisory control theory is developed for a control objective specified by an invariance formula belonging to the safety canonical class of Manna and Pneuli. Using the safety canonical class as a basis, the refinement and generalization of the existing basic predicate framework are demonstrated. A simple example illustrates the formal axiomatic means to perform control-theoretic analysis and synthesis under the new formulation.     

On commoner's liveness theorem and supervisory policies that enforce liveness in free-choice Petri nets

A Petri net (PN) (Peterson, 1981; Reisig, 1985) is said to be live if it is possible to fire any transition from every reachable marking, although not necessarily immediately. A free-choice Petri net FCPN) is a PN, where every arch from a place to a transition is either the unique output arc from that place or it is the unique input arc to the transition. Commoner's Liveness Theorem (cf. Hack, 1972, Ch. 4; Reisig, 1985, Section 7.2) states that a FCPN is live if and only if every siphon contains a marked trap at the initial marking. A siphon (trap) is a collection of places P such that . We concern ourselves with marking-dependent supervisory policies that can prevent the firing of a transition. We characterize supervisory policies that enforce liveness in non-live FCPNs using observations that strongly parallel Commoner's Liveness Theorem. We use this characterization to establish the existence of supervisory policies that enforce liveness in a Class of FCPNs called independent, increasing free-choice petri nets (II-FCPNs).     

Bisimilarity enforcing supervisory control for deterministic specifications

This paper studies the supervisory control of nondeterministic discrete event systems to achieve a bisimulation equivalence between the controlled system and the deterministic specification. In particular, a necessary and sufficient condition is given for the existence of a bisimilarity enforcing supervisor, and a polynomial algorithm is developed to verify such a condition. When the existence condition holds, a bisimilarity enforcing supervisor is constructed. Otherwise, two methods are provided for synthesizing supremal feasible sub-specifications.     

Ontology-based modeling of dynamic ubiquitous computing applications as evolving activity spheres

As the computer disappears in the environments surrounding our activities, the objects therein become augmented with sensors, actuators, processors, memories, wireless communication modules and they can receive, store, process and transmit information. In addition to objects, spaces also undergo a change towards becoming smart and eventually Ambient Intelligence (AmI) spaces. In order to model the way everyday activities are carried out within an AmI environment, we introduce the notion of “activity sphere”. In this paper, we are interested in the ontology-based representation of activity spheres from two different perspectives (as creators and as observers), as well as the modeling and control of the dynamic nature of activity spheres.     

An implementation method for the supervisory control of time-driven systems applied to high-voltage direct current transmission grids

In recent years, the growth of renewable energy production has encouraged the development of new technologies, such as High-Voltage Direct Current (HVDC) networks, that enhance the integration of such energy sources to power transmission grids. However, this type of technology introduces new challenges in the way power transmission systems are controlled and operated, as faster and more complex control strategies will be needed in a domain which nowadays relies heavily on human decisions. In this context, Discrete Event Systems (DES) modeling and Supervisory Control Theory (SCT) are powerful tools for the development of a supervisory control to be deployed in the grid. This paper presents an application of the SCT to HVDC grids and proposes an implementation method for the resulting supervisors. The proposed method is capable of integrating decentralized and discrete-event controllers that interact with the continuous-time physical system. The language chosen for the implementation is C code, as it can be easily incorporated in power system simulation software, such as EMTP-RV. The method is validated by the simulation of the start-up of a point-to-point link in the EMTP-RV software.     

Optimal sensor activation for diagnosing discrete event systems

The problem of dynamic sensor activation for event diagnosis in partially observed discrete event systems is considered. Diagnostic agents are able to activate sensors dynamically during the evolution of the system. Sensor activation policies for diagnostic agents are functions that determine which sensors are to be activated after the occurrence of a trace of events. The sensor activation policy must satisfy the property of diagnosability of centralized systems or codiagnosability of decentralized systems. A policy is said to be minimal if there is no other policy, with strictly less sensor activation, that achieves diagnosability or codiagnosability. To compute minimal policies, we propose language partition methods that lead to efficient computational algorithms. Specifically, we define “window-based” language partitions for scalable algorithms to compute minimal policies. By refining partitions, one is able to refine the solution space over which minimal solutions are computed at the expense of more computation. Thus a compromise can be achieved between fineness of solution and complexity of computation.     

Petri网上的禁止状态监控器综合

给出了Petri网上广义互斥约束的最大允许监控器综合方法,其中该监控问题满足两个条件：正权值禁止库所的影响子网是状态机;负权值禁止库所的输入和输出变迁均只有一个输入库所.首先得到了监控器存在的充分和必要条件;其次构造了约束等价转换的方法,该方法可将存在不可控变迁的监控问题简化为相当于变迁全部可控的监控问题.最后通过一个例子说明了该方法的可行性.     

A graph theoretic approach to multivariable control system design

A graph theoretic approach is described for the design of multivariable control for large systems as an alternative to geometric methods. An example is given f⊙r a distillation column to demonstrate the technique, with a particular reference to aspects of disturbance rejection and the possibilities for pole assignment.     

The synthesis and PLC implementation of hybrid modular supervisors for real time control of an experimental manufacturing system

In this paper, synthesis and PLC based implementation of hybrid modular supervisors for real time supervisory control of an experimental manufacturing system are proposed. The hybrid approach couples Ramadge–Wonham (RW) supervisors in the form of automata to uncontrolled PN models through inhibitor arcs. The RW supervisors can be obtained in monolithic or modular forms. In the monolithic case, there is only a single supervisor that has complex structure and huge number of states and events. The modularity of supervisors provides simple and small control structures compared to monolithic ones. Modular hybrid approach offers fewer states for the PLC implementation of the hybrid controller with less memory requirements. The applicability and effectiveness of the modular hybrid approach are demonstrated by the PLC based real-time control of an experimental manufacturing system for different cases. The obtained results show that modular supervisors require less memory space compared to monolithic counterparts.     

Maximally permissive mutually and globally nonblocking supervision with application to switching control

A supervisor is said to be mutually nonblocking with respect to a pair of specifications if upon completing a task in any of the specifications, it can continue on to complete the task in the other specification, i.e., the two specifications do not block each other. The notion of mutually nonblocking supervisor was introduced in Fabian and Kumar [2000. Automatica, 36(12), 1863-1869]. In this paper, we present an algorithm of polynomial complexity for computing a maximally permissive mutually and globally nonblocking supervisor. In case such a supervisor does not exist, we present a technique for relaxing the specifications for which a supervisor exists. The algorithms are based on a notion of attractability, and as a special case offer a new way of computing the maximally permissive nonblocking supervisors. The results are then applied to design of maximally permissive switching supervisors so as to allow for switching between the specifications at any time while the system is executing.     

A composite complexity approach for software defect modelling

An approach is proposed to develop defect models for software components based on a categorical multivariate regression analysis. This modelling technique is useful when the software components are sufficiently small so that the assumption of a continuous normally distributed defect distribution is not valid. Library unit aggregations from five Ada projects are analysed to yield a composite complexity measure which is a function of both software complexity characteristics and development environment characteristics. The probabilities of various numbers of defects are derived from this composite complexity measure. The probability distributions are used to calculate subsystem level defects which are then compared to the actual defects.     

多总线控制系统通用化通信程序框架设计

对应用于控制系统的通用化通信软件的设计方法进行了研究,通过监听任务下移及监听信息上传的技术方法实现了信息监听功能的通用化设计;通过设计通信路径表的方法实现了数据交互的通用性。此处的通信是指控制系统中各软硬件模块的数据交互;通用化特性体现在,这种通信程序可以应用在任何多总线控制系统中,达到一次设计、多个系统使用的目的,便于控制系统的升级。     

An algebraic approach to supervisory control

Supervisory control problems are formulated in terms of a process model where the mechanism of control is expressed in terms of an algebraic operator with the plant and supervision processes as its arguments. The solution subspaces for supervisory processes restrict the observation and the control capability of supervision. The main result corresponds to decentralized marked supervision under partial observations, and specific cases are derived from this result in a unified, algebraic way. The result and its derivation demonstrate the relative simplicity of the algebraic process formulation.     

An Efficient Modular Method for the Control of Concurrent Discrete Event Systems: A Language-based Approach

In this paper, we are interested in the control of a particular class of Concurrent Discrete Event Systems defined by a collection of components that interact with each other. We investigate the computation of the supremal controllable language contained in the language of the specification. We do not adopt the decentralized approach. Instead, we have chosen to use a modular centralized approach and to perform the control on some approximations of the plant derived from the behavior of each component. The behavior of these approximations is restricted so that they respect a new language property for discrete event systems called partial controllability condition that depends on the specification. It is shown that, under some assumptions, the intersection of these “controlled approximations” corresponds to the supremal controllable language contained in the specification with respect to the plant. This computation is performed without having to build the whole plant, hence avoiding the state space explosion induced by the concurrent nature of the plant. It is finally shown that the class of specifications on which our method can be applied strictly subsumes the class of separable specifications.

Integrated design of optimal supervisors for the enforcement of static and behavioral specifications in Petri net models

Petri net (PN) supervisory control is often performed through a sequential procedure that introduces additional constraint layers over an initial unconstrained PN model, using generalized mutual exclusion constraints (GMECs) implemented as monitor places. This is typical, e.g., in the context of flexible manufacturing systems, where the initial model represents the production sequences and the constraints are used to express static specifications, such as job limitations or the usage of resources, and behavioral ones, as liveness, controllability, etc. This sequential procedure may yield a redundant model, that is not easily reduced a posteriori. Also, it is difficult to ensure maximal permissivity with respect to multiple behavioral specifications. This paper, building on recent results regarding optimal supervisor design with branch & bound methods, proposes an integrated modeling approach that can be used to derive a minimal supervisor guaranteeing the attainment of an arbitrary set of static and behavioral specifications in a maximally permissive way. Among behavioral specifications, deadlock-freeness, liveness, reversibility and behavioral controllability are considered in the paper. The supervisor comes in the form of a simple set of GMECs or of a disjunction of sets of GMECs. Some examples emphasize the potential model size reductions that can be achieved.     

An algorithm for calculating indistinguishable states and clusters in finite-state automata with partially observable transitions

This paper presents a new algorithm for efficiently calculating pairs of indistinguishable states in finite-state automata with partially observable transitions. The need to obtain pairs of indistinguishable states occurs in several classes of problems related to control under partial observation, diagnosis, or distributed control with communication for discrete event systems. The algorithm obtains all indistinguishable state pairs in polynomial time in the number of states and events in the system. Another feature of the algorithm is the grouping of states into clusters and the identification of indistinguishable cluster pairs. Clusters can be employed to solve control problems for partially observed systems.