Search

Aiming at the problem of permanent loss of system observations during the fault prediction of stochastic discrete-event systems ( SDESs), resulting in inaccurate predictions, this paper proposed an algorithm for verification of fault prediction under permanent loss of observations. Firstly, it formalized the notion of U-predictability of SDESs under permanent loss of observations. Secondly, it constructed a U-predictor from the given system using stochastic predictors to perform fault prediction of SDESs. Based on the U-predictor, it proposed a necessary and sufficient condition and an algorithm for verifying U-predictability of SDESs, and the introduction of a pairwise approach significantly improved the complexity of the verification algorithm. Simulation results show that the verification algorithm made the fault prediction of the system accurate under permanent loss of observations. Finally, an example illustrates the application of fault prediction verification algorithm under permanent loss of observations. Compared with the existing similar algorithm, the verification algorithm has a wider range of applications and the verification results are more accurate. [ABSTRACT FROM AUTHOR]

This work is a study of the class of non-deterministic automata on infinite trees that are unambiguous i.e. have at most one accepting run on every tree. The motivating question asks if the fact that an automaton is unambiguous implies some drop in the descriptive complexity of the language recognised by the automaton. As it turns out, such a drop occurs for the parity index and does not occur for the weak parity index. More precisely, given an unambiguous parity automaton 𝒜 of index (i , 2 j) , we show how to construct an alternating automaton T r a n s f o r m a t i o n (𝒜) which accepts the same language, but is simpler in terms of the acceptance condition. In particular, if 𝒜 is a Büchi automaton (i = 0 , j = 1) then T r a n s f o r m a t i o n (𝒜) is a weak alternating automaton. In general, T r a n s f o r m a t i o n (𝒜) belongs to the class comp (i + 1 , 2 j) , what implies that it is simultaneously of alternating index (i , 2 j) and of the dual index (i + 1 , 2 j + 1). The transformation algorithm is based on a separation procedure of Arnold and Santocanale (2005). In the case of non-deterministic automata with the weak parity condition, we provide a separation procedure analogous to the one used above. However, as illustrated by examples, this separation procedure cannot be used to prove a complexity drop in the weak case, as there is no such drop. [ABSTRACT FROM AUTHOR]

In this paper, a new estimation of distribution algorithm is introduced. The goal is to propose a method that avoids complex approximations of learning a probabilistic graphical model and considers multivariate dependencies between continuous random variables. A parallel model of some subgraphs with a smaller number of variables is learned as the probabilistic graphical model. In each generation, the joint probability distribution of the selected solutions is estimated using a Gaussian Mixture model. Then, learning the graphical model of dependencies among random variables and sampling are done separately for each Gaussian component. In the learning step, using the selected solutions of each Gaussian mixture component, the structure of a Markov network is learned. This network is decomposed to maximal cliques and a clique graph. Then, complete Bayesian network structures are learned for these subgraphs using an optimization algorithm. The proposed optimization problem is a 0–1 constrained quadratic programming which finds the best permutation of variables. Then, sampling is done from each Bayesian network of each Gaussian component. The introduced method is compared with the other network-based estimation of distribution algorithms for optimization of continuous numerical functions. [ABSTRACT FROM AUTHOR]

It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is and the nondeterministic state complexity of insertion is precisely , where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning. [ABSTRACT FROM AUTHOR]

In the context of probabilistic automata, time-efficient algorithms for simulation have been proposed lately. The space complexity thereof is quadratic in the size of the transition relation, thus space requirements often become the practical bottleneck. In this paper, we propose a space-efficient algorithm for computing simulation based on partition refinement. Experimental evidence is given showing that not only the space efficiency is improved drastically: The experiments often require orders of magnitude less time. In practice, they are even faster than the (asymptotically) optimal algorithm by Crafa and Ranzato (2012). [ABSTRACT FROM AUTHOR]

Multibiometric systems based on score fusion can effectively combine the discriminative power of multiple biometric traits and overcome the limitations of individual trait, leading to a better performance of biometric authentication. To tackle multiple adverse issues with the established classifier-based or probability-based algorithms, in this paper we propose a novel order-preserving probabilistic score fusion algorithm, Order-Preserving Tree (OPT), by casting the score fusion problem into an optimisation problem with the natural order-preserving constraint. OPT is an algorithm fully non-parametric and widely applicable, not assuming any parametric forms of probabilities or independence among sources, directly estimating the posterior probabilities from maximum likelihood estimation, and exploiting the power of tree-structured ensembles. We demonstrate the effectiveness of our OPT algorithm by comparing it with many widely used score fusion algorithms on two prevalent multibiometric databases. [ABSTRACT FROM AUTHOR]

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak Kőnig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak Kőnig's Lemma, but not to Weak Weak Kőnig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space. Besides Cantor space, we study the natural numbers, the Euclidean space and Baire space. [ABSTRACT FROM AUTHOR]

Robust controllers for nonlinear stochastic systems with functional uncertainties can be consistently designed using probabilistic control methods. In this paper a generalised probabilistic controller design for the minimisation of the Kullback–Leibler divergence between the actual joint probability density function (pdf) of the closed loop control system, and an ideal joint pdf is presented emphasising how the uncertainty can be systematically incorporated in the absence of reliable systems models. To achieve this objective all probabilistic models of the system are estimated from process data using mixture density networks (MDNs) where all the parameters of the estimated pdfs are taken to be state and control input dependent. Based on this dependency of the density parameters on the input values, explicit formulations to the construction of optimal generalised probabilistic controllers are obtained through the techniques of dynamic programming and adaptive critic methods. Using the proposed generalised probabilistic controller, the conditional joint pdfs can be made to follow the ideal ones. A simulation example is used to demonstrate the implementation of the algorithm and encouraging results are obtained. [ABSTRACT FROM AUTHOR]

Probabilistic automata constitute a versatile and elegant model for concurrent probabilistic systems. They are equipped with a compositional theory supporting abstraction, enabled by weak probabilistic bisimulation serving as the reference notion for summarising the effect of abstraction. This paper considers probabilistic automata augmented with costs. It extends the notions of weak transitions in probabilistic automata in such a way that the costs incurred along a weak transition are captured. This gives rise to cost-preserving and cost-bounding variations of weak probabilistic bisimilarity, for which we establish compositionality properties with respect to parallel composition. Furthermore, polynomial-time decision algorithms are proposed, that can be effectively used to compute reward-bounding abstractions of Markov decision processes in a compositional manner. [ABSTRACT FROM AUTHOR]

In this paper, a new structure for cooperative learning automata called extended learning automata (eDLA) is introduced. Based on the new structure, an iterative randomized heuristic algorithm using sampling is proposed for finding an optimal subgraph in a stochastic edge-weighted graph. Stochastic graphs are graphs in which the weights of edges have an unknown probability distribution. The proposed algorithm uses an eDLA to find a policy that leads to a subgraph that satisfy some restrictions such as minimum or maximum weight (length). At each stage of the proposed algorithm, the eDLA determines which edges should be sampled. The proposed eDLA-based sampling method may reduce unnecessary samples and hence decrease the time required for finding an optimal subgraph. It is shown that the proposed method converges to an optimal solution, the probability of which can be made arbitrarily close to 1 by using a sufficiently small learning parameter. A new variance-aware threshold value is also proposed that can significantly improve the convergence rate of the proposed eDLA-based algorithm. It is further shown that our algorithm is competitive in terms of the quality of the solution. [ABSTRACT FROM AUTHOR]

This paper studies a difference operator for stochastic systems whose specifica-tions are represented by Abstract Probabilistic Automata (APAs). In the case refinement fails between two specifications, the target of this operator is to produce a specification APA that represents all witness PAs of this failure. Our contribution is an algorithm that permits to approximate the difference of two deterministic APAs with arbitrary precision. Our technique relies on new quantitative notions of distances between APAs used to assess convergence of the approximations, as well as on an in-depth inspection of the refinement relation for APAs. The procedure is effective and not more complex than refinement checking. [ABSTRACT FROM AUTHOR]

Markovian models with hidden state are widely-used formalisms for modeling sequential phenomena. Learnability of these models has been well studied when the sample is given in batch mode, and algorithms with PAC-like learning guarantees exist for specific classes of models such as Probabilistic Deterministic Finite Automata (PDFA). Here we focus on PDFA and give an algorithm for inferring models in this class in the restrictive data stream scenario: Unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We also present extensions of the algorithm that (1) reduce to a minimum the need for guessing parameters of the target distribution and (2) are able to adapt to changes in the input distribution, relearning new models when needed. We provide rigorous PAC-like bounds for all of the above. Our algorithm makes a key usage of stream sketching techniques for reducing memory and processing time, and is modular in that it can use different tests for state equivalence and for change detection in the stream. [ABSTRACT FROM AUTHOR]

Probabilistic computations and frequency computations were invented for the same purpose, namely, to study possible advantages of technology involving random choices. Recently several authors have discovered close relationships of these generalizations of deterministic computations to computations taking advice. Various forms of computation taking advice were studied by Karp and Lipton [1], Damm and Holzer [2], and Freivalds [3]. In the present paper, we apply the nonconstructive, probabilistic, and frequency methods to an inductive inference paradigm originally due to Gold [4] and investigate their impact on the resulting learning models. Several trade-offs with respect to the resulting learnability are shown. [ABSTRACT FROM AUTHOR]

In this letter, the computational power of a class of random access memory (RAM)-based neural networks, called general single-layer sequential weightless neural networks (GSSWNNs), is analyzed. The theoretical results presented, besides helping the understanding of the temporal behavior of these networks, could also provide useful insights for the developing of new learning algorithms. Index Terms--Automata theory, computability, p random access memory (RAM) node, probabilistic automata, RAM-based neural networks, weightless neural networks (WNNs).

Abstract: Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed -queries is defined. We show how to simulate -queries using classical Statistical Queries and show that known PAC algorithms for learning PDFA are in fact statistical query algorithms. Our results include a lower bound: every algorithm to learn PDFA with queries using a reasonable tolerance must make queries for every . Finally, an adaptive algorithm that PAC-learns w.r.t. another measure of complexity is described. This yields better efficiency in many cases, while retaining the same inevitable worst-case behavior. Our algorithm requires fewer input parameters than previously existing ones, and has a better sample bound. [Copyright &y& Elsevier]

In this article a generic method for fault detection and isolation (FDI) in manufacturing systems considered as discrete event systems (DES) is presented. The method uses an identified model of the closed-loop of plant and controller built on the basis of observed fault-free system behaviour. An identification algorithm known from literature is used to determine the fault detection model in form of a non-deterministic automaton. New results of how to parameterise this algorithm are reported. To assess the fault detection capability of an identified automaton, probabilistic measures are proposed. For fault isolation, the concept of residuals adapted for DES is used by defining appropriate set operations representing generic fault symptoms. The method is applied to a case study system. [ABSTRACT FROM PUBLISHER]

We prove that the average complexity of Moore's state minimization algorithm is $\mathcal {O}(kn\log n)$, where n is the number of states of the input and k the size of the alphabet. This result holds for a whole family of probabilistic models on automata, including the uniform distribution over deterministic and accessible automata, as well as uniform distributions over classical subclasses, such as complete automata, acyclic automata, automata where each state is final with probability γ∈(0,1), and many other variations. [ABSTRACT FROM AUTHOR]

Abstract: An alternative to deploying a single robot of high complexity can be to utilise robot swarms comprising large numbers of identical, and much simpler, robots. Such swarms have been shown to be adaptable, fault-tolerant and widely applicable. However, designing individual robot algorithms to ensure effective and correct overall swarm behaviour is actually very difficult. While mechanisms for assessing the effectiveness of any swarm algorithm before deployment are essential, such mechanisms have traditionally involved either computational simulations of swarm behaviour, or experiments with robot swarms themselves. However, such simulations or experiments cannot, by their nature, analyse all possible swarm behaviours. In this paper, we will develop and apply the use of automated probabilistic formal verification techniques to robot swarms, involving an exhaustive mathematical analysis, in order to assess whether swarms will indeed behave as required. In particular we consider a foraging robot scenario to which we apply probabilistic model checking. [Copyright &y& Elsevier]

We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we develop an algorithm that efficiently computes the distribution of a pattern matching algorithm's running time cost (such as the number of text character accesses) for any given pattern in a random text model. Text models range from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide an algorithm to compute the exact distribution of differences in running time cost of two pattern matching algorithms. Methodologically, we use extensions of finite automata which we call deterministic arithmetic automata (DAAs) and probabilistic arithmetic automata (PAAs). Given an algorithm, a pattern, and a text model, a PAA is constructed from which the sought distributions can be derived using dynamic programming. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly by computing the whole distribution of running time cost. Experimentally, we compare Horspool's algorithm, Backward DAWG Matching, and Backward Oracle Matching on prototypical patterns of short length and provide statistics on the size of minimal DAAs for these computations. [ABSTRACT FROM AUTHOR]

Abstract: We study abstract interpretations of a fixpoint protoderivation semantics defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms. [Copyright &y& Elsevier]

Abstract: Due to the hardness of solving the minimum spanning tree (MST) problem in stochastic environments, the stochastic MST (SMST) problem has not received the attention it merits, specifically when the probability distribution function (PDF) of the edge weight is not a priori known. In this paper, we first propose a learning automata-based sampling algorithm (Algorithm 1) to solve the MST problem in stochastic graphs where the PDF of the edge weight is assumed to be unknown. At each stage of the proposed algorithm, a set of learning automata is randomly activated and determines the graph edges that must be sampled in that stage. As the proposed algorithm proceeds, the sampling process focuses on the spanning tree with the minimum expected weight. Therefore, the proposed sampling method is capable of decreasing the rate of unnecessary samplings and shortening the time required for finding the SMST. The convergence of this algorithm is theoretically proved and it is shown that by a proper choice of the learning rate the spanning tree with the minimum expected weight can be found with a probability close enough to unity. Numerical results show that Algorithm 1 outperforms the standard sampling method. Selecting a proper learning rate is the most challenging issue in learning automata theory by which a good trade off can be achieved between the cost and efficiency of algorithm. To improve the efficiency (i.e., the convergence speed and convergence rate) of Algorithm 1, we also propose four methods to adjust the learning rate in Algorithm 1 and the resultant algorithms are called as Algorithm 2 through Algorithm 5. In these algorithms, the probabilistic distribution parameters of the edge weight are taken into consideration for adjusting the learning rate. Simulation experiments show the superiority of Algorithm 5 over the others. To show the efficiency of Algorithm 5, its results are compared with those of the multiple edge sensitivity method (MESM). The obtained results show that Algorithm 5 performs better than MESM both in terms of the running time and sampling rate. [Copyright &y& Elsevier]

Abstract: A novel approach based on probability and randomization has emerged to synergize with the standard deterministic methods for control of systems with uncertainty. The main objective of this paper is to provide a broad perspective on this area of research known as “probabilistic robust control”, and to address in a systematic manner recent advances. The focal point is on design methods, based on the interplay between uncertainty randomization and convex optimization, and on the illustration of specific control applications. [Copyright &y& Elsevier]

Many researchers have looked into the question of whether or not PSPACE (P) is a proper subset of NPSPACE (NP); however, very few researchers have looked into how the nature of the answer A to a problem P influences the structural characteristics of the automata required to generate A for P. As such, that is the nature of the investigation that we wish to present here. First, we take a generic automaton M that can be utilized to solve any given problem P. We then utilize the acceptable words ι for M to construct a Σ-tree t representation of the input to M with a corresponding Q-tree q, over our set Q of states for M, representing M's response to t. q is then utilized to construct a Bayesian game GB over a set G of component Markov games GM that models the behavior of M; where the component games GM represent the algorithms that can be implemented upon M. We then analyze the structure of our component Markov games with respect to deterministic and nondeterministic automata. During this analysis we show that Markov games representing deterministic automata derive their uncertainty, or the probability distribution over their set of pure strategies, from the uncertainty associated with which problem instance ιa will be applied to M during a given instantiation ra. Conversely and by necessity, nondeterministic automata contain an uncertainty that is not directly associated with our problem instance ιa. This suggests that we can prove that P⊂NP if we can define a problem P that requires a component of uncertainty that cannot be attributed to our problem instance, or input sequence ιa. With this in mind, we pose the question of solving for a perfectly random set of perfectly random numbers as an example of a problem that requires an innately stochastic answer. Finally, we demonstrate that the existence of problems with stochastic answers suggests that PSPACE is in fact a proper subset of NPSPACE. [ABSTRACT FROM AUTHOR]

Based on classical rough set approximations, the LERS (Learning from Examples based on Rough Sets) data mining system induces two types of rules, namely, certain rules from lower approximations and possible rules from upper approximations. By relaxing the stringent requirement of the classical rough sets, one can obtain probabilistic approximations. The LERS can be easily applied to induce probabilistic positive and boundary rules from probabilistic positive and boundary regions. This paper discusses several fundamental issues related to probabilistic rule induction with LERS, including rule induction algorithm, quantitative measures associated with rules, and the rule conflict resolution method. © 2011 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

The problem of automatic classification of scientific texts is considered. Methods based on statistical analysis of probabilistic distributions of scientific terms in texts are discussed. The procedures for selecting the most informative terms and the method of making use of auxiliary information related to the terms positions are presented. The results of experimental evaluation of proposed algorithms and procedures over real-world data are reported. [ABSTRACT FROM AUTHOR]

Abstract: We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size n that halts in time with probability Each message containing 1 bit, its bit complexity per channel is . From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree and size n that uses at most colours and halts in time with probability We also obtain a partition algorithm for arbitrary graphs of size n that builds a spanning forest in time with probability . We study some parameters such as the number, the size and the radius of trees of the spanning forest. [Copyright &y& Elsevier]

Abstract: The task of the robot in localization is to find out where it is, through sensing and motion. In environments which possess relatively few features that enable a robot to unambiguously determine its location, global localization algorithms can result in ‘multiple hypotheses’ locations of a robot. This is inevitable with global localization algorithms, as the local environment seen by a robot repeats at other parts of the map. Thus, for effective localization, the robot has to be actively guided to those locations where there is a maximum chance of eliminating most of the ambiguous states — which is often referred to as ‘active localization’. When extended to multi-robotic scenarios where all robots possess more than one hypothesis of their position, there is an opportunity to do better by using robots, apart from obstacles, as ‘hypotheses resolving agents’. The paper presents a unified framework which accounts for the map structure as well as measurement amongst robots, while guiding a set of robots to locations where they can singularize to a unique state. The strategy shepherds the robots to places where the probability of obtaining a unique hypothesis for a set of multiple robots is a maximum. Another aspect of framework demonstrates the idea of dispatching localized robots to locations where they can assist a maximum of the remaining unlocalized robots to overcome their ambiguity, named as ‘coordinated localization’. The appropriateness of our approach is demonstrated empirically in both simulation & real-time (on Amigo-bots) and its efficacy verified. Extensive comparative analysis portrays the advantage of the current method over others that do not perform active localization in a multi-robotic sense. It also portrays the performance gain by considering map structure and robot placement to actively localize over methods that consider only one of them or neither. Theoretical backing stems from the proven completeness of the method for a large category of diverse environments. [Copyright &y& Elsevier]

Learning automata are adaptive decision making devices that are found useful in a variety of machine learning and pattern recognition applications. Although most learning automata methods deal with the case of finitely many actions for the automaton, there are also models of continuous-action-set learning automata (CALA). A team of such CALA can be useful in stochastic optimization problems where one has access only to noise-corrupted values of the objective function. In this paper, we present a novel formulation for noise-tolerant learning of linear classifiers using a CALA team. We consider the general case of nonuniform noise, where the probability that the class label of an example is wrong may be a function of the feature vector of the example. The objective is to learn the underlying separating hyperplane given only such noisy examples. We present an algorithm employing a team of CALA and prove, under some conditions on the class conditional densities, that the algorithm achieves noise-tolerant learning as long as the probability of wrong label for any example is less than 0.5. We also present some empirical results to illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the NP-hard problem of object assignment with respect to multiple constraints: assigning a set of elements (or objects) into mutually exclusive classes (or groups), where the elements which are "similar" to each other are hopefully located in the same class. The literature reports solutions in which the similarity constraint consists of a single index that is inappropriate for the type of multiconstraint problems considered here and where the constraints could simultaneously be contradictory. Such a scenario is illustrated with the static mapping problem, which consists of distributing the processes of a parallel application onto a set of computing nodes. This is a classical and yet very important problem within the areas of parallel computing, grid computing, and cloud computing. We have developed four learning-automata (LA)-based algorithms to solve this problem: First, a fixed-structure stochastic automata algorithm is presented, where the processes try to form pairs to go onto the same node. This algorithm solves the problem, although it requires some centralized coordination. As it is desirable to avoid centralized control, we subsequently present three different variable-structure stochastic automata (VSSA) algorithms, which have superior partitioning properties in certain settings, although they forfeit some of the scalability features of the fixed-structure algorithm. All three VSSA algorithms model the processes as automata having first the hosting nodes as possible actions; second, the processes as possible actions; and, third, attempting to estimate the process communication digraph prior to probabilistically mapping the processes. This paper, which, we believe, comprehensively reports the pioneering LA solutions to this problem, unequivocally demonstrates that LA can play an important role in solving complex combinatorial and integer optimization problems. [ABSTRACT FROM AUTHOR]

Model checking for large-scale systems is extremely difficult due to the state explosion problem. Creating useful abstractions for model checking task is a challenging problem, often involving many iterations of refinement. In this paper we consider techniques for model checking in the counterexample-guided abstraction refinement. The state separation problem is one popular approach in counterexample-guided abstraction refinement, and it poses the main hurdle during the refinement process. To achieve effective minimization of the separation set, we present a novel probabilistic learning approach based on the sample learning technique, evolutionary algorithm, and effective heuristics. We integrate it with the abstraction refinement framework in the VIS [1] model checker. We include experimental results on model checking to compare our new approach to recently published techniques. The benchmark results show that our approach has overall speedup of more than 56 percent against previous techniques. Our work is the first successful integration of evolutionary algorithm and abstraction refinement for model checking. [ABSTRACT FROM AUTHOR]

WiMAX (Worldwide Interpretability for Microwave Access) is one of the leader standards of broadband Wireless Access (BWA). This standard becomes a competitor of 4G or LTE (Long Terme Evolution) with the introduction of different class of service flow (UGS, rtPS, nrtPS, BE). Each service class has its own QoS requirements. Even if the standard specify the transmission policy of each service class, it recommends the implementation of an admission control (AC) without any specification. This task is let to the operator. In this paper, we propose an implementation of an AC algorithm mechanism for IEEE 802.16. The performance evaluation of these networks by analytical models is not easy due to the state space explosion, thus we use the Stochastic Automata Networks (SAN) formalism to model our proposed AC mechanism. With the SAN we calculate the rewards of the proposed AC and we show that the proposed solution is efficient. [ABSTRACT FROM AUTHOR]

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio. We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions such amorphous computing systems can possess universal computing power with a high probability. The underlying theory makes use of properties of random graphs and that of probabilistic analysis of algorithms. To the best of our knowledge this is the first result showing the universality of such computing systems. [ABSTRACT FROM AUTHOR]

Abstract: Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs and with and states, respectively, are equivalent iff they are -equivalent [L.Z. Li, D.W. Qiu, Determination of equivalence between quantum sequential machines, Theoretical Computer Science 358 (2006) 65–74]. However, using this result to check the equivalence is likely to need exponential expected time. In this note, we consider the time complexity of deciding the equivalence between QSMs and related problems. The main results are as follows: (1) We present a polynomial-time algorithm for deciding the equivalence between QSMs, and, if two QSMs are not equivalent, this algorithm will produce an input–output pair with length not more than . (2) We improve the bound for the equivalence between QSMs from to , by employing Moore and Crutchfield’s method [C. Moore, J.P. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science 237 (2000) 275–306. Also quant-ph/9707031, 1997]. In addition, by viewing MO-1QFAs as a special case of QSMs, we briefly discuss the equivalence between MO-1QFAs, where the method used and the result obtained are slightly different from those given by Koshiba [T. Koshiba, Polynomial-time algorithms for the equivalence for one-way quantum finite automata, in: Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC’2001, Christchurch, New Zealand, in: Lecture Notes in Computer Science, vol. 2223, Springer, Berlin, 2001, pp. 268–278]. [Copyright &y& Elsevier]

A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. To reason about data words, linear temporal logic is extended by the freeze quantifier, which stores the element at the current word position into a register, for equality comparisons deeper in the formula. By translations from the logic to alternating automata with registers and then to faulty counter automata whose counters may erroneously increase at any time, and from faulty and error-free counter automata to the logic, we obtain a complete complexity table for logical fragments defined by varying the set of temporal operators and the number of registers. In particular, the logic with future-time operators and 1 register is decidable but not primitive recursive over finite data words. Adding past-time operators or 1 more register, or switching to infinite data words, causes undecidability. [ABSTRACT FROM AUTHOR]

During the past decade, sequential pattern mining has been the core of numerous research efforts. It is now possible to efficiently extract knowledge of users’ behavior from a huge set of sequences collected over time. This has applications in various domains such as purchases in supermarkets, Web site visits, etc. However, sequence mining algorithms do little to control the risks of extracting false discoveries or overlooking true knowledge. In this paper, the theoretical conditions to achieve a relevant sequence mining process are examined. Then, the article offers a statistical view of sequence mining which has the following advantages: First, it uses a compact and generalized representation of the original sequences in the form of a probabilistic automaton. Second, it integrates statistical constraints to guarantee the extraction of significant patterns. Finally, it provides an interesting solution in a privacy preserving context in order to respect individuals’ information. An application in car flow modeling is presented, showing the ability of our algorithm ( acsm) to discover frequent routes without any private information. Comparisons with a classical sequence mining algorithm ( spam) are made, showing the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the behavioral pseudometrics for probabilistic systems, which are a quantitative analogue of probabilistic bisimilarity in the sense that the distance zero captures the probabilistic bisimilarity. The model we are interested in is probabilistic automata, which are based on state transition systems and make a clear distinction between probabilistic and nondeterministic choices. The pseudometrics are defined as the greatest fixpoint of a monotonic functional on the complete lattice of state metrics. A distinguished characteristic of this pseudometric lies in that it does not discount the future, which addresses some algorithmic challenges to compute the distance of two states in the model. We solve this problem by providing an approximation algorithm: up to any desired degree of accuracy , the distance can be approximated to within in time exponential in the size of the model and logarithmic in . One of the key ingredients of our algorithm is to express a pseudometric being a post-fixpoint as the elementary sentence over real closed fields, which allows us to exploit Tarski’s decision procedure, together with the binary search to approximate the behavioral distance. [Copyright &y& Elsevier]

In this paper, a probability-based balance monitoring concept for humanoid robots is proposed. Two algorithms are presented that allow us to distinguish between exceptional situations and normal operations. The first classification approach uses Gaussian-Mixture- Models (GMM) to describe the distribution of the robot's sensor data for typical situations such as stable walking or falling down. With the GMM it is possible to state the probability of the robot being in one of the known situations. The concept of the second algorithm is based on Hidden-Markov-Models (HMM). The objective is to detect and classify unstable situations by means of their typical sequences in the robot's sensor data. When appropriate reflex motions are linked to the critical situations, the robot can prevent most falls or is at least able to execute a controlled falling motion. The proposed algorithms are verified by simulations and experiments with our bipedal robot BARt-UH. [ABSTRACT FROM AUTHOR]

Abstract: Regular expressions and their extensions have become a major component of industry-oriented specification languages such as IEEE PSL [IEEE Standard for Property Specification Language (PSL). IEEE Std 1850™-2005]. The model checking procedure of regular expression based formulas, involves constructing an automaton which runs in parallel with the model. In this paper we re-examine the automata construction. We propose an algorithm that allows an intermediate representation mixing both regular expressions and automata. This representation can be thought of as plugging an automaton inside a regular expression, to replace an existing sub-expression. In order to be verified, the intermediate representation is then translated into another automaton, resulting in a set of automata running in parallel. A key feature of this algorithm is that the plug-in automaton is independent of the regular expression from which it originated, and thus can be used in several different properties. We demonstrate the usefulness of our method by providing a set of applications. We show how the use of our method allows modularity and flexibility of the automata construction, and can increase expressiveness when seres are mixed with ctl. We give two applications for which it significantly reduces the size of the automata built for formulas, thus reducing the overall run time of the model checking procedure. [Copyright &y& Elsevier]

This article proposes a flexible and distributed stochastic automaton-based network partitioning algorithm that is capable of finding the optimal k-way partition with respect to a broad range of cost functions, and given various constraints, in directed and weighted graphs. Specifically, we motivate the distributed partitioning (self-partitioning) problem, introduce the stochastic automaton-based partitioning algorithm, and show that the algorithm finds the optimal partition with probability 1 for a large class of partitioning tasks. Also, a discussion of why the algorithm can be expected to find good partitions quickly is included, and its performance is further illustrated through examples. Finally, applications to mobile/sensor classification in ad hoc networks, fault-isolation in electric power systems, and control of autonomous vehicle teams are pursued in detail. [ABSTRACT FROM AUTHOR]

We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time. [ABSTRACT FROM AUTHOR]

We present an exhaustive analysis of the problem of computing the relative entropy of two probabilistic automata. We show that the problem of computing the relative entropy of unambiguous probabilistic automata can be formulated as a shortest-distance problem over an appropriate semiring, give efficient exact and approximate algorithms for its computation in that case, and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. We also prove that the computation of the relative entropy of arbitrary probabilistic automata is PSPACE-complete. The relative entropy is used in a variety of machine learning algorithms and applications to measure the discrepancy of two distributions. We examine the use of the symmetrized relative entropy in machine learning algorithms and show that, contrarily to what is suggested by a number of publications in that domain, the symmetrized relative entropy is neither positive definite symmetric nor negative definite symmetric, which limits its use and application in kernel methods. In particular, the convergence of training for learning algorithms is not guaranteed when the symmetrized relative entropy is used directly as a kernel, or as the operand of an exponential as in the case of Gaussian Kernels. Finally, we show that our algorithm for the computation of the entropy of an unambiguous probabilistic automaton can be generalized to the computation of the norm of an unambiguous probabilistic automaton by using a monoid morphism. In particular, this yields efficient algorithms for the computation of the Lp-norm of a probabilistic automaton. [ABSTRACT FROM AUTHOR]

Abstract  The convergence of fast probabilistic modeling algorithms (G-algorithms) is analyzed. A G-algorithm is modified based on a new probabilistic approach, used to reject points in the neighborhood of the current solution. A theoretically justified estimate of the rate of convergence, independent of the initial approximation, is obtained for this modification. A computational experiment is conducted to compare the performance of the modified G-algorithm with that of the classical one. [ABSTRACT FROM AUTHOR]

In this paper the problem of tracking multiple spawning targets with multiple finite-resolution sensors is considered and a new algorithm for measurement-to-track association with possibly unresolved measurements is presented. The goal is to initialize new tracks of spawned targets before they are resolved from the mother platform so that one has the ability to carry out early discrimination when they become resolved. The multiple scan data association problem is first formulated as a multidimensional assignment problem with explicit new constraints for the unresolved measurements. Then the top M hypotheses tracking (TMHT) is presented where the state estimates and their covariances are modified based on the M best hypotheses through the assignment solutions. A modification to the assignment problem is developed that leads to a linear programming (LP) where the optimal solution can be a noninteger in [0,1]. The fractional optimal solution is interpreted as (pseudo) probabilities over the N - 1 frame sliding window. The best hard (binary) decision assignment solution and the M best via TMHT are compared with the soft decision solution for 2-D tracking scenarios with various sensor configurations. Based on the simulation results, the soft assignment approach has better track maintenance capability than the single best hard assignment and a performance nearly as good as the TMHT. Its computational load is slightly higher than the single best hard assignment but much lighter than TMHT. [ABSTRACT FROM AUTHOR]

We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-search machinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF's techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF shows its fine scalability in a range of probabilistic domains, constituting a several orders of magnitude improvement over previous results in this area. We use a problematic case to point out the main open issue to be addressed by further research. [ABSTRACT FROM AUTHOR]

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the number of communication rounds needed to achieve a global decision, i.e., for all nonfaulty (correct) processes to reach a decision. This paper studies the time-complexity of local decisions in agreement problems, which we define as the number of communication rounds needed for at least one correct process to decide. We explore bounds for early local decision that depend on the number f of actual failures (that occur in a given run of an algorithm), out of the maximum number t of failures tolerated (by the algorithm). We first consider the synchronous message-passing model where we give tight local decision bounds for three variants of agreement: consensus, uniform consensus, and (nonblocking) atomic commit. We use these results to (1) show that, for consensus, local decision bounds are not compatible with global decision bounds (roughly speaking, they cannot be reached by the same algorithm), and (2) draw the first sharp line between the time-complexity of uniform consensus and atomic commit. Then we consider the eventually synchronous model, where we give tight local decision bounds for synchronous runs of uniform consensus. (In this model, consensus and uniform consensus are similar, atomic commit is impossible, and one cannot bound the number of rounds to reach a decision in nonsynchronous runs of consensus algorithms.) We prove a counterintuitive result that the early local decision bound is the same as the early global decision bound. We also give a matching early deciding consensus algorithm that is significantly better than previous eventually synchronous consensus algorithms. [ABSTRACT FROM AUTHOR]

This paper presents an exhaustive analysis of the problem of computing the Lp distance of two probabilistic automata. It gives efficient exact and approximate algorithms for computing these distances for p even and proves the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. It further proves the hardness of approximating the Lp distance of two probabilistic automata for odd values of p. Similar techniques to those used for computing the Lp distance also yield efficient algorithms for computing the Hellinger distance of two unambiguous probabilistic automata both exactly and approximately. A problem closely related to the computation of a distance between probabilistic automata is that of testing their equivalence. This paper also describes an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A1 and A2 in time O(|Σ|(|A1| + |A2|)3), a significant improvement over the previously best reported algorithm for this problem. [ABSTRACT FROM AUTHOR]

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders. Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures. [ABSTRACT FROM AUTHOR]

We study the dynamics of patterns exhibited by rule 52, a totalistic cellular automaton displaying intricate behaviors and wide regions of active/inactive synchronization patches. Systematic computer simulations involving 230 initial configurations reveal that all complexity in this automaton originates from random juxtaposition of a very small number of interfaces delimiting active/inactive patches. Such interfaces are studied with a sidewise spatial updating algorithm. This novel tool allows us to prove that the interfaces found empirically are the only interfaces possible for these periods, independently of the size of the automata. The spatial updating algorithm provides an alternative way to determine the dynamics of automata of arbitrary size, a way of taking into account the complexity of the connections in the lattice. [ABSTRACT FROM AUTHOR]