Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Regular Model Checking using Widening Techniques

In this paper, we consider symbolic model checking of safety properties of linear parametrized systems. Sets of configurations are represented by regular languages and actions by regular relations. Since the verification problem amounts to the computation of the reachability set, we focus on the computation of R^*(φ) for a regular relation R and a regular language φ. We present a technique called regular widening that allows, when it terminates, the computation of either the reachability set R^*(φ) of a system or the transitive closure R^* of a regular relation. We show that our method can be uniformly applied to several parametrized systems. Furthermore, we show that it is powerful enough to simulate some existing methods that compute either R^* or R^*(φ) for each R (resp. φ) belonging to a subclass of regular relations (resp. belonging to a subclass of regular languages).     

Symbolic model checking for probabilistic timed automata

Probabilistic timed automata are timed automata extended with discrete probability distributions, and can be used to model timed randomised protocols or fault-tolerant systems. We present symbolic model-checking algorithms for probabilistic timed automata to verify both qualitative temporal logic properties, corresponding to satisfaction with probability 0 or 1, and quantitative properties, corresponding to satisfaction with arbitrary probability. The algorithms operate on zones, which represent sets of valuations of the probabilistic timed automaton’s clocks. Our method considers only those system behaviours which guarantee the divergence of time with probability 1. The paper presents a symbolic framework for the verification of probabilistic timed automata against the probabilistic, timed temporal logic PTCTL. We also report on a prototype implementation of the algorithms using Difference Bound Matrices, and present the results of its application to the CSMA/CD and FireWire root contention protocol case studies.     

Use of simulation in the analysis of shop floor operations

The use of computers in actual system applications is increasing with the availability of intelligent terminals on the shop floor. These terminals can be used by management as tools in the decision making process of planning shop floor operation. This paper discusses a pilot simulation study in the use of conventional Fortran-based simulation programs by shop floor management to:

1. 1. Participate in the evaluation of proposed FMS systems,

2. 2. Assess the impact of FMS acquisition on existing facilities,

3. 3. Assist in the identification of operational alternatives in “bottle neck” situations.

The pilot study employs a batch-oriented MRP system to provide daily updates of outstanding production center loadings on a monthly planning horizon. Two intelligent terminals are used to access a mini computer facility that executes the simulation models. The terminals have AT-compatible capabilities and are also used as data acquisition devices that support the numerically controlled operations within each work center.

The simulation models represent the 13 work centers of the firm and provide information about the average utilization of each work center, the number of parts in each queue and the average delay of parts in the queues. Future extensions of the models are planned to utilize the terminals' graphic animation capabilities to display the flow of production orders through the manufacturing facility.     

Entropy maximisation and open queueing networks with priorities and blocking

A review is carried out on the characterisation and algorithmic implementation of an extended product-form approximation, based on the principle of maximum entropy (ME), for a wide class of arbitrary finite capacity open queueing network models (QNMs) with service and space priorities. A single server finite capacity GE/GE/1/N queue with R (R>1) distinct priority classes, compound Poisson arrival processes (CPPs) with geometrically distributed batches and generalised exponential (GE) service times is analysed via entropy maximisation, subject to suitable GE-type queueing theoretic constraints, under preemptive resume (PR) and head-of-line (HOL) scheduling rules combined with complete buffer sharing (CBS) and partial buffer sharing (PBS) management schemes stipulating a sequence of buffer thresholds {N=(N₁,…,N_R),0<N_i≤N_i−1,i=2,…,R}. The GE/GE/1/N queue is utilised, in conjunction with GE-type first two moment flow approximation formulae, as a cost-effective building block towards the establishment of a generic ME queue-by-queue decomposition algorithm for arbitrary open QNMs with space and service priorities under repetitive service blocking with random destination (RS-RD). Typical numerical results are included to illustrate the credibility of the ME algorithm against simulation for various network topologies and define experimentally pessimistic GE-type performance bounds. Remarks on the extensions of the ME algorithm to other types of blocking mechanisms, such as repetitive service blocking with fixed destination (RS-FD) and blocking-after-service (BAS), are included.     

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Discrete warehouse problem

A discrete warehouse is a collection of two-dimensional unit-square objects (robot and obstacles), which are allowed to move horizontally and vertically along grid lines. In this paper, we consider motion planning problems in a discrete warehouse with movable obstacles. In such a setup one is allowed to move some of the obstacles in order to:

1. (1) navigate the robot between an initial and a final position of the warehouse, and

2. (2) construct a clearing (path) between two specified points.

The final positions of the obstacles are unimportant for our problems.

We consider two forms of obstacle manipulations:

1. (a) remote, when the obstacles are moved by a remote mechanism, and

2. (b) contact, when the obstacles are moved only by direct contact of the robot.

We present necessary and sufficient conditions for the existence of a motion in both cases, and propose efficient algorithms for constructing feasible motions.     

Analysis of a tandem queue with state-dependent general blocking: A GSMP perspective

In this paper, we study a tandem queue where there is a finite number of buffer positions at each stage. The blocking scheme is general in the sense that it can model a number of classical blocking schemes, including communication, manufacturing and kanban blockings as special cases. The system considered here differs from the conventional system in two aspects: (1) departure of jobs from the system is determined by an external arrival process of another queue lying parallel to the tandem queue; (2) the control parameters of the blocking scheme are state-dependent in that they may change values depending on the state of the system.

We model this system as a generalized semi-Markov process (GSMP), we study the structural properties of its scheme, and establish monotonicity and convexity properties of event times with respect to both the clock times and the integer blocking parameters. In particular, we demonstrate that the state-dependent scheme is “better”, in certain sense, than the corresponding static scheme. Our results also recover the structural properties previously established for the classical blockings.     

Combined effects of in-plane boundary conditions and stiffening on buckling of eccentrically stringer-stiffened cylindrical panels

Donnel type stability equations for buckling of stringer stiffened cylindrical panels under combined axial compression and hydrostatic pressure are solved by the displacement approach of [6], The solution is employed for a parametric study over a wide range of panel and stringer geometries to evaluate the combined influence of panel configurations and boundary conditions along the straight edges on the buckling behavior of the panel relative to a complete “counter” cylinder (i.e. a cylinder with identical skin and stiffener parameters).

The parametric studies reveal a “sensitivity” to the “weak in shear”, N_x = N_xφ = 0, along the straight edges, SS1 boundary conditions type where the panel buckling loads are always smaller than those predicted for a complete “counter” cylinder. In the case of “classical”, SS3 B.Cs., there always exist values of panel width, 2φ₀, for which ρ = 1, i.e. the panel buckling load equals that of the complete “counter” cylinder. For SS2 and SS4 B.Cs. types, the nature by which the panel critical load approaches that of the complete cylinder appears to be panel configuration dependent.

Utilization of panels for the experimental determination of a complete cylinder buckling load is found to be satisfactory for relatively very lightly and heavily stiffened panels, as well as for short panels, (L/R) = 0.2 and 0.5. Panels of moderate length and stiffening have to be debarred, since they lead to nonconservative buckling load predictions.     

The sticky buffer flow control for the ATM

Data from different applications — voice, video, file transfer, interactive — will be multiplexed in the future over broadband integrated services digital networks (BISDN). Data are segmented into 48-byte blocks prefixed by a 5-byte header and transported over the network using the asynchronous transfer mode (ATM).

An ATM connection-request is a contract between the user and the network; the user specifies a rate requirement, delay constraints, a bound on the cell-loss probability and other quality of service parameters. If the network can meet these requirements, a connection is made. Bursty traffic producing peak traffic rates in excess of the projected average rate could result in congestion and lead to performance degradation. As a result, the network might no longer be able to deliver the negotiated quality of service to existing connections. To lessen the chance of congestion, input rate control must be implemented.

This paper contains a performance analysis of the sticky buffer (SB), a moving window input rate control scheme intended to limit the rate at which input traffic may enter a network. Policing is achieved by buffering and hence delaying the entry of ATM-cells into the network. The scheme is determined by parameters (R,T) which specify that no more than R ATM-cells are permitted to enter the network in every window of size T cells. We present an exact analysis, deriving the probability generating function of the queue length distribution. A comparison with the leaky bucket is given. Our numerical examples show the required buffer size is comparable to that required by the leaky bucket.     

异步多进程时间自动机的可覆盖性问题

已有的实时系统模型无法动态创建新进程.为此,基于时间自动机模型,提出了异步多进程时间自动机模型,将每个进程抽象为进程时间自动机,其部分状态能触发新的进程.考虑到队列会导致模型图灵完备,进程都被缓存在集合中,但仍可建模许多实时系统.通过将其编码到可读边时间Petri网,证明了该模型的可覆盖性问题可判定.     

Automata over continuous time

The principal objective of this paper is to lift basic concepts of the classical automata theory from discrete to continuous (real) time. It is argued that the set of finite memory retrospective functions is the set of functions realized by finite state devices. We show that the finite memory retrospective functions are speed-independent, i.e., they are invariant under ‘stretchings’ of the time axis. Therefore, such functions cannot deal with metrical aspects of the reals.

We classify and analyze phenomena which appear at continuous time and are invisible at discrete time.     

Intersection of finitely generated congruences over term algebra

We show that it is decidable for any given ground term rewrite systems R and S if there is a ground term rewrite system U such that ↔_U^*=↔_R^*∩↔_S^*. If the answer is yes, then we can effectively construct such a ground term rewrite system U. In other words, for any given finitely generated congruences ρ and τ over the term algebra, it is decidable if ρ∩τ is a finitely generated congruence. If the answer is yes, then we can effectively construct a ground term rewrite system U such that ↔_U^*=ρ∩τ.     

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

The power of reachability testing for timed automata

The computational engine of the verification tool U consists of a collection of efficient algorithms for the analysis of reachability properties of systems. Model-checking of properties other than plain reachability ones may currently be carried out in such a tool as follows. Given a property φ to model-check, the user must provide a test automaton T_φ for it. This test automaton must be such that the original system S has the property expressed by φ precisely when none of the distinguished reject states of T_φ can be reached in the synchronized parallel composition of S with T_φ. This raises the question of which properties may be analysed by U in such a way. This paper gives an answer to this question by providing a complete characterization of the class of properties for which model-checking can be reduced to reachability testing in the sense outlined above. This result is obtained as a corollary of a stronger statement pertaining to the compositionality of the property language considered in this study. In particular, it is shown that our language is the least expressive compositional language that can express a simple safety property stating that no reject state can ever be reached.

Finally, the property language characterizing the power of reachability testing is used to provide a definition of characteristic properties with respect to a timed version of the ready simulation preorder, for nodes of τ-free, deterministic timed automata.     

Analysis on queueing systems with synchronous vacations of partial servers

We study an M/M/c queue with server vacations. In this queueing system, d (≤c) of c servers take synchronous vacations when these d servers become idle at a service completion instant. This type of queueing model captures the major characteristics of a stochastic service system which processes both random arriving jobs and constantly available jobs. In this paper, the multi-server vacation queueing system has been analyzed as a quasi-birth and death process. Using matrix geometric method, we obtain the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Development of an integrated information model for computer integrated manufacturing

The development of an FDBS is integrate existing CIM components by using a bottom-up development process. The components used in this paper do not support any kind database management. The integration of those components into a federation may be done by using two general approaches [3]:

• • Migration of the files to a DBMS

• • Extend the file system to support DBMS-like features

Both migration and extension of the file system are costly solutions and actually depend on existing capabilities of the components. Problems may occur when the federated schema becomes too large. The schema might be split up into smaller federated schemes (loosely coupled FBDS).     

Modeling buffer utilization in cell-based networks

Variable bit rate traffic is characteristically bursty and the arrivals are highly correlated. New network technology carries such traffic in cell-based networks where the service is a discrete time, deterministic process with the service rate determined by bandwidth negotiated by the user. Managing such networks is hard, and predicting cell loss at a station with limited buffer capacity K is essential to enable the user to negotiate his quality of service requirements. We present an analysis to determine the queue length distribution and the loss probability in such circumstances. For our analysis, we use an m-phase Markov Modulated Bernoulli Process with binomial distributed batch arrivals and deterministic service and limited capacity K, i.e. a MMBP^[X]_(m)/D/1 − K queuing system. We show that the system can be analyzed using the so-called unfinished work approach. The validity of our evaluation technique is illustrated by comparing our analytical results against those obtained from an event-driven siimulation of the same system.     

On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R(n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσ_k machines running in reversal O(R(n)) is equal to the class of languages accepted by off-line 1-tape σ₁ machines running in reversal O(R(n)). An off-line 1-tape σ_k machine M is called an off-line 1-tape rσ_k machine if M always limits the non-blank part of the work-tape to at most O(R(n) log n) when making an alternation between universal and existential states during the computation.