Stochastic grammars and languages

This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.This work was supported by the National Science Foundation Grant GK-18225.     

Parameter optimization of stochastic automata operating in random environments

Two methods of determining the lower bounds of the rate of convergence of finite stochastic automata are presented. The rate of convergence, defined as the percentage decrease in the distance between the transient probability distribution and the equilibrium probability distribution in each step, is determined as a function of the probability transition matrix. Formulas for parameter optimization for a class of stochastic automata for fast convergence and maximum expediency are derived and illustrative examples of fourth-order systems are given.     

Finite stochastic automata with variable transition probabilities

The transition probabilities of the stochastic automata we introduce in this paper are dependent upon the number of times the current state has been passed by. All the possible ways an automaton can develop, are represented by a set of matrices, which is formally characterized. Based on this representation, a method to calculate some probabilities of these automata, is given.     

Stochastic optimization over continuous and discrete variables withapplications to concept learning under noise

We consider optimization problems where the objective function is defined over some continuous and some discrete variables, and only noise corrupted values of the objective function are observable. Such optimization problems occur naturally in PAC learning with noisy samples. We propose a stochastic learning algorithm based on the model of a hybrid team of learning automata involved in a stochastic game with incomplete information to solve this optimization problem and establish its convergence properties. We then illustrate an application of this automata model in learning a class of conjunctive logic expressions over both nominal and linear attributes under noise     

Numerical analysis of rational processes beyond Markov chains

Matrix exponential distributions and rational arrival processes have been proposed as an extension to pure Markov models. The paper presents an approach where these process types are used to describe the timing behavior in quantitative models like queueing networks, stochastic Petri nets or stochastic automata networks. The resulting stochastic process, which is called a rational process, is defined and it is shown that the matrix governing the behavior of the process has a structured representation which allows one to represent the matrix in a very compact form.     

A new approach to the design of reinforcement schemes for learningautomata: stochastic estimator learning algorithms

A new class of learning automata is introduced. The new automata use a stochastic estimator and are able to operate in nonstationary environments with high accuracy and a high adaptation rate. According to the stochastic estimator scheme, the estimates of the mean rewards of actions are computed stochastically. So, they are not strictly dependent on the environmental responses. The dependence between the stochastic estimates and the deterministic estimator's contents is more relaxed when the latter are old and probably invalid. In this way, actions that have not been selected recently have the opportunity to be estimated as “optimal”, to increase their choice probability, and, consequently, to be selected. Thus, the estimator is always recently updated and consequently is able to be adapted to environmental changes. The performance of the Stochastic Estimator Learning Automaton (SELA) is superior to the previous well-known S-model ergodic schemes. Furthermore, it is proved that SELA is absolutely expedient in every stationary S-model random environment     

A new class of /spl epsi/-optimal learning automata

A new class of P-model absorbing learning automata is introduced. The proposed automata are based on the use of a stochastic estimator in order to achieve a rapid and accurate convergence when operating in stationary random environments. According to the proposed stochastic estimator scheme, the estimates of the reward probabilities of actions are not strictly dependent on the environmental responses. The dependence between the stochastic estimates and the deterministic ones is more relaxed for actions that have been selected only a few times. In this way, actions that have been selected only a few times, have the opportunity to be estimated as "optimal," to increase their choice probability and consequently, to be selected. In this way, the estimates become more reliable and consequently, the automaton rapidly and accurately converges to the optimal action. The asymptotic behavior of the proposed scheme is analyzed and it is proved to be epsilon-optimal in every stationary random environment. Furthermore, extensive simulation results are presented that indicate that the proposed stochastic estimator scheme converges faster than the deterministic-estimator-based DP(RI) and DGPA schemes when operating in stationary P-model random environments.     

An iterative bounding method for stochastic automata networks

A method to bound stationary distributions of large Markov chains resulting from networks of stochastic automata is presented. It combines the concepts for bounding the stationary distribution using eigenvector polyhedra with the exploitation of the specific structure of Markov chains resulting from stochastic automata networks. The quality of the bounds depends on the coupling between automata. Three consecutive steps of the method are presented. In the first step bounds are computed using information about single automata in isolation. Bounds for single automata are refined in a second step by considering the environment of an automaton given by the other automata in the network. In a third step, bounds are further improved using a disaggregation step. By means of two small examples it is shown that the method yields tight bounds for loosely coupled automata and that the approach is extremely efficient compared to other bounding methods, let alone compared to an exact numerical analysis.     

History dependent stochastic automata: A formal view of evolutionary learning

We develop a theoretical framework for the study of evolutionary learning systems. the formalism we use is that of history dependent stochastic automata with suitable structure, as well as related structures. This formalism provides a natural setting in which to describe the learning of classification hierarchies, of control hierarchies and notions of selfreference, all of which are derived as consequences of the ability to learn by association.     

p-Automata: New foundations for discrete-time probabilistic verification

We introduce p-Automata, which are automata that accept languages of Markov chains, by adapting notions and techniques from alternating tree automata to the realm of Markov chains. The set of languages of p-automata is closed under Boolean operations, and for every PCTL formula it contains the language of the set of models of the formula. Furthermore, the language of every p-automaton is closed under probabilistic bisimulation. Similar to tree automata, whose acceptance is defined via two-player games, we define acceptance of Markov chains by p-automata through two-player stochastic games. We show that acceptance is solvable in EXPTIME; but for automata that arise from PCTL formulas acceptance matches that of PCTL model checking, namely, linear in the formula and polynomial in the Markov chain. We also derive a notion of simulation between p-automata that approximates language containment in EXPTIME and is complete for Markov chains. These foundations therefore enable abstraction-based probabilistic model checking for probabilistic specifications that subsume Markov chains, and LTL and CTL* like logics.     

Diagnosability of stochastic discrete-event systems

We investigate diagnosability of stochastic discrete-event systems. We define the notions of A- and AA-diagnosability for stochastic automata; these notions are weaker than the corresponding notion of diagnosability for logical automata introduced by Sampath et al. Through the construction of a stochastic diagnoser, we determine offline conditions necessary and sufficient to guarantee A-diagnosability and sufficient to guarantee AA-diagnosability. We also show how the stochastic diagnoser can be used for on-line diagnosis of failure events. We illustrate the results through two examples from HVAC systems.     

Learning behavior of stochastic automata in the last stage of learning

In this paper, a learning behavior of stochastic automata acting in an unknown random environment is considered. Especially, a learning behavior of stochastic automata in the last stage of learning is investigated. Using the theory of Stochastic Stability and Control [9], it is shown that there exists an upper bound of the probability with which stochastic automaton goes back to an unfavorable state within some finite time.     

State Observation and Diagnosis of Discrete-Event Systems Described by Stochastic Automata

The problems ofstate observation and diagnosis are solved for discrete–eventsystems, which are described by stochastic automata. As manysystems are not observable in the sense that it is possible toreconstruct the state unambiguously, the observation problemis set up as the problem of determining the smallest possibleset of states that are compatible with the measured input andoutput sequences. The diagnostic problem is shown to be, in principle,an observation problem. Conditions for the observability anddiagnosability of stochastic automata are presented. The resultsare illustrated by examples.     

On the definition of stochastic λ-transducers

We propose a formal definition for the general notion of stochastic transducer, called stochastic λ-transducer. Our definition is designed with two objectives in mind: (i) to extend naturally the established notion of stochastic automaton with output—as defined in the classic books of [A. Paz, Introduction to Probabilistic Automata, Academic Press, New York and London, 1971; P. Starke, Abstract Automata, North-Holland, Academic Press, 1972.]—by permitting pairs of input-output words of different lengths; (ii) to be compatible with the more general notion of weighted transducer so that one can apply tools of weighted transducers to address certain computational problems involving stochastic transducers. The new transducers can be used to model stochastic input-output processes that cannot be modelled using classical stochastic automata with output.     

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

Probabilistic Duration Calculus for Continuous Time

This paper deals with dependability of imperfect implementations concerning given requirements. The requirements are assumed to be written as formulas in Duration Calculus. Implementations are modelled by continuous semi-Markov processes with finite state space, which are expressed in the paper as finite automata with stochastic delays of state transitions. A probabilistic model for Duration Calculus formulas is introduced, so that the satisfaction probabilities of Duration Calculus formulas with respect to semi-Markov processes can be defined, reasoned about and calculated through a set of axioms and rules of the model. Received November 1994 / Accepted in revised form June 1998     

Complexity of weak acceptance conditions in tree automata

Weak acceptance conditions for automata on infinite words or trees are defined in terms of the set of states that appear in the run. This is in contrast with, more usual, strong conditions that are defined in terms of states appearing infinitely often on the run. Weak conditions appear in the context of model-checking and translations of logical formalisms to automata. We study the complexity of the emptiness problem for tree automata with weak conditions. We also study the translations between automata with weak and strong conditions.     

More on quantum,stochastic, and pseudo stochastic languages with few states

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.     

An analysis of the effect of the stochastic component of urban cellular automata models

Urban cellular automata models have proved useful tools in urban growth prediction because of their simplicity and their ability to reproduce complex emergent dynamics. Complex emergent dynamic systems involve processes that are difficult to predict, in which randomness plays a key role. In view of the fact that randomness is particularly relevant to complex processes, the aim of this paper is to analyze the sensitivity of the results of urban cellular automata models to the different methods used to incorporate the stochastic component in the models. The urban growth patterns obtained using different stochastic components are analyzed and compared using a number of spatial metrics. The results show that the differences observed in the simulated patterns are sufficiently relevant to justify the need for this type of analysis, which allows for the selection of the stochastic component that best suits the dynamics of the area.