Log in

Relevant bibliographies by topics / Probabilistic automaton / Journal articles

To see the other types of publications on this topic, follow the link: Probabilistic automaton.

Journal articles on the topic 'Probabilistic automaton'

Author: Grafiati

Published: 30 May 2022

Last updated: 31 May 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Probabilistic automaton.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Sánchez, Joan Andreu, Martha Alicia Rocha, Verónica Romero, and Mauricio Villegas. "On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models." Computational Linguistics 44, no. 1 (March 2018): 17–37. http://dx.doi.org/10.1162/coli_a_00306.

Full text

Abstract:

Probabilistic finite-state automata are a formalism that is widely used in many problems of automatic speech recognition and natural language processing. Probabilistic finite-state automata are closely related to other finite-state models as weighted finite-state automata, word lattices, and hidden Markov models. Therefore, they share many similar properties and problems. Entropy measures of finite-state models have been investigated in the past in order to study the information capacity of these models. The derivational entropy quantifies the uncertainty that the model has about the probability distribution it represents. The derivational entropy in a finite-state automaton is computed from the probability that is accumulated in all of its individual state sequences. The computation of the entropy from a weighted finite-state automaton requires a normalized model. This article studies an efficient computation of the derivational entropy of left-to-right probabilistic finite-state automata, and it introduces an efficient algorithm for normalizing weighted finite-state automata. The efficient computation of the derivational entropy is also extended to continuous hidden Markov models.

APA, Harvard, Vancouver, ISO, and other styles

2

CORTES, CORINNA, MEHRYAR MOHRI, ASHISH RASTOGI, and MICHAEL RILEY. "ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA." International Journal of Foundations of Computer Science 19, no. 01 (February 2008): 219–42. http://dx.doi.org/10.1142/s0129054108005644.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

BOCCARA, N., J. NASSER, and M. ROGER. "CRITICAL BEHAVIOR OF A PROBABILISTIC LOCAL AND NONLOCAL SITE-EXCHANGE CELLULAR AUTOMATON." International Journal of Modern Physics C 05, no. 03 (June 1994): 537–45. http://dx.doi.org/10.1142/s0129183194000714.

Full text

Abstract:

We study the critical behavior of a probabilistic automata network whose local rule consists of two subrules. The first one, applied synchronously, is a probabilistic one-dimensional range-one cellular automaton rule. The second, applied sequentially, exchanges the values of a pair of sites. According to whether the two sites are first-neighbors or not, the exchange is said to be local or nonlocal. The evolution of the system depends upon two parameters, the probability p characterizing the probabilistic cellular automaton, and the degree of mixing m resulting from the exchange process. Depending upon the values of these parameters, the system exhibits a bifurcation similar to a second order phase transition characterized by a nonnegative order parameter, whose role is played by the stationary density of occupied sites. When m is very large, the correlations created by the application of the probabilistic cellular automaton rule are destroyed, and, as expected, the behavior of the system is then correctly predicted by a mean-field-type approximation. According to whether the exchange of the site values is local or nonlocal, the critical behavior is qualitatively different as m varies.

APA, Harvard, Vancouver, ISO, and other styles

4

Rajewsky, Nikolaus, and Michael Schreckenberg. "A Probabilistic Cellular Automaton for Evolution." Journal de Physique I 5, no. 9 (September 1995): 1129–34. http://dx.doi.org/10.1051/jp1:1995186.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Nishidate, Kazume, Mamoru Baba, Hideyuki Chiba, Takanori Ito, Kouichi Kodama, and Kiyoshi Nishikawa. "Probabilistic Cellular Automaton for Random Walkers." Journal of the Physical Society of Japan 69, no. 5 (May 15, 2000): 1352–55. http://dx.doi.org/10.1143/jpsj.69.1352.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

FREIVALDS, RŪSIŅŠ. "NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA." International Journal of Foundations of Computer Science 19, no. 03 (June 2008): 565–80. http://dx.doi.org/10.1142/s0129054108005826.

Full text

Abstract:

Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. However, the proof is non-constructive. The result is presented in two versions. The first version depends on Artin's Conjecture (1927) in Number Theory. The second version does not depend on conjectures not proved but the numerical estimates are worse. In both versions the method of the proof does not allow an explicit description of the languages used. Since our finite probabilistic automata are reversible, these results imply a similar result for quantum finite automata.

APA, Harvard, Vancouver, ISO, and other styles

7

BHATTACHARYYA, PRATIP. "GROWTH OF SURFACES GENERATED BY A PROBABILISTIC CELLULAR AUTOMATION." International Journal of Modern Physics C 10, no. 01 (February 1999): 165–81. http://dx.doi.org/10.1142/s0129183199000115.

Full text

Abstract:

A one-dimensional cellular automaton with a probabilistic evolution rule can generate stochastic surface growth in (1+1) dimensions. Two such discrete models of surface growth are constructed from a probabilistic cellular automaton which is known to show a transition from an active phase to an absorbing phase at a critical probability associated with two particular components of the evolution rule. In one of these models, called Model A in this paper, the surface growth is defined in terms of the evolving front of the cellular automaton on the space-time plane. In the other model, called Model B, surface growth takes place by a solid-on-solid deposition process controlled by the cellular automaton configurations that appear in successive time-steps. Both the models show a depinning transition at the critical point of the generating cellular automaton. In addition, Model B shows a kinetic roughening transition at this point. The characteristics of the surface width in these models are derived by scaling arguments from the critical properties of the generating cellular automaton and by Monte Carlo simulations.

APA, Harvard, Vancouver, ISO, and other styles

8

Bušić, Ana, Jean Mairesse, and Irène Marcovici. "Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling." Advances in Applied Probability 45, no. 04 (December 2013): 960–80. http://dx.doi.org/10.1017/s0001867800006728.

Full text

Abstract:

A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a one-dimensional cellular automaton, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to also be a PCA. Last, we focus on the PCA majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.

APA, Harvard, Vancouver, ISO, and other styles

9

Bušić, Ana, Jean Mairesse, and Irène Marcovici. "Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling." Advances in Applied Probability 45, no. 4 (December 2013): 960–80. http://dx.doi.org/10.1239/aap/1386857853.

Full text

Abstract:

A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a one-dimensional cellular automaton, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to also be a PCA. Last, we focus on the PCA majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.

APA, Harvard, Vancouver, ISO, and other styles

10

Nederhof, Mark-Jan. "A General Technique to Train Language Models on Language Models." Computational Linguistics 31, no. 2 (June 2005): 173–85. http://dx.doi.org/10.1162/0891201054223986.

Full text

Abstract:

We show that under certain conditions, a language model can be trained on the basis of a second language model. The main instance of the technique trains a finite automaton on the basis of a probabilistic context-free grammar, such that the Kullback-Leibler distance between grammar and trained automaton is provably minimal. This is a substantial generalization of an existing algorithm to train an n-gram model on the basis of a probabilistic context-free grammar.

APA, Harvard, Vancouver, ISO, and other styles

11

Nakanishi, Masaki. "Quantum Pushdown Automata with Garbage Tape." International Journal of Foundations of Computer Science 29, no. 03 (April 2018): 425–46. http://dx.doi.org/10.1142/s0129054118500132.

Full text

Abstract:

Several kinds of quantum pushdown automata models have been proposed, and their computational power has been investigated intensively. However, for some quantum pushdown automaton models, it is unknown whether quantum models are at least as powerful as their classical counterparts or not. This is due to the reversibility restriction. In this paper, we introduce a new quantum pushdown automaton model that has a garbage tape. This model can overcome the reversibility restriction by exploiting the garbage tape to store popped symbols. We show that the proposed model can simulate any quantum pushdown automaton with classical stack as well as any probabilistic pushdown automaton. We also show that our model can solve a certain promise problem exactly while deterministic pushdown automata cannot. These results imply that our model is strictly more powerful than its classical counterparts in the setting of exact, one-sided error and non-deterministic computation. Showing impossibility for a promise problem is a difficult task in general. However, by analyzing the behavior of a deterministic pushdown automaton carefully, we obtained the impossibility result. This is one of the main contributions of the paper.

APA, Harvard, Vancouver, ISO, and other styles

12

Котовенко, Олена Андріївна, Олена Юріївна Мірошниченко, Юлія Олегівна Березницька, and Юлія Володимирівна Шосталь. "Probabilistic-automaton modeling in soils migration processes research." Eastern-European Journal of Enterprise Technologies 4, no. 10(70) (August 11, 2014): 37. http://dx.doi.org/10.15587/1729-4061.2014.26202.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

KAWAMOTO, Kazuhiko, Yusuke KOGA, and Kazushi OKAMOTO. "Learning a probabilistic cellular automaton for people tracking." Journal of Japan Society for Fuzzy Theory and Intelligent Informatics 28, no. 6 (2016): 932–41. http://dx.doi.org/10.3156/jsoft.28.932.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Petersen, Niels K., and Preben Alstrøm. "Phase transition in an elementary probabilistic cellular automaton." Physica A: Statistical Mechanics and its Applications 235, no. 3-4 (February 1997): 473–85. http://dx.doi.org/10.1016/s0378-4371(96)00410-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Bhattacharyya, Pratip. "Transients in a one-dimensional probabilistic cellular automaton." Physica A: Statistical Mechanics and its Applications 245, no. 3-4 (November 1997): 472–84. http://dx.doi.org/10.1016/s0378-4371(97)00310-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Tomé, Tânia, and J. R. Drugowich de Felício. "Probabilistic cellular automaton describing a biological immune system." Physical Review E 53, no. 4 (April 1, 1996): 3976–81. http://dx.doi.org/10.1103/physreve.53.3976.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Hirvensalo, Mika. "Quantum Automata with Open Time Evolution." International Journal of Natural Computing Research 1, no. 1 (January 2010): 70–85. http://dx.doi.org/10.4018/jncr.2010010104.

Full text

Abstract:

In this paper, a model for finite automaton with an open quantum evolution is introduced, and its basic properties are studied. It is shown that the (fuzzy) languages accepted by open evolution quantum automata obey various closure properties. More importantly, it is shown that major other models of finite automata, including probabilistic, measure once quantum, measure many quantum, and Latvian quantum automata can be simulated by the open quantum evolution automata without increasing the number of the states.

APA, Harvard, Vancouver, ISO, and other styles

18

Candic, M., Bao Hui Tian, and Christof Sommitsch. "Grain Growth during Annealing: Experiments and Modelling." Materials Science Forum 715-716 (April 2012): 611–16. http://dx.doi.org/10.4028/www.scientific.net/msf.715-716.611.

Full text

Abstract:

In the present work, for the description of grain coarsening, a probabilistic and a deterministic 2D cellular automaton simulation setup were developed. The results of the simulation have been validated by solution annealing experiments of austenitic stainless steel 304L (Fe-18Cr-8Ni) at different temperatures and times. Both cellular automata models show an excellent correlation between the experimental determined data and grain growth kinetics based upon considerations of temperature and second phase particles. Additionally, a two parameter approach of the probabilistic model was implemented, resulting in determining the grain sizes limiting normal and abnormal grains and accurate description of grain growth.

APA, Harvard, Vancouver, ISO, and other styles

19

Barbashov, Vyacheslav, Nikolai Trushkin, and Aleksei Osipov. "Using probabilistic fuzzy models for the prediction of functional failures of microwave LSI with radiation exposure." ITM Web of Conferences 30 (2019): 10003. http://dx.doi.org/10.1051/itmconf/20193010003.

Full text

Abstract:

The article presents an analysis of microwave LSI behavior under radiation exposure at the functional-logical level of description. The analysis is based on fuzzy digital automaton and topological probabilistic models of workability assessment. It is shown that in certain cases both deterministic and non-deterministic failures are typical. Each operation threshold in logic elements under radiation influence has a zone of uncertainty and can be expressed quantitatively by a fuzzy number. This case, the real nature of microwave LSI radiation behavior is determined by the specific ratio of radiation-sensitive parameters of its elements and by taking into account the influence of their statistical scatter. Methods are proposed for simulating failures of microwave LSI under radiation exposure that are based on the model of a fuzzy digital Brauer automaton and a probabilistic reliability automaton.

APA, Harvard, Vancouver, ISO, and other styles

20

Tomé, T., and J. R. Drugowich de Fel Icio. "Short Time Dynamics of an Irreversible Probabilistic Cellular Automaton." Modern Physics Letters B 12, no. 21 (September 10, 1998): 873–79. http://dx.doi.org/10.1142/s0217984998001001.

Full text

Abstract:

We study the short-time dynamics of a three-state probabilistic cellular automaton. This automaton, termed TD model, possess "up-down" symmetry similar to Ising models, and displays continuous kinetic phase transitions belonging to the Ising model universality class. We perform Monte Carlo simulations on the early time regime of the two-dimensional TD model at criticality and obtain the dynamic exponent θ associated to this regime, and the exponents β/ν and z. Our results indicate that, although the model do not possess microscopic reversibility, it presents short-time universality which is consistent with the one of the kinetic Ising model.

APA, Harvard, Vancouver, ISO, and other styles

21

Arpit, Afza Shafie, and Wan Fatima Wan Ahmad. "Automata for Modeling Reversible Probabilistic Processes." Applied Mechanics and Materials 422 (September 2013): 185–90. http://dx.doi.org/10.4028/www.scientific.net/amm.422.185.

Full text

Abstract:

This paper presents a construction of an automaton that aids the modeling of probabilistic processes which exhibit reversibility during their computations. A probabilistic process defines a probability distribution over the uncertainties of its computations. This characteristic also makes them distinct from nondeterministic processes. But, uncertainties hinder the assurance about the quality of such systems gained by the traditional testing methods. Further, reversibility acts as a catalyst in such scenarios by raising the possibility of achieving the states which were inaccessible in past. Thus, the verification of such systems is necessary and this requires the system to be formally specified. In this respect, proposed work provides the constructs for modeling probabilistic environments and reversibility. Former is achieved by the introduction of discrete probabilities in classical automata theory, and later is implemented by giving the constructs of memory. It also provides the constructs for representing non-determinism by specifying the choices over several probability mass functions for a state.

APA, Harvard, Vancouver, ISO, and other styles

22

Mendonça, J. Ricardo G. "The inactive–active phase transition in the noisy additive (exclusive-or) probabilistic cellular automaton." International Journal of Modern Physics C 27, no. 02 (December 23, 2015): 1650016. http://dx.doi.org/10.1142/s0129183116500169.

Full text

Abstract:

We investigate the inactive–active phase transition in an array of additive (exclusive-or) cellular automata (CA) under noise. The model is closely related with the Domany-Kinzel (DK) probabilistic cellular automaton (PCA), for which there are rigorous as well as numerical estimates on the transition probabilities. Here, we characterize the critical behavior of the noisy additive cellular automaton by mean field analysis and finite-size scaling and show that its phase transition belongs to the directed percolation universality class of critical behavior. As a by-product of our analysis, we argue that the critical behavior of the noisy elementary CA 90 and 102 (in Wolfram’s enumeration scheme) must be the same. We also perform an empirical investigation of the mean field equations to assess their quality and find that away from the critical point (but not necessarily very far away) the mean field approximations provide a reasonably good description of the dynamics of the PCA.

APA, Harvard, Vancouver, ISO, and other styles

23

Carvalho, Kelly C. de, and Tânia Tomé. "Anisotropic probabilistic cellular automaton for a predator-prey system." Brazilian Journal of Physics 37, no. 2a (June 2007): 466–71. http://dx.doi.org/10.1590/s0103-97332007000300020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Qian, Zhuang, Jia Bin, and Li Xin-Gang. "A modified weighted probabilistic cellular automaton traffic flow model." Chinese Physics B 18, no. 8 (July 31, 2009): 3271–78. http://dx.doi.org/10.1088/1674-1056/18/8/030.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

da Silva, Roberto, and Nelson Alves. "Dynamic exponents of a probabilistic three-state cellular automaton." Physica A: Statistical Mechanics and its Applications 350, no. 2-4 (May 2005): 263–76. http://dx.doi.org/10.1016/j.physa.2004.11.052.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Lanzer, A. T. S., and V. D. Pillar. "Probabilistic cellular automaton: model and application to vegetation dynamics." Community Ecology 3, no. 2 (November 2002): 159–67. http://dx.doi.org/10.1556/comec.3.2002.2.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Leva, Mabel A., Alejandro Leon, Rodrigo A. Garrido, and Angel Ibeas. "A PROBABILISTIC CELLULAR AUTOMATON TO FORECAST PORT CHOICE DECISIONS." Transport 33, no. 3 (September 28, 2018): 801–9. http://dx.doi.org/10.3846/transport.2018.5478.

Full text

Abstract:

The port choice problem consists in predicting the selection of a port, made by an agent who has alternatives to choose from. Most of the literature has tackled this problem assuming a discrete choice model dependent on the ports’ characteristics and agents’ attributes. However, in practice the port choice decision depends also on the choices made by other agents as well as decisions made by these agents in the past. There are only a few examples that incorporate the complexity generated by spatio-temporal interactions between agents. However, those modelling structures are rather cumbersome, precluding their use in practical cases. This article presents a new modelling framework to predict port choice decisions, based on the theory of Cellular Automaton (CA), which is simple in structure and can be quickly calibrated and applied. This framework is a probabilistic CA intended to imitate the decision processes made from multiple shippers that interact with each other. These shippers face similar alternatives of seaports for exporting their products within a certain time span. The port choice here is a dynamic decision that depends on the ports’ characteristics and attributes of each shipper at a given time, as well as the decisions made by their neighbours. The outcome of the interaction is a discrete decision that evolves in time according to the dynamics of the system as a whole. The specified CA was applied to the case of vehicle exports from Brazil and the calibration was performed through a genetic algorithm. The results show that the probabilistic CA is able to replicate the historic behaviour of the port choice decisions in the Brazilian vehicle industry, with a high degree of success. The spatial component of the CA turned out to be of major relevance in the dynamic decision process along with the attributes and geographical location of ports.

APA, Harvard, Vancouver, ISO, and other styles

28

Alonso-Sanz, Ramón. "A quantum prisoner’s dilemma cellular automaton with probabilistic updating." International Journal of Parallel, Emergent and Distributed Systems 31, no. 4 (October 28, 2015): 305–18. http://dx.doi.org/10.1080/17445760.2015.1096360.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Bouslama, Mokhtaria, and Mustapha Kamel Abdi. "Towards a Formal Approach for Assessing the Design Quality of Object-Oriented Systems." International Journal of Open Source Software and Processes 12, no. 3 (July 2021): 1–16. http://dx.doi.org/10.4018/ijossp.2021070101.

Full text

Abstract:

The cost of software maintenance is always increasing. The companies are often confronted to failures and software errors. The quality of software to use is so required. In this paper, the authors propose a new formal approach for assessing the quality of object-oriented system design according to the quality assessment model. This approach consists in modeling the input software system by an automaton based on object-oriented design metrics and their relationship with the quality attributes. The model exhibits the importance of metrics through their links with the attributes of software quality. In addition, it is very practical and flexible for all changes. It allows the quality estimation and its validation. For the verification of proposed probabilistic model (automaton), they use the model-checking and the prism tool. The model-checking is very interesting for the evaluation and validation of the probabilistic automaton. They use it to approve the software quality of the three experimental projects. The obtained results are very interesting and of great importance.

APA, Harvard, Vancouver, ISO, and other styles

30

Perinotti, Paolo. "Causal influence in operational probabilistic theories." Quantum 5 (August 3, 2021): 515. http://dx.doi.org/10.22331/q-2021-08-03-515.

Full text

Abstract:

We study the relation of causal influence between input systems of a reversible evolution and its output systems, in the context of operational probabilistic theories. We analyse two different definitions that are borrowed from the literature on quantum theory—where they are equivalent. One is the notion based on signalling, and the other one is the notion used to define the neighbourhood of a cell in a quantum cellular automaton. The latter definition, that we adopt in the general scenario, turns out to be strictly weaker than the former: it is possible for a system to have causal influence on another one without signalling to it. Remarkably, the counterexample comes from classical theory, where the proposed notion of causal influence determines a redefinition of the neighbourhood of a cell in cellular automata. We stress that, according to our definition, it is impossible anyway to have causal influence in the absence of an interaction, e.g. in a Bell-like scenario. We study various conditions for causal influence, and introduce the feature that we call no interaction without disturbance, under which we prove that signalling and causal influence coincide. The proposed definition has interesting consequences on the analysis of causal networks, and leads to a revision of the notion of neighbourhood for classical cellular automata, clarifying a puzzle regarding their quantisation that apparently makes the neighbourhood larger than the original one.

APA, Harvard, Vancouver, ISO, and other styles

31

Fatès, Nazim, Irène Marcovici, and Siamak Taati. "Self-stabilisation of Cellular Automata on Tilings." Fundamenta Informaticae 185, no. 1 (March 18, 2022): 27–82. http://dx.doi.org/10.3233/fi-222103.

Full text

Abstract:

Given a finite set of local constraints, we seek a cellular automaton (i.e., a local and uniform algorithm) that self-stabilises on the configurations that satisfy these constraints. More precisely, starting from a finite perturbation of a valid configuration, the cellular automaton must eventually fall back into the space of valid configurations where it remains still. We allow the cellular automaton to use extra symbols, but in that case, the extra symbols can also appear in the initial finite perturbation. For several classes of local constraints (e.g., k-colourings with k ≠ 3, and North-East deterministic constraints), we provide efficient self-stabilising cellular automata with or without additional symbols that wash out finite perturbations in linear or quadratic time, but also show that there are examples of local constraints for which the self-stabilisation problem is inherently hard. We note that the optimal self-stabilisation speed is the same for all local constraints that are isomorphic to one another. We also consider probabilistic cellular automata rules and show that in some cases, the use of randomness simplifies the problem. In the deterministic case, we show that if finite perturbations are corrected in linear time, then the cellular automaton self-stabilises even starting from a random perturbation of a valid configuration, that is, when errors in the initial configuration occur independently with a sufficiently low density.

APA, Harvard, Vancouver, ISO, and other styles

32

Palanichamy, Jegathambal, Holger Schüttrumpf, and Sundarambal Palani. "A probabilistic cellular automaton for two dimensional contaminant transport simulation in ground water." Water Science and Technology 58, no. 11 (December 1, 2008): 2083–92. http://dx.doi.org/10.2166/wst.2008.824.

Full text

Abstract:

In recent years evolutionary computing algorithms have been proposed to solve many engineering problems. Genetic algorithms, Neural Networks, and Cellular Automata are the branches of evolutionary computing techniques. In this study, it is proposed to simulate the contaminant transport in porous media using a Cellular Automaton. The physical processes and chemical reactions occurring in the ground water system are intricately connected at various scales of space, time, transport coefficients and molecular concentration. The validity of continuous approach for the simulation of chemical systems with low concentration of species and intracellular environments has become subtle. Due to the difference in scales of various processes that occur in the ground water system, the description of the system can be well defined in the intermediate scale called mesoscopic scale, which is in between microscopic and macroscopic description. Mesoscopic models provide the relationship between various parameters and their evolvement in time, thus establishing the contact between modeling at various scales at the interface. In this paper, a Probabilistic Cellular Automaton (PCA) model has been developed based on the transport and reaction probability values. The developed model was verified and validated for one, two dimensional transport systems and also for the simulation of BTEX transport in two dimensional system in ground water.

APA, Harvard, Vancouver, ISO, and other styles

33

CEM SAY, A. C., and ABUZER YAKARYILMAZ. "QUANTUM COUNTER AUTOMATA." International Journal of Foundations of Computer Science 23, no. 05 (August 2012): 1099–116. http://dx.doi.org/10.1142/s012905411250013x.

Full text

Abstract:

The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.

APA, Harvard, Vancouver, ISO, and other styles

34

Alonso-Sanz, Ramón. "Phase transitions in an elementary probabilistic cellular automaton with memory." Physica A: Statistical Mechanics and its Applications 347 (March 2005): 383–401. http://dx.doi.org/10.1016/j.physa.2004.08.082.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Emam, S. S., and J. Miller. "Inferring Extended Probabilistic Finite-State Automaton Models from Software Executions." ACM Transactions on Software Engineering and Methodology 27, no. 1 (June 5, 2018): 1–39. http://dx.doi.org/10.1145/3196883.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Alekseev, D. V., and G. A. Kazunina. "Simulation of damage accumulation kinetics with a probabilistic cellular automaton." Physics of the Solid State 48, no. 2 (February 2006): 272–78. http://dx.doi.org/10.1134/s1063783406020132.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Bhattacharyya, P. "Dynamic critical properties of a one-dimensional probabilistic cellular automaton." European Physical Journal B 3, no. 2 (July 1998): 247–52. http://dx.doi.org/10.1007/s100510050309.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Ide, Satoshi, and Suguru Yabe. "Two-Dimensional Probabilistic Cell Automaton Model for Broadband Slow Earthquakes." Pure and Applied Geophysics 176, no. 3 (August 17, 2018): 1021–36. http://dx.doi.org/10.1007/s00024-018-1976-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

ALLAUZEN, CYRIL, MEHRYAR MOHRI, and ASHISH RASTOGI. "GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS." International Journal of Foundations of Computer Science 22, no. 04 (June 2011): 883–904. http://dx.doi.org/10.1142/s0129054111008477.

Full text

Abstract:

We present efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with ε-transitions. We give an algorithm for testing the exponential ambiguity of an automaton A in time [Formula: see text], and finite or polynomial ambiguity in time [Formula: see text], where |A|E denotes the number of transitions of A. These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and based on a general algorithm for the composition or intersection of automata. Additionally, we give an algorithm to determine in time [Formula: see text] the degree of polynomial ambiguity of a polynomially ambiguous automaton A and present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton. We also study the double-tape ambiguity of finite-state transducers. We show that the general problem is undecidable and that it is NP-hard for acyclic transducers. We present a specific analysis of the double-tape ambiguity of transducers with bounded delay. In particular, we give a characterization of double-tape ambiguity for synchronized transducers with zero delay that can be tested in quadratic time and give an algorithm for testing the double-tape ambiguity of transducers with bounded delay.

APA, Harvard, Vancouver, ISO, and other styles

40

Marzen, Sarah E., and James P. Crutchfield. "Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited." Entropy 24, no. 1 (January 6, 2022): 90. http://dx.doi.org/10.3390/e24010090.

Full text

Abstract:

Reservoir computers (RCs) and recurrent neural networks (RNNs) can mimic any finite-state automaton in theory, and some workers demonstrated that this can hold in practice. We test the capability of generalized linear models, RCs, and Long Short-Term Memory (LSTM) RNN architectures to predict the stochastic processes generated by a large suite of probabilistic deterministic finite-state automata (PDFA) in the small-data limit according to two metrics: predictive accuracy and distance to a predictive rate-distortion curve. The latter provides a sense of whether or not the RNN is a lossy predictive feature extractor in the information-theoretic sense. PDFAs provide an excellent performance benchmark in that they can be systematically enumerated, the randomness and correlation structure of their generated processes are exactly known, and their optimal memory-limited predictors are easily computed. With less data than is needed to make a good prediction, LSTMs surprisingly lose at predictive accuracy, but win at lossy predictive feature extraction. These results highlight the utility of causal states in understanding the capabilities of RNNs to predict.

APA, Harvard, Vancouver, ISO, and other styles

41

Kazunina, G. A., and D. V. Alekseev. "Peculiarities of Damage Cluster Distribution in Loaded Materials: Simulation with Probabilistic Cellular Automaton." Advanced Materials Research 933 (May 2014): 62–65. http://dx.doi.org/10.4028/www.scientific.net/amr.933.62.

Full text

Abstract:

Distribution of damage clusters according to size and local density is investigated on the basis of probabilistic cellular automaton proposed by the authors. Specific features of the distributions typical for systems that are prone to disasters are identified.

APA, Harvard, Vancouver, ISO, and other styles

42

Huang, Yuchong, Ning Xu, Nan Wang, and Jie Li. "Synthesis method of strategy for multi-robot systems from local automatons under probabilistic model checking." Journal of Intelligent & Fuzzy Systems 42, no. 3 (February 2, 2022): 2057–69. http://dx.doi.org/10.3233/jifs-211427.

Full text

Abstract:

Through innovatively introducing the receding horizon into probabilistic model checking, an online strategy synthesis method for multi-robot systems from local automatons is proposed to complete complex tasks that are assigned to each robot. Firstly, each robot is modeled as a Markov decision process which models both probabilistic and nondeterministic behavior. Secondly, the task specification of each robot is expressed as a linear temporal logic formula. For some tasks that robots cannot complete by themselves, the collaboration requirements take the form of atomic proposition into the LTL specifications. And the LTL specifications are transformed to deterministic rabin automatons over which a task progression metric is defined to determine the local goal states in the finite-horizon product systems. Thirdly, two horizons are set to determine the running steps in automatons and MDPs. By dynamically building local finite-horizon product systems, the collaboration strategies are synthesized iteratively for each robot to satisfy the task specifications with maximum probability. Finally, through simulation experiments in an indoor environment, the results show that the method can synthesize correct strategies online for multi-robot systems which has no restriction on the LTL operators and reduce the computational burden brought by the automaton-based approach.

APA, Harvard, Vancouver, ISO, and other styles

43

Zhang, L., C. C. Zhang, Y. Y. Wang, X. X. Liu, and G. G. Wang. "Cellular automaton model to simulate nucleation and growth of ferrite grains for low-carbon steels." Journal of Materials Research 17, no. 9 (September 2002): 2251–59. http://dx.doi.org/10.1557/jmr.2002.0331.

Full text

Abstract:

A two-dimensional cellular automaton model was developed for the simulation of nucleation and growth of ferrite grains at various cooling rates in low-carbon steels. The model calculates the diffusion of the solute and temperature fields in an explicit finite method and incorporates local temperature and concentration changes into a nucleation or growth function, which is utilized by the automaton in a probabilistic fashion. The modeling provides an efficient way to understand how those physical processes dynamically progress and affect nucleation and growth of ferrite grains.

APA, Harvard, Vancouver, ISO, and other styles

44

BOCCARA, N., and M. ROGER. "TOTALISTIC TWO-DIMENSIONAL CELLULAR AUTOMATA EXHIBITING GLOBAL PERIODIC BEHAVIOR." International Journal of Modern Physics C 10, no. 06 (September 1999): 1017–24. http://dx.doi.org/10.1142/s0129183199000814.

Full text

Abstract:

We have determined families of two-dimensional deterministic totalistic cellular automaton rules whose stationary density of active sites exhibits a period two in time. Each family of deterministic rules is characterized by an "average probabilistic totalistic rule" exhibiting the same periodic behavior.

APA, Harvard, Vancouver, ISO, and other styles

45

Gan, Guo Qiang, Ke Min Xue, and Ping Li. "Cellular Automaton Modeling of the Isothermal Hot Compression Phase Transformation in TA15 Titanium Alloy." Advanced Materials Research 146-147 (October 2010): 1806–10. http://dx.doi.org/10.4028/www.scientific.net/amr.146-147.1806.

Full text

Abstract:

A two-dimensional cellular automaton model is developed to simulate the isothermal hot compression phase transformation of β→α in TA15 titanium alloy. The model, based on the data of hot compression deformation and some assumption, the phase transformation nucleation and growth function of the phase β→α which is utilized by the automaton in a probabilistic fashion. The probability of nucleation and growth of α phase is confirmed and described by the existing theories of dislocation density. The competition between phase transformation and growth of transitional phase is described by the changes of dislocation density in this cellular automaton lattice. Based on the results of cellular automaton, the transformation fraction of α phase is calculated with the number of lattice and isothermal phase transformation kinetic equation is also calculated with data of transformation fraction, and the effect of hot compression deformation parameters on phase transformation is also discussed.

APA, Harvard, Vancouver, ISO, and other styles

46

HIRATA, Takayuki, and Masajiro IMOTO. "A Probabilistic Cellular Automaton Approach for a Spatiotemporal Seismic Activity Pattern." Zisin (Journal of the Seismological Society of Japan. 2nd ser.) 49, no. 4 (1997): 441–49. http://dx.doi.org/10.4294/zisin1948.49.4_441.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Ortega, Neli R. S., C. Felipe de S. Pinheiro, Tânia Tomé, and J. R. Drugowich de Felı́cio. "Critical behavior of a probabilistic cellular automaton describing a biological system." Physica A: Statistical Mechanics and its Applications 255, no. 1-2 (June 1998): 189–200. http://dx.doi.org/10.1016/s0378-4371(98)00049-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Chassaing, Philippe, and Jean Mairesse. "A non-ergodic probabilistic cellular automaton with a unique invariant measure." Stochastic Processes and their Applications 121, no. 11 (November 2011): 2474–87. http://dx.doi.org/10.1016/j.spa.2011.06.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Xing-Li, Li, Kuang Hua, Song Tao, Dai Shi-Qiang, and Li Zhi-Peng. "New insights into traffic dynamics: a weighted probabilistic cellular automaton model." Chinese Physics B 17, no. 7 (July 2008): 2366–72. http://dx.doi.org/10.1088/1674-1056/17/7/008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Jiménez-Morales, F., and J. J. Luque. "Collective behaviour of a probabilistic cellular automaton with two absorbing phases." Physics Letters A 181, no. 1 (September 1993): 33–38. http://dx.doi.org/10.1016/0375-9601(93)91120-t.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!