A note on controllability of deterministic context-free systems

In this paper, we prove that the most important concept of supervisory control of discrete-event systems, the controllability property, is undecidable for two deterministic context-free languages $K$ and $L$, where $L$ is prefix closed, even though $K$ is a subset of $L$. If $K$ is not a subset of $L$, the undecidability follows from the work by Sreenivas. However, the case where $K$ is a subset of $L$ does not follow from that work because it is decidable whether $K$ and $L$ are equivalent as shown by Sénizergues. Thus, our result completes this study. The problem is also mentioned as open in the Ph.D. thesis by Griffin, who extended the supervisory control framework so that the specification language is modeled as a deterministic context-free language (compared to the classical approach where the specification is regular) and the plant language is regular. This approach is of interest because it brings an opportunity for more concise representations of the specification (as discussed, e.g., in the work by Geffert et al.) and, therefore, in some sense it treats the most interesting problem of current supervisory control theory, the state-space explosion problem.     

Supervisory control using variable lookahead policies

This paper deals with the efficient on-line calculation of supervisory controls for discrete event systems (DES's) in the framework of limited lookahead control policies (or LLPs) that we introduced in previous papers. In the LLP scheme, the control action after a given trace of events has been executed is calculated on-line on the basis of anN-step ahead projection of the behavior of the DES. To compute these controls, one must calculate after the execution of each event the supremal controllable sublanguage of a finite language with respect to another finite larger language. In our previous work, we showed how the required supremal controllable sublanguage calculation can be performed by using a backward dynamic programming algorithm over the nodes of the tree representation of these two languages. In this paper, we pursue the same approach for the calculation of LLP controls, but instead we adopt a forward calculation procedure over theN-level tree of interest. This forward procedure improves upon previous work by avoiding the explicit consideration of all the nodes of theN-level tree, while still permitting tree-to-tree recursiveness as enabled events are executed by the system. The forward search ends whenever a control decision can be made unambiguously or whenever the boundary of theN-level tree is reached, whichever comes first. This motivates the name Variable Lookahead Policy (or VLP) for this implementation of the LLP supervisory control scheme. This paper presents a general VLP algorithm and studies the properties of several special cases of it. The paper also discusses the implementation of the VLP algorithms and presents computational results regarding the application of these algorithms to a time-varying DES.     

Evaluation of language measure parameters for discrete event manufacturing systems with multiproduct machines

The concept of language measure provides a mathematical framework for quantitative analysis and synthesis of discrete event supervisory control systems. The language measure is assigned two parameters, namely the state transition cost matrix and the state cost vector. In a recent paper (Khatab and Nourelfath 2006 Khatab, A and Nourelfath, M. 2006. Analytical approach to evaluate language measure parameters for discreteevent supervisory control. Int. J. Control, 79: 688–706.  [Google Scholar]), an analytical approach has been formulated to evaluate the language measure parameters for discrete event manufacturing systems composed of several monoproduct machines, i.e., each machine is able to perform only one kind of product. This paper generalizes these results to the multiproduct case, i.e., to the case where each machine in the manufacturing system is able to perform different kinds of products. The proposed approach is based on the theory of Markov stochastic processes and Kronecker algebra. The main advantage of the proposed approach is that the mathematical expressions of the system language measure parameters are derived from data of individual elementary machines without generating the whole, possibly huge, system state space.     

Equivalence of Polynomial Identity Testing and Polynomial Factorization

In this paper, we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f).Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.Previously, such an equivalence was known only for multilinear circuits (Shpilka & Volkovich, 2010).     

On the Hopcroft’s minimization technique for DFA and DFCA

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires $O(nlogn)$ steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.     

Recursive computation of limited lookahead supervisory controls for discrete event systems

We continue the study of limited lookahead policies in supervisory control of discrete event systems undertaken in a previous paper. On-line control of discrete event systems using limited lookahead policies requires, after the execution of each event, the calculation of the supremal controllable sublanguage of a given language with respect to another larger language. These two languages are finite and represented by their tree generators, where one tree is a subtree of the other. These trees change dynamically from step to step, where one step is the execution of one event by the system. We show in this paper how to perform this calculation in a recursive manner, in the sense that the calculation for a new pair of trees can make use of the calculation for the preceding pair, thus substantially reducing the amount of computation that has to be done on-line. In order to make such a recursive procedure possible from step to step, we show how the calculation for a single step (i.e., for a given pair of trees) can itself be performed recursively by means of a backward dynamic programming algorithm on the vertices of the larger tree. These two nested recursive procedures are also extended to the limited lookahead version of the supervisory control problem with tolerance.Research supported in part by the National Science Foundation under grants ECS-9057967 and ECS-9008947. The first two authors also acknowledge support from GE and DEC.     

Parallel <Emphasis Type="Italic">LL</Emphasis> parsing

A deterministic parallel LL parsing algorithm is presented. The algorithm is based on a transformation from a parsing problem to parallel reduction. First, a nondeterministic version of a parallel LL parser is introduced. Then, it is transformed into the deterministic version—the LLP parser. The deterministic LLP(q,k) parser uses two kinds of information to select the next operation — a lookahead string of length up to k symbols and a lookback string of length up to q symbols. Deterministic parsing is available for LLP grammars, a subclass of LL grammars. Since the presented deterministic and nondeterministic parallel parsers are both based on parallel reduction, they are suitable for most parallel architectures.     

Robust optimal control of regular languages

This paper presents an algorithm for robust optimal control of regular languages under specified uncertainty bounds on the event cost parameters of the language measure that has been recently reported in literature. The performance index for the proposed robust optimal policy is obtained by combining the measure of the supervised plant language with uncertainty. The performance of a controller is represented by the language measure of the supervised plant and is minimized over the given range of event cost uncertainties. Synthesis of the robust optimal supervisory control policy requires at most n iterations, where n is the number of states of the deterministic finite-state automaton (DFSA) model, generated from the regular language of the unsupervised plant behavior. The computational complexity of the control synthesis method is polynomial in n.     

Supervisory control and reactive synthesis: a comparative introduction

This paper presents an introduction to and a formal connection between synthesis problems for discrete event systems that have been considered, largely separately, in the two research communities of supervisory control in control engineering and reactive synthesis in computer science. By making this connection mathematically precise in a paper that attempts to be as self-contained as possible, we wish to introduce these two research areas to non-expert readers and at the same time to highlight how they can be bridged in the context of classical synthesis problems. After presenting general introductions to supervisory control theory and reactive synthesis, we provide a novel reduction of the basic supervisory control problem, non-blocking case, to a problem of reactive synthesis with plants and with a maximal permissiveness requirement. The reduction is for fully-observed systems that are controlled by a single supervisor/controller. It complements prior work that has explored problems at the interface of supervisory control and reactive synthesis. The formal bridge constructed in this paper should be a source of inspiration for new lines of investigation that will leverage the power of the synthesis techniques that have been developed in these two areas.     

An \mathcal O (N \log N) Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices

This article describes a fast direct solver (i.e., not iterative) for partial hierarchically semi-separable systems. This solver requires a storage of $\mathcal O (N \log N)$ and has a computational complexity of $\mathcal O (N \log N)$ arithmetic operations. The numerical benchmarks presented illustrate the method in the context of interpolation using radial basis functions. The key ingredients behind this fast solver are recursion, efficient low rank factorization using Chebyshev interpolation, and the Sherman–Morrison–Woodbury formula. The algorithm and the analysis are worked out in detail. The performance of the algorithm is illustrated for a variety of radial basis functions and target accuracies.     

Fault tolerant scheduling of tasks of two sizes under resource augmentation

Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1-completed load competitiveness properties of deterministic scheduling algorithms under worst-case scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named \(\gamma \text{-Burst } \), that achieves both latency and 1-completed-load competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.     

Time versus cost tradeoffs for deterministic rendezvous in networks

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. Each agent has a distinct integer label from the set \(\{1,\ldots ,L\}\). Two main efficiency measures of rendezvous are its time (the number of rounds until the meeting) and its cost (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (where E and a corresponding exploration procedure are known to both agents) and of the size L of the label space. We present two natural rendezvous algorithms. Algorithm Cheap has cost O(E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O(EL). Algorithm Fast has both time and cost \(O(E\log L)\). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically E (i.e., of cost \(E+o(E)\)) must have time \(\varOmega (EL)\). On the other hand, we show that any deterministic rendezvous algorithm with time complexity \(O(E\log L)\) must have cost \(\varOmega (E\log L)\).     

Synthesis of Σ-Automata Specified in the First Order Logical Languages LP and LF

This paper presents methods for synthesizing Σ-automata from specifications in the language LP with deterministic semantics and in the language LF with nondeterministic semantics. These methods are based on the equivalent transformation of a formula of the form ?tF (t) into the so-called normal form whose structure corresponds to the state transition graph of a specified Σ-automaton.     

On the supervisory control of multi-agent product systems: Controllability properties

Multi-Agent (MA) product systems were defined in [I. Romanovski, P.E. Caines, On the supervisory control of multi-agent products systems, IEEE Trans. Automated Control 51(5) (2006)] where the notion of an MA controllable vector language specification was introduced and necessary and sufficient conditions for the existence of a supervisor for such a specification were derived. In this paper we present a set of results about the controllability of an MA product system and its components. In particular, we obtain an algorithm for finding the infimal MA-controllable superlanguage inf_MA(K) of a given vector (language) specification K w.r.t. an MA product system G and establish that in fact . It is proven that there is an algorithmic procedure for the recursive construction of MA supervisors when additional automata are added to a system via the MA product. Controllability properties of component structures (such as standard controllability and MA controllability of projections) are considered. Several examples are given to illustrate the results of the paper.     

A Modified Deterministic Annealing Algorithm for Robust Image Segmentation

In this paper, we present a modified deterministic annealing algorithm, which is called DA-RS, for robust image segmentation. The presented algorithm is implemented by incorporating the local spatial information and a robust non-Euclidean distance measure into the formulation of the standard deterministic annealing (DA) algorithm. This implementation offers several improved features compared to existing image segmentation methods. First, it has less sensitivity to noise and other image artifacts due to the incorporation of spatial information. Second, it is independent of data initialization and has the ability to avoid many poor local optima due to the deterministic annealing process. Lastly, it possesses enhancing robustness and segmentation ability due to the injection of a robust non-Euclidean distance measure, which is obtained through a nonlinear mapping by using Gaussian radial basis function (GRBF). Experimental results on synthetic and real images are given to demonstrate the effectiveness and efficiency of the presented algorithm.

B-spline surface fitting by iterative geometric interpolation/approximation algorithms

Recently, the use of $B$-spline curves/surfaces to fit point clouds by iteratively repositioning the $B$-spline’s control points on the basis of geometrical rules has gained in popularity because of its simplicity, scalability, and generality. We distinguish between two types of fitting, interpolation and approximation. Interpolation generates a $B$-spline surface that passes through the data points, whereas approximation generates a $B$-spline surface that passes near the data points, minimizing the deviation of the surface from the data points. For surface interpolation, the data points are assumed to be in grids, whereas for surface approximation the data points are assumed to be randomly distributed. In this paper, an iterative geometric interpolation method, as well as an approximation method, which is based on the framework of the iterative geometric interpolation algorithm, is discussed. These two iterative methods are compared with standard fitting methods using some complex examples, and the advantages and shortcomings of our algorithms are discussed. Furthermore, we introduce two methods to accelerate the iterative geometric interpolation algorithm, as well as a method to impose geometric constraints, such as reflectional symmetry, on the iterative geometric interpolation process, and a novel fairing method for non-uniform complex data points. Complex examples are provided to demonstrate the effectiveness of the proposed algorithms.     

An Algorithm for Timing Verification of Systems Constrained by Min–max Inequalities

To determine the maximum separation between events for nonrepetitive systems with max and linear constraints, there are the “iterative tightening from above” (ITA) approach and the “iterative tightening from below” (ITB) approach. Since such systems can be formulated as systems constrained by min–max inequalities, this paper gives an algorithm named MMIMaxSep for solving min–max inequalities. The algorithm is a generalization and a mathematically elegant reformulation of Yen et al.’s MaxSeparation algorithm which uses the ITB approach. Our numerical experiments indicate that MMIMaxSep is very efficient. Moreover, MMIMaxSep has a unique advantage of being able to directly handle tree-represented min–max functions, and its complexity is closely related to the complexity of computing cycle time of min–max functions.

Competitive Online Multicommodity Routing

We study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm showing that for affine price functions this algorithm is  -competitive, where K is the number of commodities. For networks with two nodes and parallel arcs, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. We then investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. The variant of the greedy algorithm that produces unsplittable flows is -competitive, and we prove a lower bound of 2 for the competitive ratio of any deterministic online algorithm. A preliminary version of this paper appeared in [20]. S. Heinz has been supported by the DFG Research Center Matheon Mathematics for key technologies in Berlin.     

On the effect of the deployment setting on broadcasting in Euclidean radio networks

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane (each station knows its own coordinates). In any given time step, a station can either receive or transmit. A message transmitted from station v is delivered to every station u at distance at most 1 from v, but u successfully hears the message if and only if v is the only station at distance at most 1 from u that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [17] that the time complexity of deterministic broadcasting algorithms depends on two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [17] present a deterministic broadcasting algorithm that works in time O (Dg) and prove that every broadcasting algorithm requires \(\varOmega \left( D \sqrt{g} \right) \) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [17], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a d-spaced grid. Does the latter (more restricted) setting provide any speedup in broadcasting time complexity? Although the O (Dg) broadcasting algorithm of [17] works under the (original) arbitrary deployment setting, it turns out that the \(\varOmega \left( D \sqrt{g} \right) \) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of deterministic broadcasting algorithms under the arbitrary deployment setting proving that broadcasting cannot be completed in less than \(\varOmega (D g)\) time. For the grid deployment setting, we develop a deterministic broadcasting algorithm that runs in time \(O \left( D g^{5 / 6} \log g \right) \), thus breaking the linear dependency on g.