A study of queueing networks with deterministic service and application to computer networks

Summary We consider a packet-switching network as a queueing system with constant service times: that means that the lengths of the packets are equal. We study such a network by isolating a particular path which we treat as tandem queueing system. Two aspects will be examined: the study of the response time of such a system, and the throughput of such a system when time-outs are used to destroy packets. The results we obtain show that when the interference between paths is neglected the response time is independent of the order of the stations. The control policy we examine proves the necessity to have a limitated memory capacity at each node of a packet-switching network. These results confirm the intuitive options taken in a network like CYCLADES.     

A notation for deterministic cooperating processes

This paper proposes extensions of sequential programming languages for parallel programming that have the following features: 1) Dynamic Structures: The process structure is dynamic. Processes and variables can be created and deleted. 2) Paradigm Integration: The programming notation supports shared memory and message passing models. 3) Determinism: Demonstrating that a program is deterministic-all executions with the same input produce the same output-is straightforward, Programs can be written so that compilers can verify that the programs are deterministic. Nondeterministic constructs can be introduced in a sequence of refinement steps to obtain greater efficiency if required. The ideas have been incorporated in an extension of Fortran, but the underlying sequential imperative language is not central to the ideas described here. A compiler for the Fortran extension, called Fortran M, is available by anonymous ftp From Argonne National Laboratory. Fortran M has been used for a variety of parallel applications     

A hierarchy of deterministic top-down tree transformations

The classDTT ^DR (resp.DTT) is the family of all deterministic top-down tree transductions with deterministic top-down look-ahead (resp. no look-ahead). In this paper we prove that the two hierarchies (DTT ^DR ) ⁿ and (DTT ^DR ) ⁿ oDTT are proper and that they “shuffle perfectly” in the sense that (DTT ^DR ) ⁿ is properly contained in (DTT ^DR ) ⁿ oDTT and (DTT ^DR ) ⁿ oDTT is properly contained in (DTT ^DR ) ⁿ⁺¹ for alln ≥ 0. Using these results we show that the problem of determining the correct inclusion relationship between two arbitrary compositions of tree transformation classes from the set {DTA, DTT, DTT ^DR ,DTT ^R } can be decided in linear time. A preliminary version of this paper appeared in theProceedings of Fundamentals of Computation Theory 9th International Conference, FCT'93, Szeged, Hungary, Lecture Notes in Computer Science, Vol. 710, Springer-Verlag, Berlin, pp. 440–451, 1993. This research was done while the second author was on leave from the Research Group on Theory of Automata, Hungarian Academy of Sciences, supported by a research grant from the Soros Foundation.     

A deterministic theory of estimation and control

A feedback control system can be structured for linear nonstationary process and measurement systems comprising a deterministic filter whose output is the independent variable of a linear control law. Subject to uniform controllability and observability, the filter and control gains can be specified to provide arbitrary and separable stability properties. If the filter gain is selected to produce a stabilizing effect on the state estimate, and the control gain is selected to produce a stabilizing effect on the process, the filter and control gains are shown to satisfy matrix Riccati differential equations. This suggests the use of stochastic optimal control theory when there is no quantitative measure of optimality, but it is desirable to assure the qualitative property that feedback be stabilizing. A concise derivation of the Kalman-Bucy filter is included in an appendix to illustrate the facility of approaching optimal estimation problems with the methods of stability theory.     

A deterministic test for permutation polynomials

A new deterministic algorithm is presented for testing whether a given polynomial of degreen over a finite field ofq elements is a permutation polynomial. The algorithm has computing time (nq)^6/7+, and gives a positive answer to a question of Lidl and Mullen.     

A study of the Kalman filter as a state estimator of deterministic and stochastic systems

It is shown that the optimality of the Kalman filter prevents its application to estimate the state of deterministic; systems but that if the gain is slightly modified a deterministic filter is possible. Such a filter is subsequently used to explain some of the difficulties encountered in Kalman filter computations, from which it transpires that much Kalman filtering is essentially an application of a deterministic filter to stochastic problems. To reduce the order of the algorithm the concept of observer robustness is incorporated into the subsequent development of the deterministic filter. Exactly equivalent discrete- and continuous-time algorithms are derived and used for a new treatment of the problem of obtaining estimates of the state variables of a stochastic system when the measurements are free of noise.     

A note on non-singular deterministic pushdown automata

The non-singular deterministic pushdown automata were first defined by Valiant as an example of a class of machines with a decidable equivalence problem [3]. No algorithm currently exist for deciding whether or not a deterministic pushdown automation is non-singular, so the applicability of Valiant's equivalence decision procedure cannot be readily (if ever) determined. In this paper, it is shown that the equivalence problem for non-singular automata is reducible to the problem of deciding whether or not a deterministic pushdown automaton is non-singular.     

A General Probabilistic Framework for uncertainty and global sensitivity analysis of deterministic models: A hydrological case study

The present study proposes a General Probabilistic Framework (GPF) for uncertainty and global sensitivity analysis of deterministic models in which, in addition to scalar inputs, non-scalar and correlated inputs can be considered as well. The analysis is conducted with the variance-based approach of Sobol/Saltelli where first and total sensitivity indices are estimated. The results of the framework can be used in a loop for model improvement, parameter estimation or model simplification. The framework is applied to SWAP, a 1D hydrological model for the transport of water, solutes and heat in unsaturated and saturated soils. The sources of uncertainty are grouped in five main classes: model structure (soil discretization), input (weather data), time-varying (crop) parameters, scalar parameters (soil properties) and observations (measured soil moisture). For each source of uncertainty, different realizations are created based on direct monitoring activities. Uncertainty of evapotranspiration, soil moisture in the root zone and bottom fluxes below the root zone are considered in the analysis. The results show that the sources of uncertainty are different for each output considered and it is necessary to consider multiple output variables for a proper assessment of the model. Improvements on the performance of the model can be achieved reducing the uncertainty in the observations, in the soil parameters and in the weather data. Overall, the study shows the capability of the GPF to quantify the relative contribution of the different sources of uncertainty and to identify the priorities required to improve the performance of the model. The proposed framework can be extended to a wide variety of modelling applications, also when direct measurements of model output are not available.     

A deterministic capacity-finding method for multi-valuedexponential BAM

The multi-valued exponential bidirectional associative memory (MV-eBAM) has been proposed and proved to be asymptotically stable under certain constraints. Although multi-valued eBAM has been verified to possess high capacity by thorough simulations, the capacity is still unable to be solved analytically. In the paper, an algorithm is proposed to derive the capacity. Some important characteristics, including the absolute lower bound of the radix, and the approximate capacity are also discussed. The result shows that the multi-valued eBAM indeed possesses high capacity     

A complete characterization of deterministic regular liveness properties

Many systems can be modeled formally by nondeterministic Büchi-automata. The complexity of model checking then essentially depends on deciding subset conditions on languages that are recognizable by these automata and that represent the system behavior and the desired properties of the system. The involved complementation process may lead to an exponential blow-up in the size of the automata. We investigate a rich subclass of properties, called deterministic regular liveness properties, for which complementation at most doubles the automaton size if the properties are represented by deterministic Büchi-automata. In this paper, we will present a decomposition theorem for this language class that entails a complete characterization of the deterministic regular liveness properties, and extend an existing incomplete result which then, too, characterizes the deterministic regular liveness properties completely.     

A deterministic analysis of stochastic approximation withrandomized directions

We study the convergence of two stochastic approximation algorithms with randomized directions: the simultaneous perturbation stochastic approximation algorithm and the random direction Kiefer-Wolfowitz algorithm. We establish deterministic necessary and sufficient conditions on the random directions and noise sequences for both algorithms, and these conditions demonstrate the effect of the “random” directions on the “sample-path” behavior of the algorithms studied. We discuss ideas for further research in the analysis and design of these algorithms     

基于三态调制的电力线载波通信的研究

电力线是目前分布最广的有线网络,利用电力线网络进行通信实现自动抄表是电力企业追切需求,但目前电力线载波通信的现状不能令人满意,针对电力线载波通信的现状,本文提出了一种基于三态脉冲位移相位调制的电力线载波通信的调制解调方式,利用RS编解码技术,通过信号检测算法的研究,实现了在相对恶劣环境下的电力线载波通信,并将软硬件开发设计完成的DEMO（实验样品）板进行了实验室模拟环境下的测试,由测试结果可知,此方案基本能满足电力载波抄表的要求,对目前电力线载波通信的研究有一定的参考价值。     

A Cramer-Rao-like error bound in deterministic parameter estimation

This paper derives a Cramer-Rao-like lower bound on the parameter estimation error in a deterministic setting. The bound provides the theoretical limit for deterministic identifiers     

A note on unary deterministic time-delayed OL systems

We point out an error in Wood [1] and show how to modify the particular theorem in question.     

A deterministic skip list for k-dimensional range search

This paper presents a new data structure for multi-dimensional point data which is based on an extension of the deterministic skip list data structure projected into k dimensions. The structure is labeled the k-d Range Deterministic Skip List and it supports fast insertions, deletions, and range search. The k-d Range Deterministic Skip List is optimal (i.e. t) to locate and report t of n data points in range) for k-dimensional range search, assuming that our data points are elements of a commutative semigroup with set union as the commutative and associative addition operation. A dynamic data structure is defined to be optimally balanced if the product of its worst case cost functions for k-dimensional range search, insertion, deletion, storage, and preprocessing is minimal. The k-d Range Deterministic Skip List is found to be optimally balanced based on this definition.Received: 17 October 1995, Published online: 19 January 2005