Shortest directing words of nondeterministic directable automata

In this paper, we will survey several results on the shortest directing words of various types of nondeterministic directable automata.¹     

On an expansion of nondeterministic finite automata

We consider a possible generalization of nondeterministic finite automata. The goals of this consideration are: to apply some obtained algorithms for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; to simplify some proofs for algorithms of simplification for usual nondeterministic automata.     

Some algorithms for equivalent transformation of nondeterministic finite automata

In this paper we consider algorithms which allow one to combine several states of a nondeterministic finite automaton into one state. Along with the algorithms for combining states, we adduce one more algorithm for the equivalent transformation of a non-deterministic finite automaton, namely, an algorithm for adding cycles. Problems under consideration imply the development of robust computer programs.     

On the equivalence of stationary and finite-nonstationary nondeterministic automata

The synthesis problem for a generalized stationary nondeterministic automaton equivalent to an arbitrary given generalized finite-nonstationary nondeterministic automation is solved. A synthesis algorithm is described.     

Once more about the state-minimization of the nondeterministic finite automata

In this paper we consider the corrected version of the algorithm of the state-minimization for the nondeterministic finite automata: we correct here a mistake of the previous paper, where the same problem was considered.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

A new algorithm of the state-minimization for the nondeterministic finite automata

The problem of the state-minimization for the nondeterministic finite Rabin-Scott’s automata is considered. A new algorithm for this problem is obtained. The obtained algorithm has the exponential effectiveness, like the earlier-known algorithms for this problem. But each of previous algorithms amounts to the search of minimum generative system for local reaction of equal automaton of canonical form, and unlike them, we use in this paper two special functions, marking states of the given automaton.     

On right congruences associated with the input semigroupS of automata

LetA=(M, S, δ) be an automaton without outputs whereM is a nonemptyset andS is a nonempty semigroup. Then the right congruences μM and μ _m associated withS have been expressed in many different ways (μ _M is called the Myhill-Nerode congruence onS). Also, their algebraic properties have been investigated. We have introduced the right congruences μ _S and μ_α onM and we have obtained necessary and sufficient conditions thatS/μ andM/w have nontrivialS-homomorphisms where μ andw are any right congruences onS andM respectively. The faithfulness ofS has been introduced.     

Controllability of linear nonstationary systems with scalar input and quasidifferentiable coefficients

We suggest a method for studying the controllability of linear nonstationary systems of ordinary differential equations. The method is based on the quasidifferentiability of the coefficients with respect to a specially constructed lower-triangular matrix. This approach permits substantially weakening the well-known smoothness conditions imposed on the coefficients when stating controllability criteria.     

Finitely additive random walks on infinitely generated free groups

We consider any purely finitely additive probability measure supported on the generators of an infinitely generated free group and the Markov strategy with stationary transition probability . As well as for the case of random walks (with countably additive transition probability) on finitely generated free groups, we prove that all bounded sets are transient. Finally, we consider any finitely additive measure (supported on the group generators) and we prove that the classification of the state space depends only on the continuous part of .     

Local likelihood estimation for nonstationary random fields

We develop a weighted local likelihood estimate for the parameters that govern the local spatial dependency of a locally stationary random field. The advantage of this local likelihood estimate is that it smoothly downweights the influence of faraway observations, works for irregular sampling locations, and when designed appropriately, can trade bias and variance for reducing estimation error. This paper starts with an exposition of our technique on the problem of estimating an unknown positive function when multiplied by a stationary random field. This example gives concrete evidence of the benefits of our local likelihood as compared to unweighted local likelihoods. We then discuss the difficult problem of estimating a bandwidth parameter that controls the amount of influence from distant observations. Finally we present a simulation experiment for estimating the local smoothness of a local Matérn random field when observing the field at random sampling locations in [0,1]². The local Matérn is a fully nonstationary random field, has a closed form covariance, can attain any degree of differentiability or Hölder smoothness and behaves locally like a stationary Matérn. We include an appendix that proves the positive definiteness of this covariance function.     

Small work-load mode in a queueing system with random nonstationary intensity

We consider a queueing system of M _t R|GI|1|∞ type with doubly stochastic Poisson arrival stream. The case of a small work load in such a system is studied. We derive an asymptotic expansion in the work-load smallness parameter of the distribution function of the virtual waiting time.     

Dynamics of quasiparticles in a nonstationary random field

Khar'kov Physicotechnical Institute of Low Temperatures, Ukrainian SSR Academy of Sciences. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 76, No. 3, pp. 401–417, September, 1988.     

Stability of vertices in random boolean cellular automata

Based on computer simulations, Kauffman (Physica D, 10, 145-156, 1984) made several generalizations about a random Boolean cellular automaton which he invented as a model of cellular metabolism. Here we give the first rigorous proofs of two of Kauffman's generalizations: a large fraction of vertices stabilize quickly, consequently the length of cycles in the automaton's behavior is small compared to that of a random mapping with the same number of states; and reversal of the states of a large fraction of the vertices does not affect the cycle to which the automaton moves.     

Stochastic Galerkin methods for elliptic interface problems with random input

In this work, we consider random elliptic interface problems, namely, the media in elliptic equations have both randomness and interfaces. A Galerkin method using bi-orthogonal polynomials is used to convert the random problem into an uncoupled system of deterministic interface problems. A principle on how to choose the orders of the approximated polynomial spaces is given based on the sensitivity analysis in random spaces, with which the total degree of freedom can be significantly reduced. Then immersed finite element methods are introduced to solve the resulting system. Convergence results are given both theoretically and numerically.