On the role of complementation in implicit language equations and relations

We solve systems of boolean implicit equations and relations with union and complementation. If the languages are regular, we determine whether a system of implicit boolean equations or relations has solutions. If there is a solution, we provide an effective construction of a (regular) solution. We give representations for maximal and minimal solutions. Moreover, we also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.     

Modelling and control of discrete event systems using switching max-plus-linear systems

In this paper we consider the modelling and control of discrete event systems using switching max-plus-linear systems. In switching max-plus-linear systems we can switch between different modes of operation. In each mode the discrete event system is described by a max-plus-linear state space model with different system matrices for each mode. The switching allows us to change the structure of the system, to break synchronization and to change the order of events. We will give some examples of this type of systems.We define the model predictive control design problem for this type of discrete event system, and we show that solving this problem in general leads to a mixed integer optimization problem.     

A nonfragile controller for suppressing exogenous disturbances

We suggest an approach to the problem of building a nonfragile controller, i.e., one that would allow for variation in its parameters, in order to suppress bounded exogenous disturbances in a linear dynamic system. We consider both continuous and discrete version of the problem and also its robust version. As an example, we study the control problem for a double oscillator.     

Input signal design for identification of max-plus-linear systems

Max-plus-linear systems efficiently describe the dynamics of event time sequences of a class of discrete event systems. The present contribution addresses the problem of designing adequate input signals for state space identification of max-plus-linear systems. It is shown that the input signal design problem can be rewritten as a set of upper bound constraints and therefore solved using an existing algorithm. This input signal design method allows to incorporate additional objectives and constraints, e.g. minimum or maximum input event separation, time order constraints, etc., which are desirable or even required for the input signals and the resulting process behavior.     

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.     

Truss topology optimization with discrete design variables—Guaranteed global optimality and benchmark examples

This paper considers the problem of optimal truss topology design subject to multiple loading conditions. We minimize a weighted average of the compliances subject to a volume constraint. Based on the ground structure approach, the cross-sectional areas are chosen as the design variables. While this problem is well-studied for continuous bar areas, we consider in this study the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single available bar area, i.e., a 0/1 problem. In contrast to the heuristic methods considered in many other approaches, our goal is to compute guaranteed globally optimal structures. This is done by a branch-and-bound method for which convergence can be proven. In this branch-and-bound framework, lower bounds of the optimal objective function values are calculated by treating a sequence of continuous but non-convex relaxations of the original mixed-integer problem. The main effect of using this approach lies in the fact that these relaxed problems can be equivalently reformulated as convex problems and, thus, can be solved to global optimality. In addition, these convex problems can be further relaxed to quadratic programs for which very efficient numerical solution procedures exist. By exploiting this special problem structure, much larger problem instances can be solved to global optimality compared to similar mixed-integer problems. The main intention of this paper is to provide optimal solutions for single and multiple load benchmark examples, which can be used for testing and validating other methods or heuristics for the treatment of this discrete topology design problem.     

Quadratic optimal control of stable systems through spectral factorization

We consider the infinite horizon quadratic cost minimization problem for a linear system with finitely many inputs and outputs. A common approach to treat a problem of this type is to construct a semigroup in an abstract state space, and to use infinite-dimensional control theory. However, this approach is less appealing in the case where there are discrete time delays in the impulse response, because such time delays force both the control operator and the observation operator to be unbounded at the same time. In order to be able to include this case we take an alternative approach. We work in an input-output framework, and reduce the problem to a symmetric Wiener-Hopf problem, that can be solved by means of a canonical factorization of the symbol. In a standard shift semigroup realization this amounts to factorizations of the Riccati operator and the feedback operator into convolution operators and projections. Our approach leads to a new significant discovery: in the case where the impulse response of the system contains discrete time delays, the standard Riccati equation is incorrect; to get the correct Riccati equation the feed-through matrix of the system must be partially replaced by the feed-through matrix of the spectral factor. This means that, before it is even possible to write down the correct Riccati equation, a spectral factorization problem must first be solved to find one of the weighting matrices in this equation.     

A High Accuracy Post-processing Algorithm for the Eigenvalues of Elliptic Operators

In a very recent paper (Hu et al., The lower bounds for eigenvalues of elliptic operators by nonconforming finite element methods, Preprint, 2010), we prove that the eigenvalues by the nonconforming finite element methods are smaller than the exact ones for the elliptic operators. It is well-known that the conforming finite element methods produce the eigenvalues above to the exact ones. In this paper, we combine these two aspects and derive a new post-processing algorithm to approximate the eigenvalues of elliptic operators. We implement this algorithm and find that it actually yields very high accuracy approximation on very coarser mesh. The numerical results demonstrate that the high accuracy herein is of two fold: the much higher accuracy approximation on the very coarser mesh and the much higher convergence rate than a single lower/upper bound approximation. Moreover, we propose some acceleration technique for the algorithm of the discrete eigenvalue problem based on the solution of the discrete eigenvalue problem which yields the upper bound of the eigenvalue. With this acceleration technique we only need several iterations (two iterations in our example) to find the numerical solution of the discrete eigenvalue problem which produces the lower bound of the eigenvalue. Therefore we only need to solve essentially one discrete eigenvalue problem.     

Classical necessary optimality conditions in discrete optimal control problems with nonlocal conditions

We consider an optimal control problem in which the system’s state is described by a system of difference equations with nonlocal (two-point) conditions; this problem includes, as particular cases, the initial value problem (Cauchy problem) and different types of boundary value problems. It is assumed that the admissible controls take values from an open set. The first and second functional variations are calculated; these variations are used to express first and second order necessary optimality conditions in the classical sense for discrete optimal control problems.     

Cost functors and optimal realization

We provide a general theory of optimal realization, generalizing the minimal realization construction of automata theory. We use a categorical framework to capture general classes of deterministic and nondeterministic realization problems. We define cost functors over a category of systems relative to which optimal realizations are defined. Finally, in order to approach the generalized minimal realization problem of nondeterministic automata, we propose a quotient category of these automata which fulfills the generalized minimal realization principle.     

Control of large scale discrete event systems: Task allocation and coordination

To control a large scale discrete event system, decentralized control and hierarchical control can be used, where several local supervisors are used to control events in local sites and a coordinator is used to coordinate the local supervisors. Two important problems that need to be solved in such a control architecture are task allocation and coordination. That is, how to allocate tasks to the supervisors, and how to coordinate those tasks. We propose and solve a task allocation problem of assigning tasks to the local supervisors and a minimal intervention problem of coordinating tasks so that the intervention by the coordinator is minimal.     

Order Bound for the Realization of a Combination of Positive Filters

In a problem on the realization of digital filters, initiated by Gersho and Gopinath, we extend and complete a remarkable result of Benvenuti, Farina and Anderson on decomposing the transfer function t(z) of an arbitrary linear, asymptotically stable, discrete, time-invariant single-input-single-output system as a difference t(z)=t₁(z)-t₂(z) of two positive, asymptotically stable linear systems. We give an easy-to-compute algorithm to handle the general problem, in particular, also the case of transfer functions t(z) with multiple poles, which was left open in a previous paper. One of the appearing positive, asymptotically stable systems is always one-dimensional, while the other has dimension depending on the order and, in the case of nonreal poles, also on the location of the poles of t(z). The appearing dimension is seen to be minimal in some cases and it can always be calculated before carrying out the realization     

Trace- and failure-based semantics for responsiveness

We study open systems modeled as Petri nets with an interface for asynchronous (i.e., buffered) communication with other open systems. As a minimal requirement for successful communication, we investigate responsiveness, which guarantees that an open system and its environment always have the possibility to communicate. We investigate responsiveness with and without final states and also their respective bounded variants, where the number of pending messages never exceeds a previously known bound. Responsiveness accordance describes when one open system can be safely replaced by another open system. We present a trace-based characterization for each accordance variant. As none of the relations turns out to be compositional (i.e., it is no precongruence), we characterize the coarsest compositional relation (i.e., the coarsest precongruence) that is contained in each relation, using a variation of should testing. For the two unbounded variants, the precongruences are not decidable, but for the two bounded variants we show decidability.     

An Improved Randomized On-Line Algorithm for a Weighted Interval Selection Problem

Given a set of weighted intervals, the objective of the weighted interval selection problem (WISP) is to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider on-line algorithms that process the intervals in order of non-decreasing left endpoints. Preemption is allowed, but rejections are irrevocable. This problem has natural applications in various scheduling problems. We study the class of monotone instances of WISP, i.e., we require that the order of right endpoints of the given intervals coincides with that of the left endpoints. This class includes the case where all intervals have the same length. For monotone instances of WISP, the best possible competitive ratio for deterministic on-line algorithms is known to be 1/4. It has long been an open question whether there exists a randomized algorithm with better competitive ratio. In this paper, we present a new randomized algorithm and prove that it achieves a better competitive ratio 1/3 for the special case of monotone WISP where the sequence of weights of the arriving intervals is non-decreasing. Thus we provide the first result towards a solution of the long-standing open question. Furthermore, we show that no randomized algorithm achieves a competitive ratio strictly larger than 4/5. This is the first non-trivial upper bound for randomized algorithms for monotone WISP.     

Deterministic optimizational problems of transportation logistics

We give a survey of a wide class of transportation logistics problems, in which we consider, from a unified standpoint, both discrete (e.g., routing) and continuous (e.g., classical transport) problems. We single out a collection of elementary premises that underlie such problems, give corresponding mathematical models and approaches to the solution. We also consider a new multinomenclature transportation logistics problem.     

REALIZATION THEORY OF DISCRETE-EVENT SYSTEMS AND ITS APPLICATION TO THE UNIQUENESS AND UNIVERSALITY OF DEVS FORMALISM

Many man-made systems have discrete event nature. Many modeling formalisms for discrete-event mechanisms have invented and been used for many problems. Among those models, the DEVS formalism is to provide natural and universal models in some sense.

This paper first provides a realization theory of general discrete-event systems. That is, a behavioral definition of discrete-event system is defined, and then a state transition function of the system is constructed. Based on the realization, the uniqueness problem of representations for discrete-event systems is positively solved. Furthermore, as an application of that solution, this paper shows both the fact that a legitimate DEVS with surjective internal transition function is unique up to isomorphism in the class of state representations of the state system defined from the DEVS, and the fact that any discrete-event system has a DEVS realization. In this sense the DEVS modeling facility has the uniqueness and universality in modeling discrete event mechanisms.     

Euclidean Ordering via Chamfer Distance Calculations

This paper studies the mapping between continuous and discrete distances. The continuous distance considered is the widely used Euclidean distance, whereas we consider as the discrete distance the chamfer distance based on 3×3 masks. A theoretical characterization of topological errors which arise during the approximation of Euclidean distances by discrete ones is presented. Optimal chamfer distance coefficients are characterized with respect to the topological ordering they induce, rather than the approximation of Euclidean distance values. We conclude the theoretical part by presenting a global upper bound for a topologically correct distance mapping, irrespective of the chamfer distance coefficients, and we identify the smallest coefficients associated with this bound. We illustrate the practical significance of these results by presenting a framework for the solution of a well-known problem, namely the Euclidean nearest-neighbor problem. This problem is formulated as a discrete optimization problem and solved accordingly using algorithmic graph theory and integer arithmetic.     

A graph-theoretic optimal control problem for terminating discrete event processes

Most of the results to date in discrete event supervisory control assume a zero-or-infinity structure for the cost of controlling a discrete event system, in the sense that it costs nothing to disable controllable events while uncontrollable events cannot be disabled (i.e., their disablement entails infinite cost). In several applications however, a more refined structure of the control cost becomes necessary in order to quantify the tradeoffs between candidate supervisors. In this paper, we formulate and solve a new optimal control problem for a class of discrete event systems. We assume that the system can be modeled as a finite acylic directed graph, i.e., the system process has a finite set of event trajectories and thus is terminating. The optimal control problem explicitly considers the cost of control in the objective function. In general terms, this problem involves a tradeoff between the cost of system evolution, which is quantified in terms of a path cost on the event trajectories generated by the system, and the cost of impacting on the external environment, which is quantified as a dynamic cost on control. We also seek a least restrictive solution. An algorithm based on dynamic programming is developed for the solution of this problem. This algorithm is based on a graph-theoretic formulation of the problem. The use of dynamic programming allows for the efficient construction of an optimal subgraph (i.e., optimal supervisor) of the given graph (i.e., discrete event system) with respect to the cost structure imposed. We show that this algorithm is of polynomial complexity in the number of vertices of the graph of the system.Research supported in part by the National Science Foundation under grant ECS-9057967 with additional support from GE and DEC.     

Maximizing robustness of supervisors for partially observed discrete event systems

We consider a robust supervisory control problem to synthesize a supervisor for the nominal plant model which maximizes robustness. Cury and Krogh have first addressed this problem by unnecessarily restricting the upper bound of the legal behavior. In our previous work, we have solved the problem without restricting the upper bound of the legal behavior when the specification is described by prefix-closed languages. In this paper, we extend our previous work to the partial (event) observation case. First, we synthesize a supervisor that maximizes robustness. This result shows that robustness can be optimized under partial observation, while permissiveness cannot be optimized in general. We next consider a special case where all the controllable events are observable. In this special case, we synthesize a maximally permissive supervisor for the nominal plant model which maximizes not only the robustness but also permissiveness for the maximal set of admissible plant variations.     

Optimal reachability for multi-priced timed automata

In this paper, we prove the decidability of the minimal and maximal reachability problems for multi-priced timed automata, an extension of timed automata with multiple cost variables evolving according to given rates for each location. More precisely, we consider the problems of synthesizing the minimal and maximal costs of reaching a given target location. These problems generalize conditional optimal reachability, i.e., the problem of minimizing one primary cost under individual upper bound constraints on the remaining, secondary, costs, and the problem of maximizing the primary cost under individual lower bound constraints on the secondary costs. Furthermore, under the liveness constraint that all traces eventually reach the goal location, we can synthesize all costs combinations that can reach the goal.

The decidability of the minimal reachability problem is proven by constructing a zone-based algorithm that always terminates while synthesizing the optimal cost tuples. For the corresponding maximization problem, we construct two zone-based algorithms, one with and one without the above liveness constraint. All algorithms are presented in the setting of two cost variables and then lifted to an arbitrary number of cost variables.