Finite automata over magmas: models and some applications in Cryptography

Directory of Open Access Journals (Sweden)

Volodymyr V. Skobelev

2018-05-01

Full Text Available In the paper the families of finite semi-automata and reversible finite Mealy and Moore automata over finite magmas are defined and analyzed in detail. On the base of these models it is established that the set of finite quasigroups is the most acceptable subset of the set of finite magmas at resolving model problems in Cryptography, such as design of iterated hash functions and stream ciphers. Defined families of finite semi-automata and reversible finite automata over finite $T$-quasigroups are investigated in detail. It is established that in this case models time and space complexity for simulation of the functioning during one instant of automaton time can be much lower than in general case.

Automata, universality, computation tribute to Maurice Margenstern

CERN Document Server

2015-01-01

This book is an intellectually stimulating excursion into mathematical machines and structures capable for a universal computation. World top experts in computer science and mathematics overview exciting and intriguing topics of logical theory of monoids, geometry of Gauss word, philosophy of mathematics in computer science, asynchronous and parallel P-systems, decidability in cellular automata, splicing systems, reversible Turing machines, information flows in two-way finite automata, prime generators in automaton arrays, Grossone and Turing machines, automaton models of atomic lattices. The book is  full of visually attractive examples of mathematical machines, open problems and challenges for future research. Those interested in the advancement of a theory of computation, philosophy of mathematics, future and emergent computing paradigms, architectures and implementations will find the book vital for their research and development.

Weighted Watson-Crick automata

Energy Technology Data Exchange (ETDEWEB)

Tamrin, Mohd Izzuddin Mohd [Department of Information System, Kulliyyah of Information and Communication Technology, International Islamic University Malaysia, 50728 Gombak, Selangor (Malaysia); Turaev, Sherzod; Sembok, Tengku Mohd Tengku [Department of Computer Science, Kulliyyah of Information and Communication Technology, International Islamic University Malaysia, 50728 Gombak, Selangor (Malaysia)

2014-07-10

There are tremendous works in biotechnology especially in area of DNA molecules. The computer society is attempting to develop smaller computing devices through computational models which are based on the operations performed on the DNA molecules. A Watson-Crick automaton, a theoretical model for DNA based computation, has two reading heads, and works on double-stranded sequences of the input related by a complementarity relation similar with the Watson-Crick complementarity of DNA nucleotides. Over the time, several variants of Watson-Crick automata have been introduced and investigated. However, they cannot be used as suitable DNA based computational models for molecular stochastic processes and fuzzy processes that are related to important practical problems such as molecular parsing, gene disease detection, and food authentication. In this paper we define new variants of Watson-Crick automata, called weighted Watson-Crick automata, developing theoretical models for molecular stochastic and fuzzy processes. We define weighted Watson-Crick automata adapting weight restriction mechanisms associated with formal grammars and automata. We also study the generative capacities of weighted Watson-Crick automata, including probabilistic and fuzzy variants. We show that weighted variants of Watson-Crick automata increase their generative power.

Weighted Watson-Crick automata

International Nuclear Information System (INIS)

Tamrin, Mohd Izzuddin Mohd; Turaev, Sherzod; Sembok, Tengku Mohd Tengku

2014-01-01

There are tremendous works in biotechnology especially in area of DNA molecules. The computer society is attempting to develop smaller computing devices through computational models which are based on the operations performed on the DNA molecules. A Watson-Crick automaton, a theoretical model for DNA based computation, has two reading heads, and works on double-stranded sequences of the input related by a complementarity relation similar with the Watson-Crick complementarity of DNA nucleotides. Over the time, several variants of Watson-Crick automata have been introduced and investigated. However, they cannot be used as suitable DNA based computational models for molecular stochastic processes and fuzzy processes that are related to important practical problems such as molecular parsing, gene disease detection, and food authentication. In this paper we define new variants of Watson-Crick automata, called weighted Watson-Crick automata, developing theoretical models for molecular stochastic and fuzzy processes. We define weighted Watson-Crick automata adapting weight restriction mechanisms associated with formal grammars and automata. We also study the generative capacities of weighted Watson-Crick automata, including probabilistic and fuzzy variants. We show that weighted variants of Watson-Crick automata increase their generative power

Logic and Automata History and Perspectives

CERN Document Server

Gradel, Erich; Wilk, Thomas

2007-01-01

Mathematical logic and automata theory are two scientific disciplines with a fundamentally close relationship. The authors of Logic and Automata take the occasion of the sixtieth birthday of Wolfgang Thomas to present a tour d'horizon of automata theory and logic. The twenty papers in this volume cover many different facets of logic and automata theory, emphasizing the connections to other disciplines such as games, algorithms, and semigroup theory, as well as discussing current challenges in the field. Title: Logic and Automata : History and Perspectives Print ISBN: 9789053565766 Author(s): Flum, Jörg; Gr; del, Erich; Wilke, Thomas eISBN: 9789048501281 Publisher: Amsterdam University Press Dewey: 511.3 Publication Date: 01 Jan, 2007 Pages: 737 Category: Mathematics LCCN: Language: English Edition: N/A LCSH:

a Discrete Mathematical Model to Simulate Malware Spreading

Science.gov (United States)

Del Rey, A. Martin; Sánchez, G. Rodriguez

2012-10-01

With the advent and worldwide development of Internet, the study and control of malware spreading has become very important. In this sense, some mathematical models to simulate malware propagation have been proposed in the scientific literature, and usually they are based on differential equations exploiting the similarities with mathematical epidemiology. The great majority of these models study the behavior of a particular type of malware called computer worms; indeed, to the best of our knowledge, no model has been proposed to simulate the spreading of a computer virus (the traditional type of malware which differs from computer worms in several aspects). In this sense, the purpose of this work is to introduce a new mathematical model not based on continuous mathematics tools but on discrete ones, to analyze and study the epidemic behavior of computer virus. Specifically, cellular automata are used in order to design such model.

On Algebraic Study of Type-2 Fuzzy Finite State Automata

Directory of Open Access Journals (Sweden)

Anupam K. Singh

2017-08-01

Full Text Available Theories of fuzzy sets and type-2 fuzzy sets are powerful mathematical tools for modeling various types of uncertainty. In this paper we introduce the concept of type-2 fuzzy finite state automata and discuss the algebraic study of type-2 fuzzy finite state automata, i.e., to introduce the concept of homomorphisms between two type-2 fuzzy finite state automata, to associate a type-2 fuzzy transformation semigroup with a type-2 fuzzy finite state automata. Finally, we discuss several product of type-2 fuzzy finite state automata and shown that these product is a categorical product.

Modelling Social-Technical Attacks with Timed Automata

DEFF Research Database (Denmark)

David, Nicolas; David, Alexandre; Hansen, Rene Rydhof

2015-01-01

. In this paper we develop an approach towards modelling socio-technical systems in general and socio-technical attacks in particular, using timed automata and illustrate its application by a complex case study. Thanks to automated model checking and automata theory, we can automatically generate possible attacks...... in our model and perform analysis and simulation of both model and attack, revealing details about the specific interaction between attacker and victim. Using timed automata also allows for intuitive modelling of systems, in which quantities like time and cost can be easily added and analysed....

Algebraic and structural automata theory

CERN Document Server

Mikolajczak, B

1991-01-01

Automata Theory is part of computability theory which covers problems in computer systems, software, activity of nervous systems (neural networks), and processes of live organisms development.The result of over ten years of research, this book presents work in the following areas of Automata Theory: automata morphisms, time-varying automata, automata realizations and relationships between automata and semigroups.Aimed at those working in discrete mathematics and computer science, parts of the book are suitable for use in graduate courses in computer science, electronics, telecommunications, and control engineering. It is assumed that the reader is familiar with the basic concepts of algebra and graph theory.

Generic framework for mining cellular automata models on protein-folding simulations.

Science.gov (United States)

Diaz, N; Tischer, I

2016-05-13

Cellular automata model identification is an important way of building simplified simulation models. In this study, we describe a generic architectural framework to ease the development process of new metaheuristic-based algorithms for cellular automata model identification in protein-folding trajectories. Our framework was developed by a methodology based on design patterns that allow an improved experience for new algorithms development. The usefulness of the proposed framework is demonstrated by the implementation of four algorithms, able to obtain extremely precise cellular automata models of the protein-folding process with a protein contact map representation. Dynamic rules obtained by the proposed approach are discussed, and future use for the new tool is outlined.

Quantitative Analysis of Intra Urban Growth Modeling using socio economic agents by combining cellular automata model with agent based model

Science.gov (United States)

Singh, V. K.; Jha, A. K.; Gupta, K.; Srivastav, S. K.

2017-12-01

Recent studies indicate that there is a significant improvement in the urban land use dynamics through modeling at finer spatial resolutions. Geo-computational models such as cellular automata and agent based model have given evident proof regarding the quantification of the urban growth pattern with urban boundary. In recent studies, socio- economic factors such as demography, education rate, household density, parcel price of the current year, distance to road, school, hospital, commercial centers and police station are considered to the major factors influencing the Land Use Land Cover (LULC) pattern of the city. These factors have unidirectional approach to land use pattern which makes it difficult to analyze the spatial aspects of model results both quantitatively and qualitatively. In this study, cellular automata model is combined with generic model known as Agent Based Model to evaluate the impact of socio economic factors on land use pattern. For this purpose, Dehradun an Indian city is selected as a case study. Socio economic factors were collected from field survey, Census of India, Directorate of economic census, Uttarakhand, India. A 3X3 simulating window is used to consider the impact on LULC. Cellular automata model results are examined for the identification of hot spot areas within the urban area and agent based model will be using logistic based regression approach where it will identify the correlation between each factor on LULC and classify the available area into low density, medium density, high density residential or commercial area. In the modeling phase, transition rule, neighborhood effect, cell change factors are used to improve the representation of built-up classes. Significant improvement is observed in the built-up classes from 84 % to 89 %. However after incorporating agent based model with cellular automata model the accuracy improved from 89 % to 94 % in 3 classes of urban i.e. low density, medium density and commercial classes

a Predator-Prey Model Based on the Fully Parallel Cellular Automata

Science.gov (United States)

He, Mingfeng; Ruan, Hongbo; Yu, Changliang

We presented a predator-prey lattice model containing moveable wolves and sheep, which are characterized by Penna double bit strings. Sexual reproduction and child-care strategies are considered. To implement this model in an efficient way, we build a fully parallel Cellular Automata based on a new definition of the neighborhood. We show the roles played by the initial densities of the populations, the mutation rate and the linear size of the lattice in the evolution of this model.

Comments On Clock Models In Hybrid Automata And Hybrid Control Systems

Directory of Open Access Journals (Sweden)

Virginia Ecaterina OLTEAN

2001-12-01

Full Text Available Hybrid systems have received a lot of attention in the past decade and a number of different models have been proposed in order to establish mathematical framework that is able to handle both continuous and discrete aspects. This contribution is focused on two models: hybrid automata and hybrid control systems with continuous-discrete interface and the importance of clock models is emphasized. Simple and relevant examples, some taken from the literature, accompany the presentation.

Statistical mechanics of cellular automata

International Nuclear Information System (INIS)

Wolfram, S.

1983-01-01

Cellular automata are used as simple mathematical models to investigate self-organization in statistical mechanics. A detailed analysis is given of ''elementary'' cellular automata consisting of a sequence of sites with values 0 or 1 on a line, with each site evolving deterministically in discrete time steps according to p definite rules involving the values of its nearest neighbors. With simple initial configurations, the cellular automata either tend to homogeneous states, or generate self-similar patterns with fractal dimensions approx. =1.59 or approx. =1.69. With ''random'' initial configurations, the irreversible character of the cellular automaton evolution leads to several self-organization phenomena. Statistical properties of the structures generated are found to lie in two universality classes, independent of the details of the initial state or the cellular automaton rules. More complicated cellular automata are briefly considered, and connections with dynamical systems theory and the formal theory of computation are discussed

Linear Parametric Model Checking of Timed Automata

DEFF Research Database (Denmark)

Hune, Tohmas Seidelin; Romijn, Judi; Stoelinga, Mariëlle

2001-01-01

We present an extension of the model checker Uppaal capable of synthesize linear parameter constraints for the correctness of parametric timed automata. The symbolic representation of the (parametric) state-space is shown to be correct. A second contribution of this paper is the identication...... of a subclass of parametric timed automata (L/U automata), for which the emptiness problem is decidable, contrary to the full class where it is know to be undecidable. Also we present a number of lemmas enabling the verication eort to be reduced for L/U automata in some cases. We illustrate our approach...

Cellular-automata supercomputers for fluid-dynamics modeling

International Nuclear Information System (INIS)

Margolus, N.; Toffoli, T.; Vichniac, G.

1986-01-01

We report recent developments in the modeling of fluid dynamics, and give experimental results (including dynamical exponents) obtained using cellular automata machines. Because of their locality and uniformity, cellular automata lend themselves to an extremely efficient physical realization; with a suitable architecture, an amount of hardware resources comparable to that of a home computer can achieve (in the simulation of cellular automata) the performance of a conventional supercomputer

Cellular automata and statistical mechanical models

International Nuclear Information System (INIS)

Rujan, P.

1987-01-01

The authors elaborate on the analogy between the transfer matrix of usual lattice models and the master equation describing the time development of cellular automata. Transient and stationary properties of probabilistic automata are linked to surface and bulk properties, respectively, of restricted statistical mechanical systems. It is demonstrated that methods of statistical physics can be successfully used to describe the dynamic and the stationary behavior of such automata. Some exact results are derived, including duality transformations, exact mappings, disorder, and linear solutions. Many examples are worked out in detail to demonstrate how to use statistical physics in order to construct cellular automata with desired properties. This approach is considered to be a first step toward the design of fully parallel, probabilistic systems whose computational abilities rely on the cooperative behavior of their components

Modeling biological pathway dynamics with timed automata.

Science.gov (United States)

Schivo, Stefano; Scholma, Jetse; Wanders, Brend; Urquidi Camacho, Ricardo A; van der Vet, Paul E; Karperien, Marcel; Langerak, Rom; van de Pol, Jaco; Post, Janine N

2014-05-01

Living cells are constantly subjected to a plethora of environmental stimuli that require integration into an appropriate cellular response. This integration takes place through signal transduction events that form tightly interconnected networks. The understanding of these networks requires capturing their dynamics through computational support and models. ANIMO (analysis of Networks with Interactive Modeling) is a tool that enables the construction and exploration of executable models of biological networks, helping to derive hypotheses and to plan wet-lab experiments. The tool is based on the formalism of Timed Automata, which can be analyzed via the UPPAAL model checker. Thanks to Timed Automata, we can provide a formal semantics for the domain-specific language used to represent signaling networks. This enforces precision and uniformity in the definition of signaling pathways, contributing to the integration of isolated signaling events into complex network models. We propose an approach to discretization of reaction kinetics that allows us to efficiently use UPPAAL as the computational engine to explore the dynamic behavior of the network of interest. A user-friendly interface hides the use of Timed Automata from the user, while keeping the expressive power intact. Abstraction to single-parameter kinetics speeds up construction of models that remain faithful enough to provide meaningful insight. The resulting dynamic behavior of the network components is displayed graphically, allowing for an intuitive and interactive modeling experience.

Geometrical automata for two phase flow simulation

International Nuclear Information System (INIS)

Herrero, V.; Guido-Lavalle, G.; Clausse, A.

1996-01-01

An automaton is an entity defined by a mathematical state which changes following iterative rules representing the interaction with the neighborhood. A model of automata for two-phase flow simulation consisting in a field of disks which are allowed to change their radii and move in a plane is presented. The model is more general than the classical cellular automata in two respects: (1) the grid of cellular automata is dismissed in favor of a trajectory generator; and (2) the rules of interaction involve parameters intended to represent some of the most relevant variables governing the actual physical interactions between phases. Computational experiments show that the algorithm captures the essential physics underlying two-phase flow problems such as bubbly-slug pattern transition and void fraction development along tubes. A comparison with experimental data of void fraction profiles is presented, showing excellent agreement. (orig.)

A Cellular Automata-based Model for Simulating Restitution Property in a Single Heart Cell.

Science.gov (United States)

Sabzpoushan, Seyed Hojjat; Pourhasanzade, Fateme

2011-01-01

Ventricular fibrillation is the cause of the most sudden mortalities. Restitution is one of the specific properties of ventricular cell. The recent findings have clearly proved the correlation between the slope of restitution curve with ventricular fibrillation. This; therefore, mandates the modeling of cellular restitution to gain high importance. A cellular automaton is a powerful tool for simulating complex phenomena in a simple language. A cellular automaton is a lattice of cells where the behavior of each cell is determined by the behavior of its neighboring cells as well as the automata rule. In this paper, a simple model is depicted for the simulation of the property of restitution in a single cardiac cell using cellular automata. At first, two state variables; action potential and recovery are introduced in the automata model. In second, automata rule is determined and then recovery variable is defined in such a way so that the restitution is developed. In order to evaluate the proposed model, the generated restitution curve in our study is compared with the restitution curves from the experimental findings of valid sources. Our findings indicate that the presented model is not only capable of simulating restitution in cardiac cell, but also possesses the capability of regulating the restitution curve.

Simulasi Tumbukan Partikel Gas Ideal Dengan Model Cellular Automata Dua Dimensi

OpenAIRE

Abdul Basid, Annisa Mujriati

2010-01-01

Telah dilakukan simulasi tumbukan partikel gas ideal dengan menggunakan  model cellular automata dua dimensi untuk memvisualisasikan tumbukan partikel gas ideal. Tumbukan partikel  disimulasikan  dengan  menggunakan  model  cellular  automata  dua  dimensi.  Di  dalam cellular automata, pergerakan partikel diatur dengan suatu aturan  yaitu aturan delapan tetangga yang merupakan aturan acak. Hasil program simulasi tumbukan partikel gas ideal dengan model cellular automata dua dimensi  mengguna...

A cardiac electrical activity model based on a cellular automata system in comparison with neural network model.

Science.gov (United States)

Khan, Muhammad Sadiq Ali; Yousuf, Sidrah

2016-03-01

Cardiac Electrical Activity is commonly distributed into three dimensions of Cardiac Tissue (Myocardium) and evolves with duration of time. The indicator of heart diseases can occur randomly at any time of a day. Heart rate, conduction and each electrical activity during cardiac cycle should be monitor non-invasively for the assessment of "Action Potential" (regular) and "Arrhythmia" (irregular) rhythms. Many heart diseases can easily be examined through Automata model like Cellular Automata concepts. This paper deals with the different states of cardiac rhythms using cellular automata with the comparison of neural network also provides fast and highly effective stimulation for the contraction of cardiac muscles on the Atria in the result of genesis of electrical spark or wave. The specific formulated model named as "States of automaton Proposed Model for CEA (Cardiac Electrical Activity)" by using Cellular Automata Methodology is commonly shows the three states of cardiac tissues conduction phenomena (i) Resting (Relax and Excitable state), (ii) ARP (Excited but Absolutely refractory Phase i.e. Excited but not able to excite neighboring cells) (iii) RRP (Excited but Relatively Refractory Phase i.e. Excited and able to excite neighboring cells). The result indicates most efficient modeling with few burden of computation and it is Action Potential during the pumping of blood in cardiac cycle.

Global properties of cellular automata

International Nuclear Information System (INIS)

Jen, E.

1986-01-01

Cellular automata are discrete mathematical systems that generate diverse, often complicated, behavior using simple deterministic rules. Analysis of the local structure of these rules makes possible a description of the global properties of the associated automata. A class of cellular automata that generate infinitely many aperoidic temporal sequences is defined,a s is the set of rules for which inverses exist. Necessary and sufficient conditions are derived characterizing the classes of ''nearest-neighbor'' rules for which arbitrary finite initial conditions (i) evolve to a homogeneous state; (ii) generate at least one constant temporal sequence

Modeling and Density Estimation of an Urban Freeway Network Based on Dynamic Graph Hybrid Automata.

Science.gov (United States)

Chen, Yangzhou; Guo, Yuqi; Wang, Ying

2017-03-29

In this paper, in order to describe complex network systems, we firstly propose a general modeling framework by combining a dynamic graph with hybrid automata and thus name it Dynamic Graph Hybrid Automata (DGHA). Then we apply this framework to model traffic flow over an urban freeway network by embedding the Cell Transmission Model (CTM) into the DGHA. With a modeling procedure, we adopt a dual digraph of road network structure to describe the road topology, use linear hybrid automata to describe multi-modes of dynamic densities in road segments and transform the nonlinear expressions of the transmitted traffic flow between two road segments into piecewise linear functions in terms of multi-mode switchings. This modeling procedure is modularized and rule-based, and thus is easily-extensible with the help of a combination algorithm for the dynamics of traffic flow. It can describe the dynamics of traffic flow over an urban freeway network with arbitrary topology structures and sizes. Next we analyze mode types and number in the model of the whole freeway network, and deduce a Piecewise Affine Linear System (PWALS) model. Furthermore, based on the PWALS model, a multi-mode switched state observer is designed to estimate the traffic densities of the freeway network, where a set of observer gain matrices are computed by using the Lyapunov function approach. As an example, we utilize the PWALS model and the corresponding switched state observer to traffic flow over Beijing third ring road. In order to clearly interpret the principle of the proposed method and avoid computational complexity, we adopt a simplified version of Beijing third ring road. Practical application for a large-scale road network will be implemented by decentralized modeling approach and distributed observer designing in the future research.

Modeling reliability of power systems substations by using stochastic automata networks

International Nuclear Information System (INIS)

Šnipas, Mindaugas; Radziukynas, Virginijus; Valakevičius, Eimutis

2017-01-01

In this paper, stochastic automata networks (SANs) formalism to model reliability of power systems substations is applied. The proposed strategy allows reducing the size of state space of Markov chain model and simplifying system specification. Two case studies of standard configurations of substations are considered in detail. SAN models with different assumptions were created. SAN approach is compared with exact reliability calculation by using a minimal path set method. Modeling results showed that total independence of automata can be assumed for relatively small power systems substations with reliable equipment. In this case, the implementation of Markov chain model by a using SAN method is a relatively easy task. - Highlights: • We present the methodology to apply stochastic automata network formalism to create Markov chain models of power systems. • The stochastic automata network approach is combined with minimal path sets and structural functions. • Two models of substation configurations with different model assumptions are presented to illustrate the proposed methodology. • Modeling results of system with independent automata and functional transition rates are similar. • The conditions when total independence of automata can be assumed are addressed.

A survey on the modeling and applications of cellular automata theory

Science.gov (United States)

Gong, Yimin

2017-09-01

The Cellular Automata Theory is a discrete model which is now widely used in scientific researches and simulations. The model is comprised of some cells which changes according to a specific rule over time. This paper provides a survey of the Modeling and Applications of Cellular Automata Theory, which focus on the program realization of Cellular Automata Theory and the application of Cellular Automata in each field, such as road traffic, land use, and cutting machines. Each application is further explained, and several related main models are briefly introduced. This research aims to help decision-makers formulate appropriate development plans.

Probabilistic cellular automata.

Science.gov (United States)

Agapie, Alexandru; Andreica, Anca; Giuclea, Marius

2014-09-01

Cellular automata are binary lattices used for modeling complex dynamical systems. The automaton evolves iteratively from one configuration to another, using some local transition rule based on the number of ones in the neighborhood of each cell. With respect to the number of cells allowed to change per iteration, we speak of either synchronous or asynchronous automata. If randomness is involved to some degree in the transition rule, we speak of probabilistic automata, otherwise they are called deterministic. With either type of cellular automaton we are dealing with, the main theoretical challenge stays the same: starting from an arbitrary initial configuration, predict (with highest accuracy) the end configuration. If the automaton is deterministic, the outcome simplifies to one of two configurations, all zeros or all ones. If the automaton is probabilistic, the whole process is modeled by a finite homogeneous Markov chain, and the outcome is the corresponding stationary distribution. Based on our previous results for the asynchronous case-connecting the probability of a configuration in the stationary distribution to its number of zero-one borders-the article offers both numerical and theoretical insight into the long-term behavior of synchronous cellular automata.

A generalized cellular automata approach to modeling first order ...

Indian Academy of Sciences (India)

... inhibitors deforming the allosteric site or inhibitors changing the structure of active ... Cell-based models with discrete state variables, such as Cellular Automata ... capture the essential features of a discrete real system, consisting of space, ...

A 3-D model of tumor progression based on complex automata driven by particle dynamics.

Science.gov (United States)

Wcisło, Rafał; Dzwinel, Witold; Yuen, David A; Dudek, Arkadiusz Z

2009-12-01

The dynamics of a growing tumor involving mechanical remodeling of healthy tissue and vasculature is neglected in most of the existing tumor models. This is due to the lack of efficient computational framework allowing for simulation of mechanical interactions. Meanwhile, just these interactions trigger critical changes in tumor growth dynamics and are responsible for its volumetric and directional progression. We describe here a novel 3-D model of tumor growth, which combines particle dynamics with cellular automata concept. The particles represent both tissue cells and fragments of the vascular network. They interact with their closest neighbors via semi-harmonic central forces simulating mechanical resistance of the cell walls. The particle dynamics is governed by both the Newtonian laws of motion and the cellular automata rules. These rules can represent cell life-cycle and other biological interactions involving smaller spatio-temporal scales. We show that our complex automata, particle based model can reproduce realistic 3-D dynamics of the entire system consisting of the tumor, normal tissue cells, blood vessels and blood flow. It can explain phenomena such as the inward cell motion in avascular tumor, stabilization of tumor growth by the external pressure, tumor vascularization due to the process of angiogenesis, trapping of healthy cells by invading tumor, and influence of external (boundary) conditions on the direction of tumor progression. We conclude that the particle model can serve as a general framework for designing advanced multiscale models of tumor dynamics and it is very competitive to the modeling approaches presented before.

Complex Automata: Multi-scale Modeling with Coupled Cellular Automata

NARCIS (Netherlands)

Hoekstra, A.G.; Caiazzo, A.; Lorenz, E.; Falcone, J.-L.; Chopard, B.; Hoekstra, A.G.; Kroc, J.; Sloot, P.M.A.

2010-01-01

Cellular Automata (CA) are generally acknowledged to be a powerful way to describe and model natural phenomena [1-3]. There are even tempting claims that nature itself is one big (quantum) information processing system, e.g. [4], and that CA may actually be nature’s way to do this processing [5-7].

MTL-Model Checking of One-Clock Parametric Timed Automata is Undecidable

Directory of Open Access Journals (Sweden)

Karin Quaas

2014-03-01

Full Text Available Parametric timed automata extend timed automata (Alur and Dill, 1991 in that they allow the specification of parametric bounds on the clock values. Since their introduction in 1993 by Alur, Henzinger, and Vardi, it is known that the emptiness problem for parametric timed automata with one clock is decidable, whereas it is undecidable if the automaton uses three or more parametric clocks. The problem is open for parametric timed automata with two parametric clocks. Metric temporal logic, MTL for short, is a widely used specification language for real-time systems. MTL-model checking of timed automata is decidable, no matter how many clocks are used in the timed automaton. In this paper, we prove that MTL-model checking for parametric timed automata is undecidable, even if the automaton uses only one clock and one parameter and is deterministic.

Station Model for Rail Transit System Using Cellular Automata

International Nuclear Information System (INIS)

Xun Jing; Ning Bin; Li Keping

2009-01-01

In this paper, we propose a new cellular automata model to simulate the railway traffic at station. Based on NaSch model, the proposed station model is composed of the main track and the siding track. Two different schemes for trains passing through station are considered. One is the scheme of 'pass by the main track, start and stop by the siding track'. The other is the scheme of 'two tracks play the same role'. We simulate the train movement using the proposed model and analyze the traffic flow at station. The simulation results demonstrate that the proposed cellular automata model can be successfully used for the simulations of railway traffic. Some characteristic behaviors of railway traffic flow can be reproduced. Moreover, the simulation values of the minimum headway are close to the theoretical values. This result demonstrates the dependability and availability of the proposed model. (general)

Finite automata over algebraic structures: models and some methods of analysis

Directory of Open Access Journals (Sweden)

Volodymyr V. Skobelev

2015-10-01

Full Text Available In this paper some results of research in two new trends of finite automata theory are presented. For understanding the value and the aim of these researches some short retrospective analysis of development of finite automata theory is given. The first trend deals with families of finite automata defined via recurrence relations on algebraic structures over finite rings. The problem of design of some algorithm that simulates with some accuracy any element of given family of automata is investigated. Some general scheme for design of families of hash functions defined by outputless automata is elaborated. Computational security of these families of hash functions is analyzed. Automata defined on varieties with some algebra are presented and their homomorphisms are characterized. Special case of these automata, namely automata on elliptic curves, are investigated in detail. The second trend deals with quantum automata. Languages accepted by some basic models of quantum automata under supposition that unitary operators associated with input alphabet commute each with the others are characterized.

On the derivation of approximations to cellular automata models and the assumption of independence.

Science.gov (United States)

Davies, K J; Green, J E F; Bean, N G; Binder, B J; Ross, J V

2014-07-01

Cellular automata are discrete agent-based models, generally used in cell-based applications. There is much interest in obtaining continuum models that describe the mean behaviour of the agents in these models. Previously, continuum models have been derived for agents undergoing motility and proliferation processes, however, these models only hold under restricted conditions. In order to narrow down the reason for these restrictions, we explore three possible sources of error in deriving the model. These sources are the choice of limiting arguments, the use of a discrete-time model as opposed to a continuous-time model and the assumption of independence between the state of sites. We present a rigorous analysis in order to gain a greater understanding of the significance of these three issues. By finding a limiting regime that accurately approximates the conservation equation for the cellular automata, we are able to conclude that the inaccuracy between our approximation and the cellular automata is completely based on the assumption of independence. Copyright © 2014 Elsevier Inc. All rights reserved.

Complementation of coalgebra automata

NARCIS (Netherlands)

Kissig, C.; Venema, Y.

2009-01-01

Coalgebra automata, introduced by the second author, generalize the well-known automata that operate on infinite words/streams, trees, graphs or transition systems. This coalgebraic perspective on automata lays foundation to a universal theory of automata operating on infinite models of computation.

A cryptosystem based on elementary cellular automata

Science.gov (United States)

Abdo, A. A.; Lian, Shiguo; Ismail, I. A.; Amin, M.; Diab, H.

2013-01-01

Based on elementary cellular automata, a new image encryption algorithm is proposed in this paper. In this algorithm, a special kind of periodic boundary cellular automata with unity attractors is used. From the viewpoint of security, the number of cellular automata attractor states are changed with respect to the encrypted image, and different key streams are used to encrypt different plain images. The cellular neural network with chaotic properties is used as the generator of a pseudo-random key stream. Theoretical analysis and experimental results have both confirmed that the proposed algorithm possesses high security level and good performances against differential and statistical attacks. The comparison with other existing schemes is given, which shows the superiority of the proposal scheme.

Cellular-automata method for phase unwrapping

International Nuclear Information System (INIS)

Ghiglia, D.C.; Mastin, G.A.; Romero, L.A.

1987-01-01

Research into two-dimensional phase unwrapping has uncovered interesting and troublesome inconsistencies that cause path-dependent results. Cellular automata, which are simple, discrete mathematical systems, offered promise of computation in nondirectional, parallel manner. A cellular automaton was discovered that can unwrap consistent phase data in n dimensions in a path-independent manner and can automatically accommodate noise-induced (pointlike) inconsistencies and arbitrary boundary conditions (region partitioning). For data with regional (nonpointlike) inconsistencies, no phase-unwrapping algorithm will converge, including the cellular-automata approach. However, the automata method permits more simple visualization of the regional inconsistencies. Examples of its behavior on one- and two-dimensional data are presented

Learning automata an introduction

CERN Document Server

Narendra, Kumpati S

2012-01-01

This self-contained introductory text on the behavior of learning automata focuses on how a sequential decision-maker with a finite number of choices responds in a random environment. Topics include fixed structure automata, variable structure stochastic automata, convergence, 0 and S models, nonstationary environments, interconnected automata and games, and applications of learning automata. A must for all students of stochastic algorithms, this treatment is the work of two well-known scientists and is suitable for a one-semester graduate course in automata theory and stochastic algorithms.

A note on limited pushdown alphabets in stateless deterministic pushdown automata

Czech Academy of Sciences Publication Activity Database

Masopust, Tomáš

2013-01-01

Roč. 24, č. 3 (2013), s. 319-328 ISSN 0129-0541 R&D Projects: GA ČR(CZ) GPP202/11/P028 Institutional support: RVO:67985840 Keywords : deterministic pushdown automata * stateless pushdown automata * realtime pushdown automata Subject RIV: BA - General Mathematics Impact factor: 0.326, year: 2013 http://www.worldscientific.com/doi/abs/10.1142/S0129054113500068

Algorithmic crystal chemistry: A cellular automata approach

International Nuclear Information System (INIS)

Krivovichev, S. V.

2012-01-01

Atomic-molecular mechanisms of crystal growth can be modeled based on crystallochemical information using cellular automata (a particular case of finite deterministic automata). In particular, the formation of heteropolyhedral layered complexes in uranyl selenates can be modeled applying a one-dimensional three-colored cellular automaton. The use of the theory of calculations (in particular, the theory of automata) in crystallography allows one to interpret crystal growth as a computational process (the realization of an algorithm or program with a finite number of steps).

Modelling robot's behaviour using finite automata

Science.gov (United States)

Janošek, Michal; Žáček, Jaroslav

2017-07-01

This paper proposes a model of a robot's behaviour described by finite automata. We split robot's knowledge into several knowledge bases which are used by the inference mechanism of the robot's expert system to make a logic deduction. Each knowledgebase is dedicated to the particular behaviour domain and the finite automaton helps us switching among these knowledge bases with the respect of actual situation. Our goal is to simplify and reduce complexity of one big knowledgebase splitting it into several pieces. The advantage of this model is that we can easily add new behaviour by adding new knowledgebase and add this behaviour into the finite automaton and define necessary states and transitions.

QM Automata: A New Class of Restricted Quantum Membrane Automata.

Science.gov (United States)

Giannakis, Konstantinos; Singh, Alexandros; Kastampolidou, Kalliopi; Papalitsas, Christos; Andronikos, Theodore

2017-01-01

The term "Unconventional Computing" describes the use of non-standard methods and models in computing. It is a recently established field, with many interesting and promising results. In this work we combine notions from quantum computing with aspects of membrane computing to define what we call QM automata. Specifically, we introduce a variant of quantum membrane automata that operate in accordance with the principles of quantum computing. We explore the functionality and capabilities of the QM automata through indicative examples. Finally we suggest future directions for research on QM automata.

Model Checking Timed Automata with Priorities using DBM Subtraction

DEFF Research Database (Denmark)

David, Alexandre; Larsen, Kim Guldstrand; Pettersson, Paul

2006-01-01

In this paper we describe an extension of timed automata with priorities, and efficient algorithms to compute subtraction on DBMs (difference bounded matrices), needed in symbolic model-checking of timed automata with priorities. The subtraction is one of the few operations on DBMs that result...... in a non-convex set needing sets of DBMs for representation. Our subtraction algorithms are efficient in the sense that the number of generated DBMs is significantly reduced compared to a naive algorithm. The overhead in time is compensated by the gain from reducing the number of resulting DBMs since...... this number affects the performance of symbolic model-checking. The uses of the DBM subtraction operation extend beyond timed automata with priorities. It is also useful for allowing guards on transitions with urgent actions, deadlock checking, and timed games....

Minimum-Cost Reachability for Priced Timed Automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Fehnker, Ansgar; Hune, Thomas Seidelin

2001-01-01

This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine...... the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques...

Universal map for cellular automata

International Nuclear Information System (INIS)

García-Morales, V.

2012-01-01

A universal map is derived for all deterministic 1D cellular automata (CAs) containing no freely adjustable parameters and valid for any alphabet size and any neighborhood range (including non-symmetrical neighborhoods). The map can be extended to an arbitrary number of dimensions and topologies and to arbitrary order in time. Specific CA maps for the famous Conway's Game of Life and Wolfram's 256 elementary CAs are given. An induction method for CAs, based in the universal map, allows mathematical expressions for the orbits of a wide variety of elementary CAs to be systematically derived. -- Highlights: ► A universal map is derived for all deterministic 1D cellular automata (CA). ► The map is generalized to 2D for Von Neumann, Moore and hexagonal neighborhoods. ► A map for all Wolfram's 256 elementary CAs is derived. ► A map for Conway's “Game of Life” is obtained.

Mathematical approaches for complexity/predictivity trade-offs in complex system models : LDRD final report.

Energy Technology Data Exchange (ETDEWEB)

Goldsby, Michael E.; Mayo, Jackson R.; Bhattacharyya, Arnab (Massachusetts Institute of Technology, Cambridge, MA); Armstrong, Robert C.; Vanderveen, Keith

2008-09-01

The goal of this research was to examine foundational methods, both computational and theoretical, that can improve the veracity of entity-based complex system models and increase confidence in their predictions for emergent behavior. The strategy was to seek insight and guidance from simplified yet realistic models, such as cellular automata and Boolean networks, whose properties can be generalized to production entity-based simulations. We have explored the usefulness of renormalization-group methods for finding reduced models of such idealized complex systems. We have prototyped representative models that are both tractable and relevant to Sandia mission applications, and quantified the effect of computational renormalization on the predictive accuracy of these models, finding good predictivity from renormalized versions of cellular automata and Boolean networks. Furthermore, we have theoretically analyzed the robustness properties of certain Boolean networks, relevant for characterizing organic behavior, and obtained precise mathematical constraints on systems that are robust to failures. In combination, our results provide important guidance for more rigorous construction of entity-based models, which currently are often devised in an ad-hoc manner. Our results can also help in designing complex systems with the goal of predictable behavior, e.g., for cybersecurity.

Designing beauty the art of cellular automata

CERN Document Server

Martínez, Genaro

2016-01-01

This fascinating, colourful book offers in-depth insights and first-hand working experiences in the production of art works, using simple computational models with rich morphological behaviour, at the edge of mathematics, computer science, physics and biology. It organically combines ground breaking scientific discoveries in the theory of computation and complex systems with artistic representations of the research results. In this appealing book mathematicians, computer scientists, physicists, and engineers brought together marvelous and esoteric patterns generated by cellular automata, which are arrays of simple machines with complex behavior. Configurations produced by cellular automata uncover mechanics of dynamic patterns formation, their propagation and interaction in natural systems: heart pacemaker, bacterial membrane proteins, chemical rectors, water permeation in soil, compressed gas, cell division, population dynamics, reaction-diffusion media and self-organisation. The book inspires artists to tak...

A cellular automata model of traffic flow with variable probability of randomization

International Nuclear Information System (INIS)

Zheng Wei-Fan; Zhang Ji-Ye

2015-01-01

Research on the stochastic behavior of traffic flow is important to understand the intrinsic evolution rules of a traffic system. By introducing an interactional potential of vehicles into the randomization step, an improved cellular automata traffic flow model with variable probability of randomization is proposed in this paper. In the proposed model, the driver is affected by the interactional potential of vehicles before him, and his decision-making process is related to the interactional potential. Compared with the traditional cellular automata model, the modeling is more suitable for the driver’s random decision-making process based on the vehicle and traffic situations in front of him in actual traffic. From the improved model, the fundamental diagram (flow–density relationship) is obtained, and the detailed high-density traffic phenomenon is reproduced through numerical simulation. (paper)

Simulation of root forms using cellular automata model

International Nuclear Information System (INIS)

Winarno, Nanang; Prima, Eka Cahya; Afifah, Ratih Mega Ayu

2016-01-01

This research aims to produce a simulation program for root forms using cellular automata model. Stephen Wolfram in his book entitled “A New Kind of Science” discusses the formation rules based on the statistical analysis. In accordance with Stephen Wolfram’s investigation, the research will develop a basic idea of computer program using Delphi 7 programming language. To best of our knowledge, there is no previous research developing a simulation describing root forms using the cellular automata model compared to the natural root form with the presence of stone addition as the disturbance. The result shows that (1) the simulation used four rules comparing results of the program towards the natural photographs and each rule had shown different root forms; (2) the stone disturbances prevent the root growth and the multiplication of root forms had been successfully modeled. Therefore, this research had added some stones, which have size of 120 cells placed randomly in the soil. Like in nature, stones cannot be penetrated by plant roots. The result showed that it is very likely to further develop the program of simulating root forms by 50 variations

Simulation of root forms using cellular automata model

Energy Technology Data Exchange (ETDEWEB)

Winarno, Nanang, E-mail: nanang-winarno@upi.edu; Prima, Eka Cahya [International Program on Science Education, Universitas Pendidikan Indonesia, Jl. Dr. Setiabudi no 229, Bandung40154 (Indonesia); Afifah, Ratih Mega Ayu [Department of Physics Education, Post Graduate School, Universitas Pendidikan Indonesia, Jl. Dr. Setiabudi no 229, Bandung40154 (Indonesia)

2016-02-08

This research aims to produce a simulation program for root forms using cellular automata model. Stephen Wolfram in his book entitled “A New Kind of Science” discusses the formation rules based on the statistical analysis. In accordance with Stephen Wolfram’s investigation, the research will develop a basic idea of computer program using Delphi 7 programming language. To best of our knowledge, there is no previous research developing a simulation describing root forms using the cellular automata model compared to the natural root form with the presence of stone addition as the disturbance. The result shows that (1) the simulation used four rules comparing results of the program towards the natural photographs and each rule had shown different root forms; (2) the stone disturbances prevent the root growth and the multiplication of root forms had been successfully modeled. Therefore, this research had added some stones, which have size of 120 cells placed randomly in the soil. Like in nature, stones cannot be penetrated by plant roots. The result showed that it is very likely to further develop the program of simulating root forms by 50 variations.

The Determining Finite Automata Process

Directory of Open Access Journals (Sweden)

M. S. Vinogradova

2017-01-01

Full Text Available The theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the approach to the synthesis of the mobile robot controls, for example, based on the theory of formal languages, there are problems concerning the construction of various finite automata, but such finite automata, as a rule, will not be deterministic. The algorithm of determinization can be applied to the finite automata, as specified, in various ways. The basic ideas of the algorithm of determinization can be most simply explained using the representations of a finite automaton in the form of a weighted directed graph.The paper deals with finite automata represented as weighted directed graphs, and discusses in detail the procedure for determining the finite automata represented in this way. Gives a detailed description of the algorithm for determining finite automata. A large number of examples illustrate a capability of the determinization algorithm.

Efficient Modelling and Generation of Markov Automata

NARCIS (Netherlands)

Koutny, M.; Timmer, Mark; Ulidowski, I.; Katoen, Joost P.; van de Pol, Jan Cornelis; Stoelinga, Mariëlle Ida Antoinette

This paper introduces a framework for the efficient modelling and generation of Markov automata. It consists of (1) the data-rich process-algebraic language MAPA, allowing concise modelling of systems with nondeterminism, probability and Markovian timing; (2) a restricted form of the language, the

Computational Modeling of Proteins based on Cellular Automata: A Method of HP Folding Approximation.

Science.gov (United States)

Madain, Alia; Abu Dalhoum, Abdel Latif; Sleit, Azzam

2018-06-01

The design of a protein folding approximation algorithm is not straightforward even when a simplified model is used. The folding problem is a combinatorial problem, where approximation and heuristic algorithms are usually used to find near optimal folds of proteins primary structures. Approximation algorithms provide guarantees on the distance to the optimal solution. The folding approximation approach proposed here depends on two-dimensional cellular automata to fold proteins presented in a well-studied simplified model called the hydrophobic-hydrophilic model. Cellular automata are discrete computational models that rely on local rules to produce some overall global behavior. One-third and one-fourth approximation algorithms choose a subset of the hydrophobic amino acids to form H-H contacts. Those algorithms start with finding a point to fold the protein sequence into two sides where one side ignores H's at even positions and the other side ignores H's at odd positions. In addition, blocks or groups of amino acids fold the same way according to a predefined normal form. We intend to improve approximation algorithms by considering all hydrophobic amino acids and folding based on the local neighborhood instead of using normal forms. The CA does not assume a fixed folding point. The proposed approach guarantees one half approximation minus the H-H endpoints. This lower bound guaranteed applies to short sequences only. This is proved as the core and the folds of the protein will have two identical sides for all short sequences.

Addressing population heterogeneity and distribution in epidemics models using a cellular automata approach.

Science.gov (United States)

López, Leonardo; Burguerner, Germán; Giovanini, Leonardo

2014-04-12

The spread of an infectious disease is determined by biological and social factors. Models based on cellular automata are adequate to describe such natural systems consisting of a massive collection of simple interacting objects. They characterize the time evolution of the global system as the emergent behaviour resulting from the interaction of the objects, whose behaviour is defined through a set of simple rules that encode the individual behaviour and the transmission dynamic. An epidemic is characterized trough an individual-based-model built upon cellular automata. In the proposed model, each individual of the population is represented by a cell of the automata. This way of modeling an epidemic situation allows to individually define the characteristic of each individual, establish different scenarios and implement control strategies. A cellular automata model to study the time evolution of a heterogeneous populations through the various stages of disease was proposed, allowing the inclusion of individual heterogeneity, geographical characteristics and social factors that determine the dynamic of the desease. Different assumptions made to built the classical model were evaluated, leading to following results: i) for low contact rate (like in quarantine process or low density population areas) the number of infective individuals is lower than other areas where the contact rate is higher, and ii) for different initial spacial distributions of infected individuals different epidemic dynamics are obtained due to its influence on the transition rate and the reproductive ratio of disease. The contact rate and spatial distributions have a central role in the spread of a disease. For low density populations the spread is very low and the number of infected individuals is lower than in highly populated areas. The spacial distribution of the population and the disease focus as well as the geographical characteristic of the area play a central role in the dynamics of the

Three-dimensional cellular automata as a model of a seismic fault

International Nuclear Information System (INIS)

Gálvez, G; Muñoz, A

2017-01-01

The Earth's crust is broken into a series of plates, whose borders are the seismic fault lines and it is where most of the earthquakes occur. This plating system can in principle be described by a set of nonlinear coupled equations describing the motion of the plates, its stresses, strains and other characteristics. Such a system of equations is very difficult to solve, and nonlinear parts leads to a chaotic behavior, which is not predictable. In 1989, Bak and Tang presented an earthquake model based on the sand pile cellular automata. The model though simple, provides similar results to those observed in actual earthquakes. In this work the cellular automata in three dimensions is proposed as a best model to approximate a seismic fault. It is noted that the three-dimensional model reproduces similar properties to those observed in real seismicity, especially, the Gutenberg-Richter law. (paper)

Quantum features of natural cellular automata

International Nuclear Information System (INIS)

Elze, Hans-Thomas

2016-01-01

Cellular automata can show well known features of quantum mechanics, such as a linear rule according to which they evolve and which resembles a discretized version of the Schrödinger equation. This includes corresponding conservation laws. The class of “natural” Hamiltonian cellular automata is based exclusively on integer-valued variables and couplings and their dynamics derives from an Action Principle. They can be mapped reversibly to continuum models by applying Sampling Theory. Thus, “deformed” quantum mechanical models with a finite discreteness scale l are obtained, which for l → 0 reproduce familiar continuum results. We have recently demonstrated that such automata can form “multipartite” systems consistently with the tensor product structures of nonrelativistic many-body quantum mechanics, while interacting and maintaining the linear evolution. Consequently, the Superposition Principle fully applies for such primitive discrete deterministic automata and their composites and can produce the essential quantum effects of interference and entanglement. (paper)

Genetic Algorithm Calibration of Probabilistic Cellular Automata for Modeling Mining Permit Activity

Science.gov (United States)

Louis, S.J.; Raines, G.L.

2003-01-01

We use a genetic algorithm to calibrate a spatially and temporally resolved cellular automata to model mining activity on public land in Idaho and western Montana. The genetic algorithm searches through a space of transition rule parameters of a two dimensional cellular automata model to find rule parameters that fit observed mining activity data. Previous work by one of the authors in calibrating the cellular automaton took weeks - the genetic algorithm takes a day and produces rules leading to about the same (or better) fit to observed data. These preliminary results indicate that genetic algorithms are a viable tool in calibrating cellular automata for this application. Experience gained during the calibration of this cellular automata suggests that mineral resource information is a critical factor in the quality of the results. With automated calibration, further refinements of how the mineral-resource information is provided to the cellular automaton will probably improve our model.

Horn clause verification with convex polyhedral abstraction and tree automata-based refinement

DEFF Research Database (Denmark)

Kafle, Bishoksan; Gallagher, John Patrick

2017-01-01

In this paper we apply tree-automata techniques to refinement of abstract interpretation in Horn clause verification. We go beyond previous work on refining trace abstractions; firstly we handle tree automata rather than string automata and thereby can capture traces in any Horn clause derivations...... underlying the Horn clauses. Experiments using linear constraint problems and the abstract domain of convex polyhedra show that the refinement technique is practical and that iteration of abstract interpretation with tree automata-based refinement solves many challenging Horn clause verification problems. We...... compare the results with other state-of-the-art Horn clause verification tools....

Cellular Automata Simulation for Wealth Distribution

Science.gov (United States)

Lo, Shih-Ching

2009-08-01

Wealth distribution of a country is a complicate system. A model, which is based on the Epstein & Axtell's "Sugars cape" model, is presented in Netlogo. The model considers the income, age, working opportunity and salary as control variables. There are still other variables should be considered while an artificial society is established. In this study, a more complicate cellular automata model for wealth distribution model is proposed. The effects of social welfare, tax, economical investment and inheritance are considered and simulated. According to the cellular automata simulation for wealth distribution, we will have a deep insight of financial policy of the government.

Compositions of (max, +) automata

Czech Academy of Sciences Publication Activity Database

Lahaye, S.; Komenda, Jan; Boimond, J.-L.

2015-01-01

Roč. 25, 1-2 (2015), s. 323-344 ISSN 0924-6703 R&D Projects: GA ČR(CZ) GAP103/11/0517 Institutional support: RVO:67985840 Keywords : (max,+) automata * synchronous product * asynchronous product Subject RIV: BA - General Mathematics Impact factor: 1.268, year: 2015 http://link.springer.com/article/10.1007/s10626-014-0186-6

Chaotic behavior in the disorder cellular automata

International Nuclear Information System (INIS)

Ko, J.-Y.; Hung, Y.-C.; Ho, M.-C.; Jiang, I-M.

2008-01-01

Disordered cellular automata (DCA) represent an intermediate class between elementary cellular automata and the Kauffman network. Recently, Rule 126 of DCA has been explicated: the system can be accurately described by a discrete probability function. However, a means of extending to other rules has not been developed. In this investigation, a density map of the dynamical behavior of DCA is formulated based on Rule 22 and other totalistic rules. The numerical results reveal excellent agreement between the model and original automata. Furthermore, the inhomogeneous situation is also discussed

Height-Deterministic Pushdown Automata

DEFF Research Database (Denmark)

Nowotka, Dirk; Srba, Jiri

2007-01-01

We define the notion of height-deterministic pushdown automata, a model where for any given input string the stack heights during any (nondeterministic) computation on the input are a priori fixed. Different subclasses of height-deterministic pushdown automata, strictly containing the class...... of regular languages and still closed under boolean language operations, are considered. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes all the formalisms proposed so far by employing height-deterministic pushdown automata...

From Orchestration to Choreography through Contract Automata

Directory of Open Access Journals (Sweden)

Davide Basile

2014-10-01

Full Text Available We study the relations between a contract automata and an interaction model. In the former model, distributed services are abstracted away as automata - oblivious of their partners - that coordinate with each other through an orchestrator. The interaction model relies on channel-based asynchronous communication and choreography to coordinate distributed services. We define a notion of strong agreement on the contract model, exhibit a natural mapping from the contract model to the interaction model, and give conditions to ensure that strong agreement corresponds to well-formed choreography.

Finite automata, their algebras and grammars towards a theory of formal expressions

CERN Document Server

Büchi, J Richard

1989-01-01

The author, who died in 1984, is well-known both as a person and through his research in mathematical logic and theoretical computer science. In the first part of the book he presents the new classical theory of finite automata as unary algebras which he himself invented about 30 years ago. Many results, like his work on structure lattices or his characterization of regular sets by generalized regular rules, are unknown to a wider audience. In the second part of the book he extends the theory to general (non-unary, many-sorted) algebras, term rewriting systems, tree automata, and pushdown automata. Essentially Büchi worked independent of other rersearch, following a novel and stimulating approach. He aimed for a mathematical theory of terms, but could not finish the book. Many of the results are known by now, but to work further along this line presents a challenging research program on the borderline between universal algebra, term rewriting systems, and automata theory. For the whole book and aga...

Image Encryption Scheme Based on Balanced Two-Dimensional Cellular Automata

Directory of Open Access Journals (Sweden)

Xiaoyan Zhang

2013-01-01

Full Text Available Cellular automata (CA are simple models of computation which exhibit fascinatingly complex behavior. Due to the universality of CA model, it has been widely applied in traditional cryptography and image processing. The aim of this paper is to present a new image encryption scheme based on balanced two-dimensional cellular automata. In this scheme, a random image with the same size of the plain image to be encrypted is first generated by a pseudo-random number generator with a seed. Then, the random image is evoluted alternately with two balanced two-dimensional CA rules. At last, the cipher image is obtained by operating bitwise XOR on the final evolution image and the plain image. This proposed scheme possesses some advantages such as very large key space, high randomness, complex cryptographic structure, and pretty fast encryption/decryption speed. Simulation results obtained from some classical images at the USC-SIPI database demonstrate the strong performance of the proposed image encryption scheme.

Behavioral Modeling Based on Probabilistic Finite Automata: An Empirical Study.

Science.gov (United States)

Tîrnăucă, Cristina; Montaña, José L; Ontañón, Santiago; González, Avelino J; Pardo, Luis M

2016-06-24

Imagine an agent that performs tasks according to different strategies. The goal of Behavioral Recognition (BR) is to identify which of the available strategies is the one being used by the agent, by simply observing the agent's actions and the environmental conditions during a certain period of time. The goal of Behavioral Cloning (BC) is more ambitious. In this last case, the learner must be able to build a model of the behavior of the agent. In both settings, the only assumption is that the learner has access to a training set that contains instances of observed behavioral traces for each available strategy. This paper studies a machine learning approach based on Probabilistic Finite Automata (PFAs), capable of achieving both the recognition and cloning tasks. We evaluate the performance of PFAs in the context of a simulated learning environment (in this case, a virtual Roomba vacuum cleaner robot), and compare it with a collection of other machine learning approaches.

Minimum-Cost Reachability for Priced Timed Automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Fehnker, Ansgar; Hune, Thomas Seidelin

2001-01-01

This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine...... the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques...... and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them....

Simulating Urban Growth Using a Random Forest-Cellular Automata (RF-CA Model

Directory of Open Access Journals (Sweden)

Courage Kamusoko

2015-04-01

Full Text Available Sustainable urban planning and management require reliable land change models, which can be used to improve decision making. The objective of this study was to test a random forest-cellular automata (RF-CA model, which combines random forest (RF and cellular automata (CA models. The Kappa simulation (KSimulation, figure of merit, and components of agreement and disagreement statistics were used to validate the RF-CA model. Furthermore, the RF-CA model was compared with support vector machine cellular automata (SVM-CA and logistic regression cellular automata (LR-CA models. Results show that the RF-CA model outperformed the SVM-CA and LR-CA models. The RF-CA model had a Kappa simulation (KSimulation accuracy of 0.51 (with a figure of merit statistic of 47%, while SVM-CA and LR-CA models had a KSimulation accuracy of 0.39 and −0.22 (with figure of merit statistics of 39% and 6%, respectively. Generally, the RF-CA model was relatively accurate at allocating “non-built-up to built-up” changes as reflected by the correct “non-built-up to built-up” components of agreement of 15%. The performance of the RF-CA model was attributed to the relatively accurate RF transition potential maps. Therefore, this study highlights the potential of the RF-CA model for simulating urban growth.

Cellular automata a parallel model

CERN Document Server

Mazoyer, J

1999-01-01

Cellular automata can be viewed both as computational models and modelling systems of real processes. This volume emphasises the first aspect. In articles written by leading researchers, sophisticated massive parallel algorithms (firing squad, life, Fischer's primes recognition) are treated. Their computational power and the specific complexity classes they determine are surveyed, while some recent results in relation to chaos from a new dynamic systems point of view are also presented. Audience: This book will be of interest to specialists of theoretical computer science and the parallelism challenge.

Computer Models and Automata Theory in Biology and Medicine

CERN Document Server

Baianu, I C

2004-01-01

The applications of computers to biological and biomedical problem solving goes back to the very beginnings of computer science, automata theory [1], and mathematical biology [2]. With the advent of more versatile and powerful computers, biological and biomedical applications of computers have proliferated so rapidly that it would be virtually impossible to compile a comprehensive review of all developments in this field. Limitations of computer simulations in biology have also come under close scrutiny, and claims have been made that biological systems have limited information processing power [3]. Such general conjectures do not, however, deter biologists and biomedical researchers from developing new computer applications in biology and medicine. Microprocessors are being widely employed in biological laboratories both for automatic data acquisition/processing and modeling; one particular area, which is of great biomedical interest, involves fast digital image processing and is already established for rout...

Fuzzy cellular automata models in immunology

International Nuclear Information System (INIS)

Ahmed, E.

1996-01-01

The self-nonself character of antigens is considered to be fuzzy. The Chowdhury et al. cellular automata model is generalized accordingly. New steady states are found. The first corresponds to a below-normal help and suppression and is proposed to be related to autoimmune diseases. The second corresponds to a below-normal B-cell level

Car-following Behavior Model Learning Using Timed Automata

NARCIS (Netherlands)

Zhang, Yihuan; Lin, Q.; Wang, Jun; Verwer, S.E.; Dochain, D.; Henrion, D.; Peaucelle, D.

Learning driving behavior is fundamental for autonomous vehicles to “understand” traffic situations. This paper proposes a novel method for learning a behavioral model of car-following using automata learning algorithms. The model is interpretable for car-following behavior analysis. Frequent common

Efficient Translation of LTL Formulae into Buchi Automata

Science.gov (United States)

Giannakopoulou, Dimitra; Lerda, Flavio

2001-01-01

Model checking is a fully automated technique for checking that a system satisfies a set of required properties. With explicit-state model checkers, properties are typically defined in linear-time temporal logic (LTL), and are translated into B chi automata in order to be checked. This report presents how we have combined and improved existing techniques to obtain an efficient LTL to B chi automata translator. In particular, we optimize the core of existing tableau-based approaches to generate significantly smaller automata. Our approach has been implemented and is being released as part of the Java PathFinder software (JPF), an explicit state model checker under development at the NASA Ames Research Center.

Multi-head Watson-Crick automata

OpenAIRE

Chatterjee, Kingshuk; Ray, Kumar Sankar

2015-01-01

Inspired by multi-head finite automata and Watson-Crick automata in this paper, we introduce new structure namely multi-head Watson-Crick automata where we replace the single tape of multi-head finite automaton by a DNA double strand. The content of the second tape is determined using a complementarity relation similar to Watson-Crick complementarity relation. We establish the superiority of our model over multi-head finite automata and also show that both the deterministic and non-determinis...

Glider-based computing in reaction-diffusion hexagonal cellular automata

International Nuclear Information System (INIS)

Adamatzky, Andrew; Wuensche, Andrew; De Lacy Costello, Benjamin

2006-01-01

A three-state hexagonal cellular automaton, discovered in [Wuensche A. Glider dynamics in 3-value hexagonal cellular automata: the beehive rule. Int J Unconvention Comput, in press], presents a conceptual discrete model of a reaction-diffusion system with inhibitor and activator reagents. The automaton model of reaction-diffusion exhibits mobile localized patterns (gliders) in its space-time dynamics. We show how to implement the basic computational operations with these mobile localizations, and thus demonstrate collision-based logical universality of the hexagonal reaction-diffusion cellular automaton

Mode automata and their compilation into fault trees

International Nuclear Information System (INIS)

Rauzy, Antoine

2002-01-01

In this article, we advocate the use of mode automata as a high level representation language for reliability studies. Mode automata are states/transitions based representations with the additional notion of flow. They can be seen as a generalization of both finite capacity Petri nets and block diagrams. They can be assembled into hierarchies by means of composition operations. The contribution of this article is twofold. First, we introduce mode automata and we discuss their relationship with other formalisms. Second, we propose an algorithm to compile mode automata into Boolean equations (fault trees). Such a compilation is of interest for two reasons. First, assessment tools for Boolean models are much more efficient than those for states/transitions models. Second, the automated generation of fault trees from higher level representations makes easier their maintenance through the life cycle of systems under study

A cellular automata model for ant trails

Indian Academy of Sciences (India)

In this study, the unidirectional ant traffic flow with U-turn in an ant trail was investigated using one-dimensional cellular automata model. It is known that ants communicate with each other by dropping a chemical, called pheromone, on the substrate. Apart from the studies in the literature, it was considered in the model that ...

Lower and Upper Bounds in Zone Based Abstractions of Timed Automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Bouyer, Patricia; Larsen, Kim Guldstrand

2004-01-01

Timed automata have an infinite semantics. For verification purposes, one usually uses zone based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds, significantly coarser abstractions can...... dramatically increases the scalability of the real-time model checker Uppaal....

What will be eventually true of polymomial hybrid automata

DEFF Research Database (Denmark)

Fränzle, Martin

2001-01-01

Hybrid automata have been introduced in both control engineering and computer science as a formal model for the dynamics of hybrid discrete-continuous systems. While computability issues concerning safety properties have been extensively studied, liveness properties have remained largely uninvest......Hybrid automata have been introduced in both control engineering and computer science as a formal model for the dynamics of hybrid discrete-continuous systems. While computability issues concerning safety properties have been extensively studied, liveness properties have remained largely...... uninvestigated. In this article, we investigate decidability of state recurrence and of progress properties. First, we show that state recurrence and progress are in general undecidable for polynomial hybrid automata. Then, we demonstrate that they are closely related for hybrid automata subject to a simple...... model of noise, even though these automata are infinite-state systems. Based on this, we augment a semi-decision procedure for recurrence with a semi-decision method for length-boundedness of paths in such a way that we obtain an automatic verification method for progress properties of linear...

Cellular automata and integrodifferential equation models for cell renewal in mosaic tissues

Science.gov (United States)

Bloomfield, J. M.; Sherratt, J. A.; Painter, K. J.; Landini, G.

2010-01-01

Mosaic tissues are composed of two or more genetically distinct cell types. They occur naturally, and are also a useful experimental method for exploring tissue growth and maintenance. By marking the different cell types, one can study the patterns formed by proliferation, renewal and migration. Here, we present mathematical modelling suggesting that small changes in the type of interaction that cells have with their local cellular environment can lead to very different outcomes for the composition of mosaics. In cell renewal, proliferation of each cell type may depend linearly or nonlinearly on the local proportion of cells of that type, and these two possibilities produce very different patterns. We study two variations of a cellular automaton model based on simple rules for renewal. We then propose an integrodifferential equation model, and again consider two different forms of cellular interaction. The results of the continuous and cellular automata models are qualitatively the same, and we observe that changes in local environment interaction affect the dynamics for both. Furthermore, we demonstrate that the models reproduce some of the patterns seen in actual mosaic tissues. In particular, our results suggest that the differing patterns seen in organ parenchymas may be driven purely by the process of cell replacement under different interaction scenarios. PMID:20375040

Performance of Сellular Automata-based Stream Ciphers in GPU Implementation

Directory of Open Access Journals (Sweden)

P. G. Klyucharev

2016-01-01

Full Text Available Earlier the author had developed methods to build high-performance generalized cellular automata-based symmetric ciphers, which allow obtaining the encryption algorithms that show extremely high performance in hardware implementation. However, their implementation based on the conventional microprocessors lacks high performance. The mere fact is quite common - it shows a scope of applications for these ciphers. Nevertheless, the use of graphic processors enables achieving an appropriate performance for a software implementation.The article is extension of a series of the articles, which study various aspects to construct and implement cryptographic algorithms based on the generalized cellular automata. The article is aimed at studying the capabilities to implement the GPU-based cryptographic algorithms under consideration.Representing a key generator, the implemented encryption algorithm comprises 2k generalized cellular automata. The cellular automata graphs are Ramanujan’s ones. The cells of produced k gamma streams alternate, thereby allowing the GPU capabilities to be better used.To implement was used OpenCL, as the most universal and platform-independent API. The software written in C ++ was designed so that the user could set various parameters, including the encryption key, the graph structure, the local communication function, various constants, etc. To test were used a variety of graphics processors (NVIDIA GTX 650; NVIDIA GTX 770; AMD R9 280X.Depending on operating conditions, and GPU used, a performance range is from 0.47 to 6.61 Gb / s, which is comparable to the performance of the countertypes.Thus, the article has demonstrated that using the GPU makes it is possible to provide efficient software implementation of stream ciphers based on the generalized cellular automata.This work was supported by the RFBR, the project №16-07-00542.

Monitoring with Data Automata

Science.gov (United States)

Havelund, Klaus

2014-01-01

We present a form of automaton, referred to as data automata, suited for monitoring sequences of data-carrying events, for example emitted by an executing software system. This form of automata allows states to be parameterized with data, forming named records, which are stored in an efficiently indexed data structure, a form of database. This very explicit approach differs from other automaton-based monitoring approaches. Data automata are also characterized by allowing transition conditions to refer to other parameterized states, and by allowing transitions sequences. The presented automaton concept is inspired by rule-based systems, especially the Rete algorithm, which is one of the well-established algorithms for executing rule-based systems. We present an optimized external DSL for data automata, as well as a comparable unoptimized internal DSL (API) in the Scala programming language, in order to compare the two solutions. An evaluation compares these two solutions to several other monitoring systems.

On the spatial dynamics and oscillatory behavior of a predator-prey model based on cellular automata and local particle swarm optimization.

Science.gov (United States)

Molina, Mario Martínez; Moreno-Armendáriz, Marco A; Carlos Seck Tuoh Mora, Juan

2013-11-07

A two-dimensional lattice model based on Cellular Automata theory and swarm intelligence is used to study the spatial and population dynamics of a theoretical ecosystem. It is found that the social interactions among predators provoke the formation of clusters, and that by increasing the mobility of predators the model enters into an oscillatory behavior. © 2013 Elsevier Ltd. All rights reserved.

Opinion evolution based on cellular automata rules in small world networks

Science.gov (United States)

Shi, Xiao-Ming; Shi, Lun; Zhang, Jie-Fang

2010-03-01

In this paper, we apply cellular automata rules, which can be given by a truth table, to human memory. We design each memory as a tracking survey mode that keeps the most recent three opinions. Each cellular automata rule, as a personal mechanism, gives the final ruling in one time period based on the data stored in one's memory. The key focus of the paper is to research the evolution of people's attitudes to the same question. Based on a great deal of empirical observations from computer simulations, all the rules can be classified into 20 groups. We highlight the fact that the phenomenon shown by some rules belonging to the same group will be altered within several steps by other rules in different groups. It is truly amazing that, compared with the last hundreds of presidential voting in America, the eras of important events in America's history coincide with the simulation results obtained by our model.

Dengue fever spreading based on probabilistic cellular automata with two lattices

Science.gov (United States)

Pereira, F. M. M.; Schimit, P. H. T.

2018-06-01

Modeling and simulation of mosquito-borne diseases have gained attention due to a growing incidence in tropical countries in the past few years. Here, we study the dengue spreading in a population modeled by cellular automata, where there are two lattices to model the human-mosquitointeraction: one lattice for human individuals, and one lattice for mosquitoes in order to enable different dynamics in populations. The disease considered is the dengue fever with one, two or three different serotypes coexisting in population. Although many regions exhibit the incidence of only one serotype, here we set a complete framework to also study the occurrence of two and three serotypes at the same time in a population. Furthermore, the flexibility of the model allows its use to other mosquito-borne diseases, like chikungunya, yellow fever and malaria. An approximation of the cellular automata is proposed in terms of ordinary differential equations; the spreading of mosquitoes is studied and the influence of some model parameters are analyzed with numerical simulations. Finally, a method to combat dengue spreading is simulated based on a reduction of mosquito birth and mosquito bites in population.

Lattice gas cellular automata and lattice Boltzmann models an introduction

CERN Document Server

Wolf-Gladrow, Dieter A

2000-01-01

Lattice-gas cellular automata (LGCA) and lattice Boltzmann models (LBM) are relatively new and promising methods for the numerical solution of nonlinear partial differential equations. The book provides an introduction for graduate students and researchers. Working knowledge of calculus is required and experience in PDEs and fluid dynamics is recommended. Some peculiarities of cellular automata are outlined in Chapter 2. The properties of various LGCA and special coding techniques are discussed in Chapter 3. Concepts from statistical mechanics (Chapter 4) provide the necessary theoretical background for LGCA and LBM. The properties of lattice Boltzmann models and a method for their construction are presented in Chapter 5.

Relating timed and register automata

Directory of Open Access Journals (Sweden)

Diego Figueira

2010-11-01

Full Text Available Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave in appearance differently, several decision problems have the same (undecidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance. This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton, and conversely that a run of a register automaton can be simulated by a timed automaton. Our results allow to transfer complexity and decidability results back and forth between these two kinds of models. We justify the usefulness of these reductions by obtaining new results on register automata.

Efficient Modelling and Generation of Markov Automata (extended version)

NARCIS (Netherlands)

Timmer, Mark; Katoen, Joost P.; van de Pol, Jan Cornelis; Stoelinga, Mariëlle Ida Antoinette

2012-01-01

This paper introduces a framework for the efficient modelling and generation of Markov automata. It consists of (1) the data-rich process-algebraic language MAPA, allowing concise modelling of systems with nondeterminism, probability and Markovian timing; (2) a restricted form of the language, the

Controller synthesis for dynamic hierarchical real-time plants using timed automata

DEFF Research Database (Denmark)

Bin Waez, Md Tawhid; Wasowski, Andrzej; Dingel, Juergen

2017-01-01

We use timed I/O automata based timed games to synthesize task-level reconfiguration services for cost-effective fault tolerance in a case study. The case study shows that state-space explosion is a severe problem for timed games. By applying suitable abstractions, we dramatically improve...... the scalability. However, timed I/O automata do not facilitate algorithmic abstraction generation techniques. The case study motivates the development of timed process automata to improve modeling and analysis for controller synthesis of time-critical plants which can be hierarchical and dynamic. The model offers...

Confluence reduction for Markov automata

NARCIS (Netherlands)

Timmer, Mark; Katoen, Joost P.; van de Pol, Jaco; Stoelinga, Mariëlle Ida Antoinette

2016-01-01

Markov automata are a novel formalism for specifying systems exhibiting nondeterminism, probabilistic choices and Markovian rates. As expected, the state space explosion threatens the analysability of these models. We therefore introduce confluence reduction for Markov automata, a powerful reduction

A half-century of automata theory celebration and inspiration

CERN Document Server

Salomaa, A; Yu, S

2001-01-01

This volume gathers lectures by 8 distinguished pioneers of automata theory, including two Turing Award winners. In each contribution, the early developments of automata theory are reminisced about and future directions are suggested. Although some of the contributions go into rather intriguing technical details, most of the book is accessible to a wide audience interested in the progress of the age of computers. The book is a must for professionals in theoretical computer science and related areas of mathematics. For students in these areas it provides an exceptionally deep view at the beginn

A generalized cellular automata approach to modeling first order ...

Indian Academy of Sciences (India)

system, consisting of space, time and state, structured with simple local rules without ... Sensitivity analysis of a stochastic cellular automata model. 413 ..... Baetens J M and De Baets B 2011 Design and parameterization of a stochastic cellular.

Simulations of fluid flow through porous media based on cellular automata and non-linear dynamics

Energy Technology Data Exchange (ETDEWEB)

Paulson, K V

1992-05-15

A study is being carried out to apply cellular automata and non-linear dynamics in the construction of efficient and accurate computer simulations of multiphase fluid flow through porous media, with the objective of application to reservoir modelling for hydrocarbon recovery. An algorithm based on Boolean operations has been developed which transforms a PC clone into a highly efficient vector processor capable of cellular automata simulation of single fluid flow through two-dimensional rock matrix models of varying porosities. Macroscopic flow patterns have been established through spatial and temporal averaging with no floating point operations. Permeabilities of the different models have been calculated. Hardware allows the algorithm to function on dual processors on a PC platform using a video recording and editing facility. Very encouraging results have been obtained. 4 figs.

PRM113 - Timed Automata Modeling of The Personalized Treatment Decisions In Metastatic Castration Resistant Prostate Cancer

NARCIS (Netherlands)

Schivo, Stefano; Degeling, K.; Degeling, Koen; Koffijberg, Hendrik; IJzerman, Maarten Joost; Langerak, Romanus

2015-01-01

Objectives The Timed Automata modeling paradigm has emerged from Computer Science as a mature tool for the functional analysis and performance evaluation of timed distributed systems. This study is a first exploration of the suitability of Timed Automata for health economic modeling, using a case

Visibly Pushdown Automata

DEFF Research Database (Denmark)

Srba, Jiri

2006-01-01

We investigate the possibility of (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds...... for a number of studied preorders and equivalences like simulation, completed simulation, ready simulation, 2-nested simulation preorders/equivalences and bisimulation equivalence. Our main results are that all the mentioned equivalences and preorders are EXPTIME-complete on visibly pushdown automata, PSPACE......-complete on visibly one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for visibly one-counter automata improves also the previously known DP-hardness results for ordinary one-counter automata and one-counter nets. Finally, we study regularity checking problems for visibly pushdown automata...

Communicative automata based programming. Society Framework

Directory of Open Access Journals (Sweden)

Andrei Micu

2015-10-01

Full Text Available One of the aims of this paper is to present a new programming paradigm based on the new paradigms intensively used in IT industry. Implementation of these techniques can improve the quality of code through modularization, not only in terms of entities used by a program, but also in terms of states in which they pass. Another aspect followed in this paper takes into account that in the development of software applications, the transition from the design to the source code is a very expensive step in terms of effort and time spent. Diagrams can hide very important details for simplicity of understanding, which can lead to incorrect or incomplete implementations. To improve this process communicative automaton based programming comes with an intermediate step. We will see how it goes after creating modeling diagrams to communicative automata and then to writing code for each of them. We show how the transition from one step to another is much easier and intuitive.

Stochastic cellular automata model of cell migration, proliferation and differentiation: validation with in vitro cultures of muscle satellite cells.

Science.gov (United States)

Garijo, N; Manzano, R; Osta, R; Perez, M A

2012-12-07

Cell migration and proliferation has been modelled in the literature as a process similar to diffusion. However, using diffusion models to simulate the proliferation and migration of cells tends to create a homogeneous distribution in the cell density that does not correlate to empirical observations. In fact, the mechanism of cell dispersal is not diffusion. Cells disperse by crawling or proliferation, or are transported in a moving fluid. The use of cellular automata, particle models or cell-based models can overcome this limitation. This paper presents a stochastic cellular automata model to simulate the proliferation, migration and differentiation of cells. These processes are considered as completely stochastic as well as discrete. The model developed was applied to predict the behaviour of in vitro cell cultures performed with adult muscle satellite cells. Moreover, non homogeneous distribution of cells has been observed inside the culture well and, using the above mentioned stochastic cellular automata model, we have been able to predict this heterogeneous cell distribution and compute accurate quantitative results. Differentiation was also incorporated into the computational simulation. The results predicted the myotube formation that typically occurs with adult muscle satellite cells. In conclusion, we have shown how a stochastic cellular automata model can be implemented and is capable of reproducing the in vitro behaviour of adult muscle satellite cells. Copyright © 2012 Elsevier Ltd. All rights reserved.

Tree automata-based refinement with application to Horn clause verification

DEFF Research Database (Denmark)

Kafle, Bishoksan; Gallagher, John Patrick

2015-01-01

In this paper we apply tree-automata techniques to refinement of abstract interpretation in Horn clause verification. We go beyond previous work on refining trace abstractions; firstly we handle tree automata rather than string automata and thereby can capture traces in any Horn clause derivation...... compare the results with other state of the art Horn clause verification tools....

On Nonlinear Prices in Timed Automata

Directory of Open Access Journals (Sweden)

Devendra Bhave

2016-12-01

Full Text Available Priced timed automata provide a natural model for quantitative analysis of real-time systems and have been successfully applied in various scheduling and planning problems. The optimal reachability problem for linearly-priced timed automata is known to be PSPACE-complete. In this paper we investigate priced timed automata with more general prices and show that in the most general setting the optimal reachability problem is undecidable. We adapt and implement the construction of Audemard, Cimatti, Kornilowicz, and Sebastiani for non-linear priced timed automata using state-of-the-art theorem prover Z3 and present some preliminary results.

Magnetohydrodynamics cellular automata

International Nuclear Information System (INIS)

Hatori, Tadatsugu.

1990-02-01

There has been a renewal of interest in cellular automata, partly because they give an architecture for a special purpose computer with parallel processing optimized to solve a particular problem. The lattice gas cellular automata are briefly surveyed, which are recently developed to solve partial differential equations such as hydrodynamics or magnetohydrodynamics. A new model is given in the present paper to implement the magnetic Lorentz force in a more deterministic and local procedure than the previous one. (author)

Magnetohydrodynamic cellular automata

Energy Technology Data Exchange (ETDEWEB)

Hatori, Tadatsugu [National Inst. for Fusion Science, Nagoya (Japan)

1990-03-01

There has been a renewal of interest in cellular automata, partly because they give an architecture for a special purpose computer with parallel processing optimized to solve a particular problem. The lattice gas cellular automata are briefly surveyed, which are recently developed to solve partial differential equations such as hydrodynamics or magnetohydrodynamics. A new model is given in the present paper to implement the magnetic Lorentz force in a more deterministic and local procedure than the previous one. (author).

Magnetohydrodynamic cellular automata

International Nuclear Information System (INIS)

Hatori, Tadatsugu

1990-01-01

There has been a renewal of interest in cellular automata, partly because they give an architecture for a special purpose computer with parallel processing optimized to solve a particular problem. The lattice gas cellular automata are briefly surveyed, which are recently developed to solve partial differential equations such as hydrodynamics or magnetohydrodynamics. A new model is given in the present paper to implement the magnetic Lorentz force in a more deterministic and local procedure than the previous one. (author)

Modeling chemical systems using cellular automata a textbook and laboratory manual

CERN Document Server

Kier, Lemont B; Cheng, Chao-Kun

2005-01-01

There are few publications on Cellular Automata and certainly no direct competition Insight into a new modeling paradigm Novel approach to the use of in silico modeling to replace or supplement costly labs.

On the Correctness of Real-Time Modular Computer Systems Modeling with Stopwatch Automata Networks

Directory of Open Access Journals (Sweden)

Alevtina B. Glonina

2018-01-01

Full Text Available In this paper, we consider a schedulability analysis problem for real-time modular computer systems (RT MCS. A system configuration is called schedulable if all the jobs finish within their deadlines. The authors propose a stopwatch automata-based general model of RT MCS operation. A model instance for a given RT MCS configuration is a network of stopwatch automata (NSA and it can be built automatically using the general model. A system operation trace, which is necessary for checking the schedulability criterion, can be obtained from the corresponding NSA trace. The paper substantiates the correctness of the proposed approach. A set of correctness requirements to models of system components and to the whole system model were derived from RT MCS specifications. The authors proved that if all models of system components satisfy the corresponding requirements, the whole system model built according to the proposed approach satisfies its correctness requirements and is deterministic (i.e. for a given configuration a trace generated by the corresponding model run is uniquely determined. The model determinism implies that any model run can be used for schedulability analysis. This fact is crucial for the approach efficiency, as the number of possible model runs grows exponentially with the number of jobs in a system. Correctness requirements to models of system components models can be checked automatically by a verifier using observer automata approach. The authors proved by using UPPAAL verifier that all the developed models of system components satisfy the corresponding requirements. User-defined models of system components can be also used for system modeling if they satisfy the requirements.

Energy Games in Multiweighted Automata

DEFF Research Database (Denmark)

Fahrenberg, U.; Juhl, L.; Larsen, Kim Guldstrand

2011-01-01

Energy games have recently attracted a lot of attention. These are games played on finite weighted automata and concern the existence of infinite runs subject to boundary constraints on the accumulated weight, allowing e.g only for behaviours where a resource is always available (nonnegative...... accumulated weight), yet does not exceed a given maximum capacity. We extend energy games to a multiweighted and parameterized setting, allowing us to model systems with multiple quantitative aspects. We present reductions between Petri nets and multiweighted automata and among different types...... of multiweighted automata and identify new complexity and (un)decidability results for both one- and two-player games. We also investigate the tractability of an extension of multiweighted energy games in the setting of timed automata....

Dynamical phase transitions in spin models and automata

International Nuclear Information System (INIS)

Derrida, B.

1989-01-01

Some of the models and methods developed in the study of the dynamics of spin models and automata are described. Special attention is given to the distance method which consists of comparing the time evolution of two configurations. The method is used to obtain the phase boundary between a frozen and a chaotic phase in the case of deterministic models. For stochastic systems the method is used to obtain dynamical phase transitions

Efficient automata constructions and approximate automata

NARCIS (Netherlands)

Watson, B.W.; Kourie, D.G.; Ngassam, E.K.; Strauss, T.; Cleophas, L.G.W.A.

2008-01-01

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern

Efficient automata constructions and approximate automata

NARCIS (Netherlands)

Watson, B.W.; Kourie, D.G.; Ngassam, E.K.; Strauss, T.; Cleophas, L.G.W.A.; Holub, J.; Zdárek, J.

2006-01-01

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern

Forest Fires, Oil Spills, and Fractal Geometry: An Investigation in Two Parts. Part 2: Using Fractal Complexity to Analyze Mathematical Models.

Science.gov (United States)

Biehl, L. Charles

1999-01-01

Presents an activity that utilizes the mathematical models of forest fires and oil spills that were generated (in the first part of this activity, published in the November 1998 issue) by students using probability and cellular automata. (ASK)

Stair evacuation simulation based on cellular automata considering evacuees’ walk preferences

International Nuclear Information System (INIS)

Ding Ning; Luh, Peter B.; Zhang Hui; Chen Tao

2015-01-01

As a physical model, the cellular automata (CA) model is widely used in many areas, such as stair evacuation. However, existing CA models do not consider evacuees’ walk preferences nor psychological status, and the structure of the basic model is unapplicable for the stair structure. This paper is to improve the stair evacuation simulation by addressing these issues, and a new cellular automata model is established. Several evacuees’ walk preference and how evacuee’s psychology influences their behaviors are introduced into this model. Evacuees’ speeds will be influenced by these features. To validate this simulation, two fire drills held in two high-rise buildings are video-recorded. It is found that the simulation results are similar to the fire drill results. The structure of this model is simple, and it is easy to further develop and utilize in different buildings with various kinds of occupants. (paper)

Automata learning algorithms and processes for providing more complete systems requirements specification by scenario generation, CSP-based syntax-oriented model construction, and R2D2C system requirements transformation

Science.gov (United States)

Hinchey, Michael G. (Inventor); Margaria, Tiziana (Inventor); Rash, James L. (Inventor); Rouff, Christopher A. (Inventor); Steffen, Bernard (Inventor)

2010-01-01

Systems, methods and apparatus are provided through which in some embodiments, automata learning algorithms and techniques are implemented to generate a more complete set of scenarios for requirements based programming. More specifically, a CSP-based, syntax-oriented model construction, which requires the support of a theorem prover, is complemented by model extrapolation, via automata learning. This may support the systematic completion of the requirements, the nature of the requirement being partial, which provides focus on the most prominent scenarios. This may generalize requirement skeletons by extrapolation and may indicate by way of automatically generated traces where the requirement specification is too loose and additional information is required.

Hybrid modelling framework by using mathematics-based and information-based methods

International Nuclear Information System (INIS)

Ghaboussi, J; Kim, J; Elnashai, A

2010-01-01

Mathematics-based computational mechanics involves idealization in going from the observed behaviour of a system into mathematical equations representing the underlying mechanics of that behaviour. Idealization may lead mathematical models that exclude certain aspects of the complex behaviour that may be significant. An alternative approach is data-centric modelling that constitutes a fundamental shift from mathematical equations to data that contain the required information about the underlying mechanics. However, purely data-centric methods often fail for infrequent events and large state changes. In this article, a new hybrid modelling framework is proposed to improve accuracy in simulation of real-world systems. In the hybrid framework, a mathematical model is complemented by information-based components. The role of informational components is to model aspects which the mathematical model leaves out. The missing aspects are extracted and identified through Autoprogressive Algorithms. The proposed hybrid modelling framework has a wide range of potential applications for natural and engineered systems. The potential of the hybrid methodology is illustrated through modelling highly pinched hysteretic behaviour of beam-to-column connections in steel frames.

A verification strategy for web services composition using enhanced stacked automata model.

Science.gov (United States)

Nagamouttou, Danapaquiame; Egambaram, Ilavarasan; Krishnan, Muthumanickam; Narasingam, Poonkuzhali

2015-01-01

Currently, Service-Oriented Architecture (SOA) is becoming the most popular software architecture of contemporary enterprise applications, and one crucial technique of its implementation is web services. Individual service offered by some service providers may symbolize limited business functionality; however, by composing individual services from different service providers, a composite service describing the intact business process of an enterprise can be made. Many new standards have been defined to decipher web service composition problem namely Business Process Execution Language (BPEL). BPEL provides an initial work for forming an Extended Markup Language (XML) specification language for defining and implementing business practice workflows for web services. The problems with most realistic approaches to service composition are the verification of composed web services. It has to depend on formal verification method to ensure the correctness of composed services. A few research works has been carried out in the literature survey for verification of web services for deterministic system. Moreover the existing models did not address the verification properties like dead transition, deadlock, reachability and safetyness. In this paper, a new model to verify the composed web services using Enhanced Stacked Automata Model (ESAM) has been proposed. The correctness properties of the non-deterministic system have been evaluated based on the properties like dead transition, deadlock, safetyness, liveness and reachability. Initially web services are composed using Business Process Execution Language for Web Service (BPEL4WS) and it is converted into ESAM (combination of Muller Automata (MA) and Push Down Automata (PDA)) and it is transformed into Promela language, an input language for Simple ProMeLa Interpreter (SPIN) tool. The model is verified using SPIN tool and the results revealed better recital in terms of finding dead transition and deadlock in contrast to the

Finding and defining the natural automata acting in living plants: Toward the synthetic biology for robotics and informatics in vivo.

Science.gov (United States)

Kawano, Tomonori; Bouteau, François; Mancuso, Stefano

2012-11-01

The automata theory is the mathematical study of abstract machines commonly studied in the theoretical computer science and highly interdisciplinary fields that combine the natural sciences and the theoretical computer science. In the present review article, as the chemical and biological basis for natural computing or informatics, some plants, plant cells or plant-derived molecules involved in signaling are listed and classified as natural sequential machines (namely, the Mealy machines or Moore machines) or finite state automata. By defining the actions (states and transition functions) of these natural automata, the similarity between the computational data processing and plant decision-making processes became obvious. Finally, their putative roles as the parts for plant-based computing or robotic systems are discussed.

Priced Timed Automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Larsen, Kim Guldstrand; Rasmussen, Jacob Illum

2004-01-01

This contribution reports on the considerable effort made recently towards extending and applying well-established timed automata technology to optimal scheduling and planning problems. The effort of the authors in this direction has to a large extent been carried out as part of the European...... projects VHS [22] and AMETIST [17] and are available in the recently released UPPAAL CORA [12], a variant of the real-time verification tool UPPAAL [20,5] specialized for cost-optimal reachability for the extended model of priced timed automata....

Supervisory control of (max,+) automata: extensions towards applications

Czech Academy of Sciences Publication Activity Database

Lahaye, S.; Komenda, Jan; Boimond, J.-L.

2015-01-01

Roč. 88, č. 12 (2015), s. 2523-2537 ISSN 0020-7179 Institutional support: RVO:67985840 Keywords : discrete event systems * logical and timed behaviors * (max,+) automata * supervisory control Subject RIV: BA - General Mathematics Impact factor: 1.880, year: 2015 http://www.tandfonline.com/doi/full/10.1080/00207179.2015.1048295

Supervisory control of (max,+) automata: extensions towards applications

Czech Academy of Sciences Publication Activity Database

Lahaye, S.; Komenda, Jan; Boimond, J.-L.

2015-01-01

Roč. 88, č. 12 (2015), s. 2523-2537 ISSN 0020-7179 Institutional support: RVO:67985840 Keywords : discrete event systems * logical and time d behaviors * (max,+) automata * supervisory control Subject RIV: BA - General Mathematics Impact factor: 1.880, year: 2015 http://www.tandfonline.com/doi/full/10.1080/00207179.2015.1048295

Phase transitions and hysteresis in a cellular automata-based model of opinion formation

International Nuclear Information System (INIS)

Kacperski, K.; Holyst, J.A.

1996-01-01

A particular case of a cellular automata-based model of two-state opinion formation in social groups with a strong leader is studied. We consider a 2D Euclidian geometry of open-quotes social spaceclose quotes and mutual interactions ∝ 1/r n . The model shows an interesting dynamics which can be analytically calculated. There are two stable states of the system: a cluster around the leader and unification. Unstable clusters may also appear. A variation in parameters such as the leader's strength or the open-quotes social temperatureclose quotes can change the size of a cluster or, when they reach some critical values, make the system jump into another state. For a certain range of parameters the system exhibits bistability and hysteresis phenomena. We obtained explicit formulas for the cluster size, critical values, make the system jump into another state. For a certain range of parameters the system exhibits bistability and hysteresis phenomena. We obtained explicit formulas for the cluster size, critical leader's strength, and critical open-quotes social temperature.close quotes These analytical results are verified by computer simulations

Automata-Based Verification of Temporal Properties on Running Programs

Science.gov (United States)

Giannakopoulou, Dimitra; Havelund, Klaus; Lan, Sonie (Technical Monitor)

2001-01-01

This paper presents an approach to checking a running program against its Linear Temporal Logic (LTL) specifications. LTL is a widely used logic for expressing properties of programs viewed as sets of executions. Our approach consists of translating LTL formulae to finite-state automata, which are used as observers of the program behavior. The translation algorithm we propose modifies standard LTL to Buchi automata conversion techniques to generate automata that check finite program traces. The algorithm has been implemented in a tool, which has been integrated with the generic JPaX framework for runtime analysis of Java programs.

Self-organisation in Cellular Automata with Coalescent Particles: Qualitative and Quantitative Approaches

Science.gov (United States)

Hellouin de Menibus, Benjamin; Sablik, Mathieu

2017-06-01

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial shift-ergodic measure, and use the limit measure to describe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata [introduced by Fisch (J Theor Probab 3(2):311-338, 1990; Phys D 45(1-3):19-25, 1990)], one-sided captive cellular automata [introduced by Theyssier (Captive Cellular Automata, 2004)], the majority-traffic cellular automaton, a self stabilisation process towards a discrete line [introduced by Regnault and Rémila (in: Mathematical Foundations of Computer Science 2015—40th International Symposium, MFCS 2015, Milan, Italy, Proceedings, Part I, 2015)]. In a second time we restrict our study to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times [generalising K ůrka et al. (in: Proceedings of AUTOMATA, 2011)], the density of particles and the rate of convergence to the limit measure.

Dual decomposition for parsing with non-projective head automata

OpenAIRE

Koo, Terry; Rush, Alexander Matthew; Collins, Michael; Jaakkola, Tommi S.; Sontag, David Alexander

2010-01-01

This paper introduces algorithms for non-projective parsing based on dual decomposition. We focus on parsing algorithms for non-projective head automata, a generalization of head-automata models to non-projective structures. The dual decomposition algorithms are simple and efficient, relying on standard dynamic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing problem. Empirically the LP relaxation is very often tight: for man...

Simulating Complex Systems by Cellular Automata

CERN Document Server

Kroc, Jiri; Hoekstra, Alfons G

2010-01-01

Deeply rooted in fundamental research in Mathematics and Computer Science, Cellular Automata (CA) are recognized as an intuitive modeling paradigm for Complex Systems. Already very basic CA, with extremely simple micro dynamics such as the Game of Life, show an almost endless display of complex emergent behavior. Conversely, CA can also be designed to produce a desired emergent behavior, using either theoretical methodologies or evolutionary techniques. Meanwhile, beyond the original realm of applications - Physics, Computer Science, and Mathematics – CA have also become work horses in very different disciplines such as epidemiology, immunology, sociology, and finance. In this context of fast and impressive progress, spurred further by the enormous attraction these topics have on students, this book emerges as a welcome overview of the field for its practitioners, as well as a good starting point for detailed study on the graduate and post-graduate level. The book contains three parts, two major parts on th...

MODELING OF FUTURE LAND COVER LAND USE CHANGE IN NORTH CAROLINA USING MARKOV CHAIN AND CELLULAR AUTOMATA MODEL

OpenAIRE

Mohammad Sayemuzzaman; Manoj K. Jha

2014-01-01

State wide variant topographic features in North Carolina attract the hydro-climatologist. There is none modeling study found that predict future Land Cover Land Use (LCLU) change for whole North Carolina. In this study, satellite-derived land cover maps of year 1992, 2001 and 2006 of North Carolina were integrated within the framework of the Markov-Cellular Automata (Markov-CA) model which combines the Markov chain and Cellular Automata (CA) techniques. A Multi-Criteria Evaluation (MCE) was ...

Modelling and simulating in-stent restenosis with complex automata

NARCIS (Netherlands)

Hoekstra, A.G.; Lawford, P.; Hose, R.

2010-01-01

In-stent restenosis, the maladaptive response of a blood vessel to injury caused by the deployment of a stent, is a multiscale system involving a large number of biological and physical processes. We describe a Complex Automata Model for in-stent restenosis, coupling bulk flow, drug diffusion, and

Supervisory Control of (max,+) automata: a behavioral approach

Czech Academy of Sciences Publication Activity Database

Komenda, Jan; Lahaye, S.; Boimond, J.-L.

2009-01-01

Roč. 19, č. 4 (2009), s. 525-549 ISSN 0924-6703 Grant - others:EU Projekt(XE) EU.ICT.DISC 224498 Institutional research plan: CEZ:AV0Z10190503 Keywords : timed discrete-event systems * supervisory control * formal power series * (max,+) * automata Subject RIV: BA - General Mathematics Impact factor: 0.921, year: 2009

A new optimization method based on cellular automata for VVER-1000 nuclear reactor loading pattern

International Nuclear Information System (INIS)

Fadaei, Amir Hosein; Setayeshi, Saeed

2009-01-01

This paper presents a new and innovative optimization technique, which uses cellular automata for solving multi-objective optimization problems. Due to its ability in simulating the local information while taking neighboring effects into account, the cellular automata technique is a powerful tool for optimization. The fuel-loading pattern in nuclear reactor cores is a major optimization problem. Due to the immensity of the search space in fuel management optimization problems, finding the optimum solution requires a huge amount of calculations in the classical method. The cellular automata models, based on local information, can reduce the computations significantly. In this study, reducing the power peaking factor, while increasing the initial excess reactivity inside the reactor core of VVER-1000, which are two apparently contradictory objectives, are considered as the objective functions. The result is an optimum configuration, which is in agreement with the pattern proposed by the designer. In order to gain confidence in the reliability of this method, the aforementioned problem was also solved using neural network and simulated annealing, and the results and procedures were compared.

Modular tree automata

DEFF Research Database (Denmark)

Bahr, Patrick

2012-01-01

Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular...

Query Monitoring and Analysis for Database Privacy - A Security Automata Model Approach.

Science.gov (United States)

Kumar, Anand; Ligatti, Jay; Tu, Yi-Cheng

2015-11-01

Privacy and usage restriction issues are important when valuable data are exchanged or acquired by different organizations. Standard access control mechanisms either restrict or completely grant access to valuable data. On the other hand, data obfuscation limits the overall usability and may result in loss of total value. There are no standard policy enforcement mechanisms for data acquired through mutual and copyright agreements. In practice, many different types of policies can be enforced in protecting data privacy. Hence there is the need for an unified framework that encapsulates multiple suites of policies to protect the data. We present our vision of an architecture named security automata model (SAM) to enforce privacy-preserving policies and usage restrictions. SAM analyzes the input queries and their outputs to enforce various policies, liberating data owners from the burden of monitoring data access. SAM allows administrators to specify various policies and enforces them to monitor queries and control the data access. Our goal is to address the problems of data usage control and protection through privacy policies that can be defined, enforced, and integrated with the existing access control mechanisms using SAM. In this paper, we lay out the theoretical foundation of SAM, which is based on an automata named Mandatory Result Automata. We also discuss the major challenges of implementing SAM in a real-world database environment as well as ideas to meet such challenges.

Automata, Logic, and XML

OpenAIRE

NEVEN, Frank

2002-01-01

We survey some recent developments in the broad area of automata and logic which are motivated by the advent of XML. In particular, we consider unranked tree automata, tree-walking automata, and automata over infinite alphabets. We focus on their connection with logic and on questions imposed by XML.

Cellular automata model for traffic flow at intersections in internet of vehicles

Science.gov (United States)

Zhao, Han-Tao; Liu, Xin-Ru; Chen, Xiao-Xu; Lu, Jian-Cheng

2018-03-01

Considering the effect of the front vehicle's speed, the influence of the brake light and the conflict of the traffic flow, we established a cellular automata model called CE-NS for traffic flow at the intersection in the non-vehicle networking environment. According to the information interaction of Internet of Vehicles (IoV), introducing parameters describing the congestion and the accurate speed of the front vehicle into the CE-NS model, we improved the rules of acceleration, deceleration and conflict, and finally established a cellular automata model for traffic flow at intersections of IoV. The relationship between traffic parameters such as vehicle speed, flow and average travel time is obtained by numerical simulation of two models. Based on this, we compared the traffic situation of the non-vehicle networking environment with conditions of IoV environment, and analyzed the influence of the different degree of IoV on the traffic flow. The results show that the traffic speed is increased, the travel time is reduced, the flux of intersections is increased and the traffic flow is more smoothly under IoV environment. After the vehicle which achieves IoV reaches a certain proportion, the operation effect of the traffic flow begins to improve obviously.

Modelling land-use effects of future urbanization using cellular automata

DEFF Research Database (Denmark)

Fuglsang, Morten; Münier, B.; Hansen, H.S.

2013-01-01

project PASHMINA (Paradigm Shift modelling and innovative approaches), three storylines of future transportation paradigm shifts towards 2040 are created. These storylines are translated into spatial planning strategies and modelled using the cellular automata model LUCIA. For the modelling, an Eastern......The modelling of land use change is a way to analyse future scenarios by modelling different pathways. Application of spatial data of different scales coupled with socio-economic data makes it possible to explore and test the understanding of land use change relations. In the EU-FP7 research...... Danish case area was selected, comprising of the Copenhagen metropolitan area and its hinterland. The different scenarios are described using a range of different descriptive GIS datasets. These include mapping of accessibility based on public and private transportation, urban density and structure...

Algorithm for repairing the damaged images of grain structures obtained from the cellular automata and measurement of grain size

Science.gov (United States)

Ramírez-López, A.; Romero-Romo, M. A.; Muñoz-Negron, D.; López-Ramírez, S.; Escarela-Pérez, R.; Duran-Valencia, C.

2012-10-01

Computational models are developed to create grain structures using mathematical algorithms based on the chaos theory such as cellular automaton, geometrical models, fractals, and stochastic methods. Because of the chaotic nature of grain structures, some of the most popular routines are based on the Monte Carlo method, statistical distributions, and random walk methods, which can be easily programmed and included in nested loops. Nevertheless, grain structures are not well defined as the results of computational errors and numerical inconsistencies on mathematical methods. Due to the finite definition of numbers or the numerical restrictions during the simulation of solidification, damaged images appear on the screen. These images must be repaired to obtain a good measurement of grain geometrical properties. Some mathematical algorithms were developed to repair, measure, and characterize grain structures obtained from cellular automata in the present work. An appropriate measurement of grain size and the corrected identification of interfaces and length are very important topics in materials science because they are the representation and validation of mathematical models with real samples. As a result, the developed algorithms are tested and proved to be appropriate and efficient to eliminate the errors and characterize the grain structures.

A cellular automata intraurban model with prices and income-differentiated actors

NARCIS (Netherlands)

Furtado, B.A.; Ettema, D.F.; Ruiz, R.M.; Hurkens, J.; Delden, H. van

2012-01-01

This paper presents an intraurban cellular automata model that is an extension to White and Engelen’s pioneering model. The paper’s main contribution is to distinguish between agglomerative eff ects, determined by the attraction of the neighbourhood, and disagglomerative eff ects, driven by land

Cellular automata model for human articular chondrocytes migration, proliferation and cell death: An in vitro validation.

Science.gov (United States)

Vaca-González, J J; Gutiérrez, M L; Guevara, J M; Garzón-Alvarado, D A

2017-01-01

Articular cartilage is characterized by low cell density of only one cell type, chondrocytes, and has limited self-healing properties. When articular cartilage is affected by traumatic injuries, a therapeutic strategy such as autologous chondrocyte implantation is usually proposed for its treatment. This approach requires in vitro chondrocyte expansion to yield high cell number for cell transplantation. To improve the efficiency of this procedure, it is necessary to assess cell dynamics such as migration, proliferation and cell death during culture. Computational models such as cellular automata can be used to simulate cell dynamics in order to enhance the result of cell culture procedures. This methodology has been implemented for several cell types; however, an experimental validation is required for each one. For this reason, in this research a cellular automata model, based on random-walk theory, was devised in order to predict articular chondrocyte behavior in monolayer culture during cell expansion. Results demonstrated that the cellular automata model corresponded to cell dynamics and computed-accurate quantitative results. Moreover, it was possible to observe that cell dynamics depend on weighted probabilities derived from experimental data and cell behavior varies according to the cell culture period. Thus, depending on whether cells were just seeded or proliferated exponentially, culture time probabilities differed in percentages in the CA model. Furthermore, in the experimental assessment a decreased chondrocyte proliferation was observed along with increased passage number. This approach is expected to having other uses as in enhancing articular cartilage therapies based on tissue engineering and regenerative medicine.

Automation of Algorithmic Tasks for Virtual Laboratories Based on Automata Theory

Directory of Open Access Journals (Sweden)

Evgeniy A. Efimchik

2016-03-01

Full Text Available In the work a description of an automata model of standard algorithm for constructing a correct solution of algorithmic tests is given. The described model allows a formal determination of the variant complexity of algorithmic test and serves as a basis for determining the complexity functions, including the collision concept – the situation of uncertainty, when a choice must be made upon fulfilling the task between the alternatives with various priorities. The influence of collisions on the automata model and its inner structure is described. The model and complexity functions are applied for virtual laboratories upon designing the algorithms of constructing variant with a predetermined complexity in real time and algorithms of the estimation procedures of students’ solution with respect to collisions. The results of the work are applied to the development of virtual laboratories, which are used in the practical part of massive online course on graph theory.

Recursive definition of global cellular-automata mappings

International Nuclear Information System (INIS)

Feldberg, R.; Knudsen, C.; Rasmussen, S.

1994-01-01

A method for a recursive definition of global cellular-automata mappings is presented. The method is based on a graphical representation of global cellular-automata mappings. For a given cellular-automaton rule the recursive algorithm defines the change of the global cellular-automaton mapping as the number of lattice sites is incremented. A proof of lattice size invariance of global cellular-automata mappings is derived from an approximation to the exact recursive definition. The recursive definitions are applied to calculate the fractal dimension of the set of reachable states and of the set of fixed points of cellular automata on an infinite lattice

Bisimulations meet PCTL equivalences for probabilistic automata

DEFF Research Database (Denmark)

Song, Lei; Zhang, Lijun; Godskesen, Jens Chr.

2013-01-01

Probabilistic automata (PAs) have been successfully applied in formal verification of concurrent and stochastic systems. Efficient model checking algorithms have been studied, where the most often used logics for expressing properties are based on probabilistic computation tree logic (PCTL) and its...

Surface Dynamic Process Simulation with the Use of Cellular Automata

International Nuclear Information System (INIS)

Adamska-Szatko, M.; Bala, J.

2010-01-01

Cellular automata are known for many applications, especially for physical and biological simulations. Universal cellular automata can be used for modelling complex natural phenomena. The paper presents simulation of surface dynamic process. Simulation uses 2-dimensional cellular automata algorithm. Modelling and visualisation were created by in-house developed software with standard OpenGL graphic library. (authors)

Cellular-automata model of the dwarf shrubs populations and communities dynamics

Directory of Open Access Journals (Sweden)

A. S. Komarov

2015-06-01

Full Text Available The probabilistic cellular-automata model of development and long-time dynamics of dwarf shrub populations and communities is developed. It is based on the concept of discrete description of the plant ontogenesis and joint model approaches in terms of probabilistic cellular automata and L-systems by Lindenmayer. Short representation of the basic model allows evaluation of the approach and software implementation. The main variables of the model are a number of partial bushes in clones or area projective cover. The model allows us to investigate the conditions of self-maintenance and sustainability population under different environmental conditions (inaccessibility of the territory for settlement, mosaic moisture conditions of soil and wealth. The model provides a forecast of the total biomass dynamics shrubs and their fractions (stems, leaves, roots, fine roots, fruits on the basis of the data obtained in the discrete description of ontogenesis and further information on the productivity of the plant fractions. The inclusion of the joint dynamics of biomass of shrubs and soil in EFIMOD models cycle of carbon and nitrogen to evaluate the role of shrubs in these circulations, especially at high impact, such as forest fires and clear cutting, allow forecasting of the dynamics of populations and ecosystem functions of shrubs (regulation of biogeochemical cycles maintaining biodiversity, participation in the creation of non-wood products with changing climatic conditions and strong damaging effects (logging, fires; and application of the models developed to investigate the stability and productivity of shrubs and their participation in the cycle of carbon and nitrogen in different climatic and edaphic conditions.

Uniform and localized corrosion modelling by means of probabilistic cellular automata

International Nuclear Information System (INIS)

Perez-Brokate, Cristian

2016-01-01

Numerical modelling is complementary tool for corrosion prediction. The objective of this work is to develop a corrosion model by means of a probabilistic cellular automata approach at a mesoscopic scale. In this work, we study the morphological evolution and kinetics of corrosion. This model couples electrochemical oxidation and reduction reactions. Regarding kinetics, cellular automata models are able to describe current as a function of the applied potential for a redox reaction on an inert electrode. The inclusion of probabilities allows the description of the stochastic nature of anodic and cathodic reactions. Corrosion morphology has been studied in different context: generalised corrosion, pitting corrosion and corrosion in an occluded environment. a general tendency of two regimes is found. a first regime of uniform corrosion where the anodic and cathodic reactions occur homogeneously over the surface. a second regime of localized corrosion when there is a spatial separation of anodic and cathodic zones, with an increase of anodic reaction rate. (author) [fr

Parallel Genetic Algorithms for calibrating Cellular Automata models: Application to lava flows

International Nuclear Information System (INIS)

D'Ambrosio, D.; Spataro, W.; Di Gregorio, S.; Calabria Univ., Cosenza; Crisci, G.M.; Rongo, R.; Calabria Univ., Cosenza

2005-01-01

Cellular Automata are highly nonlinear dynamical systems which are suitable far simulating natural phenomena whose behaviour may be specified in terms of local interactions. The Cellular Automata model SCIARA, developed far the simulation of lava flows, demonstrated to be able to reproduce the behaviour of Etnean events. However, in order to apply the model far the prediction of future scenarios, a thorough calibrating phase is required. This work presents the application of Genetic Algorithms, general-purpose search algorithms inspired to natural selection and genetics, far the parameters optimisation of the model SCIARA. Difficulties due to the elevated computational time suggested the adoption a Master-Slave Parallel Genetic Algorithm far the calibration of the model with respect to the 2001 Mt. Etna eruption. Results demonstrated the usefulness of the approach, both in terms of computing time and quality of performed simulations

The adaptive cruise control vehicles in the cellular automata model

International Nuclear Information System (INIS)

Jiang Rui; Wu Qingsong

2006-01-01

This Letter presented a cellular automata model where the adaptive cruise control vehicles are modelled. In this model, the constant time headway policy is adopted. The fundamental diagram is presented. The simulation results are in good agreement with the analytical ones. The mixture of ACC vehicles with manually driven vehicles is investigated. It is shown that with the introduction of ACC vehicles, the jam can be suppressed

Bisimulations Meet PCTL Equivalences for Probabilistic Automata

DEFF Research Database (Denmark)

Song, Lei; Zhang, Lijun; Godskesen, Jens Chr.

2011-01-01

Probabilistic automata (PA) [20] have been successfully applied in the formal verification of concurrent and stochastic systems. Efficient model checking algorithms have been studied, where the most often used logics for expressing properties are based on PCTL [11] and its extension PCTL∗ [4...

On Elementary and Algebraic Cellular Automata

Science.gov (United States)

Gulak, Yuriy

In this paper we study elementary cellular automata from an algebraic viewpoint. The goal is to relate the emergent complex behavior observed in such systems with the properties of corresponding algebraic structures. We introduce algebraic cellular automata as a natural generalization of elementary ones and discuss their applications as generic models of complex systems.

Modelling Cow Behaviour Using Stochastic Automata

DEFF Research Database (Denmark)

Jónsson, Ragnar Ingi

This report covers an initial study on the modelling of cow behaviour using stochastic automata with the aim of detecting lameness. Lameness in cows is a serious problem that needs to be dealt with because it results in less profitable production units and in reduced quality of life...... for the affected livestock. By featuring training data consisting of measurements of cow activity, three different models are obtained, namely an autonomous stochastic automaton, a stochastic automaton with coinciding state and output and an autonomous stochastic automaton with coinciding state and output, all...... of which describe the cows' activity in the two regarded behavioural scenarios, non-lame and lame. Using the experimental measurement data the different behavioural relations for the two regarded behavioural scenarios are assessed. The three models comprise activity within last hour, activity within last...

Nested cellular automata

International Nuclear Information System (INIS)

Quasthoff, U.

1985-07-01

Cellular automata by definition consist of a finite or infinite number of cells, say of unit length, with each cell having the same transition function. These cells are usually considered as the smallest elements and so the space filled with these cells becomes discrete. Nevertheless, large pictures created by such cellular automata look very fractal. So we try to replace each cell by a couple of smaller cells, which have the same transition functions as the large ones. There are automata where this replacement does not destroy the macroscopic structure. In these cases this nesting process can be iterated. The paper contains large classes of automata with the above properties. In the case of one dimensional automata with two states and next neighbour interaction and a nesting function of the same type a complete classification is given. (author)

Evolution of probability measures by cellular automata on algebraic topological Markov chains

Directory of Open Access Journals (Sweden)

ALEJANDRO MAASS

2003-01-01

Full Text Available In this paper we review some recent results on the evolution of probability measures under cellular automata acting on a fullshift. In particular we discuss the crucial role of the attractiveness of maximal measures. We enlarge the context of the results of a previous study of topological Markov chains that are Abelian groups; the shift map is an automorphism of this group. This is carried out by studying the dynamics of Markov measures by a particular additive cellular automata. Many of these topics were within the focus of Francisco Varela's mathematical interests.

Priced Timed Automata:  Theory and Tools

DEFF Research Database (Denmark)

Larsen, Kim Guldstrand

2009-01-01

Priced timed automata are emerging as useful formalisms for modeling and analysing a broad range of resource allocation problems. In this extended abstract, we highlight recent (un)deci\\-dability results related to priced timed automata as well as point to a number of open problems....

Stochastic properties of disturbed Elementary Cellular Automata

International Nuclear Information System (INIS)

Posiewnik, M.

2005-01-01

Cellular automata are class of simple mathematical systems that generate diverse, often complicated behaviour. Evolution of such a system is given by set of local and deterministic rules. However, in spite of simplicity of 'interactions' it's global behaviour can't be, in general, simply predicted or even can not be predicted in time shorter that time of it's strict evolution. We get as, a systems well known 1-dimensional, Wolfram class automata, and connect it into the reservoir consists of some random source (noise). In our experiment we are interested in: a) numeric verification of ergodicity for such a coupled system. b) finding it's probability distribution and evolution. c) finding some analogous for 'real' quantities and behaviour. d) using the dynamical systems and Markov chains theory to describe the system, and to make any predictions of it's behaviour. (author)

The Quest for Minimal Quotients for Probabilistic Automata

DEFF Research Database (Denmark)

Eisentraut, Christian; Hermanns, Holger; Schuster, Johann

2013-01-01

One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence...... results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic...... automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms....

A new cellular automata model of traffic flow with negative exponential weighted look-ahead potential

Science.gov (United States)

Ma, Xiao; Zheng, Wei-Fan; Jiang, Bao-Shan; Zhang, Ji-Ye

2016-10-01

With the development of traffic systems, some issues such as traffic jams become more and more serious. Efficient traffic flow theory is needed to guide the overall controlling, organizing and management of traffic systems. On the basis of the cellular automata model and the traffic flow model with look-ahead potential, a new cellular automata traffic flow model with negative exponential weighted look-ahead potential is presented in this paper. By introducing the negative exponential weighting coefficient into the look-ahead potential and endowing the potential of vehicles closer to the driver with a greater coefficient, the modeling process is more suitable for the driver’s random decision-making process which is based on the traffic environment that the driver is facing. The fundamental diagrams for different weighting parameters are obtained by using numerical simulations which show that the negative exponential weighting coefficient has an obvious effect on high density traffic flux. The complex high density non-linear traffic behavior is also reproduced by numerical simulations. Project supported by the National Natural Science Foundation of China (Grant Nos. 11572264, 11172247, 11402214, and 61373009).

Modeling evolution and immune system by cellular automata

International Nuclear Information System (INIS)

Bezzi, M.

2001-01-01

In this review the behavior of two different biological systems is investigated using cellular automata. Starting from this spatially extended approach it is also tried, in some cases, to reduce the complexity of the system introducing mean-field approximation, and solving (or trying to solve) these simplified systems. It is discussed the biological meaning of the results, the comparison with experimental data (if available) and the different features between spatially extended and mean-field versions. The biological systems considered in this review are the following: Darwinian evolution in simple ecosystems and immune system response. In the first section the main features of molecular evolution are introduced, giving a short survey of genetics for physicists and discussing some models for prebiotic systems and simple ecosystems. It is also introduced a cellular automaton model for studying a set of evolving individuals in a general fitness landscape, considering also the effects of co-evolution. In particular the process of species formation (speciation) is described in sect. 5. The second part deals with immune system modeling. The biological features of immune response are discussed, as well as it is introduced the concept of shape space and of idiotypic network. More detailed reviews which deal with immune system models (mainly focused on idiotypic network models) can be found. Other themes here discussed: the applications of CA to immune system modeling, two complex cellular automata for humoral and cellular immune response. Finally, it is discussed the biological data and the general conclusions are drawn in the last section

Computer simulation of 2D grain growth using a cellular automata model based on the lowest energy principle

International Nuclear Information System (INIS)

He Yizhu; Ding Hanlin; Liu Liufa; Shin, Keesam

2006-01-01

The morphology, topology and kinetics of normal grain growth in two-dimension were studied by computer simulation using a cellular automata (Canada) model based on the lowest energy principle. The thermodynamic energy that follows Maxwell-Boltzmann statistics has been introduced into this model for the calculation of energy change. The transition that can reduce the system energy to the lowest level is chosen to occur when there is more than one possible transition direction. The simulation results show that the kinetics of normal grain growth follows the Burke equation with the growth exponent m = 2. The analysis of topology further indicates that normal grain growth can be simulated fairly well by the present CA model. The vanishing of grains with different number of sides is discussed in the simulation

Safety impacts of red light cameras at signalized intersections based on cellular automata models.

Science.gov (United States)

Chai, C; Wong, Y D; Lum, K M

2015-01-01

This study applies a simulation technique to evaluate the hypothesis that red light cameras (RLCs) exert important effects on accident risks. Conflict occurrences are generated by simulation and compared at intersections with and without RLCs to assess the impact of RLCs on several conflict types under various traffic conditions. Conflict occurrences are generated through simulating vehicular interactions based on an improved cellular automata (CA) model. The CA model is calibrated and validated against field observations at approaches with and without RLCs. Simulation experiments are conducted for RLC and non-RLC intersections with different geometric layouts and traffic demands to generate conflict occurrences that are analyzed to evaluate the hypothesis that RLCs exert important effects on road safety. The comparison of simulated conflict occurrences show favorable safety impacts of RLCs on crossing conflicts and unfavorable impacts for rear-end conflicts during red/amber phases. Corroborative results are found from broad analysis of accident occurrence. RLCs are found to have a mixed effect on accident risk at signalized intersections: crossing collisions are reduced, whereas rear-end collisions may increase. The specially developed CA model is found to be a feasible safety assessment tool.

From equilibrium spin models to probabilistic cellular automata

International Nuclear Information System (INIS)

Georges, A.; Le Doussal, P.

1989-01-01

The general equivalence between D-dimensional probabilistic cellular automata (PCA) and (D + 1)-dimensional equilibrium spin models satisfying a disorder condition is first described in a pedagogical way and then used to analyze the phase diagrams, the critical behavior, and the universality classes of some automato. Diagrammatic representations of time-dependent correlation functions PCA are introduced. Two important classes of PCA are singled out for which these correlation functions simplify: (1) Quasi-Hamiltonian automata, which have a current-carrying steady state, and for which some correlation functions are those of a D-dimensional static model PCA satisfying the detailed balance condition appear as a particular case of these rules for which the current vanishes. (2) Linear (and more generally affine) PCA for which the diagrammatics reduces to a random walk problem closely related to (D + 1)-dimensional directed SAWs: both problems display a critical behavior with mean-field exponents in any dimension. The correlation length and effective velocity of propagation of excitations can be calculated for affine PCA, as is shown on an explicit D = 1 example. The authors conclude with some remarks on nonlinear PCA, for which the diagrammatics is related to reaction-diffusion processes, and which belong in some cases to the universality class of Reggeon field theory

Automata Techniques for Epistemic Protocol Synthesis

Directory of Open Access Journals (Sweden)

Guillaume Aucher

2014-04-01

Full Text Available In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis.

Product interval automata

Indian Academy of Sciences (India)

M. Senthilkumar (Newgen Imaging) 1461 1996 Oct 15 13:05:22

automata are expressive enough to model the timed behaviour of asynchronous .... F,G ⊆ Q are, respectively, the finitary and infinitary acceptance state sets. ...... 19th Foundations of Software Technology and Theoretical Computer Science ...

A compositional Translation of Stochastic Automata into Timed Automata

NARCIS (Netherlands)

d' Argenio, P.R.

We present a translation from stochastic automata [17, 16] into timed automata with deadlines [37, 13]. The translation preserves traces when the stochastic characteristics, namely the probability measures, are abstracted from the original stochastic automaton. Moreover, we show that the translation

Lattice Automata for Control of Self-Reconfigurable Robots

DEFF Research Database (Denmark)

Støy, Kasper

2015-01-01

are extreme versatility and robustness. The organisation of self-reconfigurable robots in a lattice structure and the emphasis on local communication between modules mean that lattice automata are a useful basis for control of self-reconfigurable robots. However, there are significant differences which arise...... mainly from the physical nature of self-reconfigurable robots as opposed to the virtual nature of lattice automata. The problems resulting from these differences are mutual exclusion, handling motion constraints of modules, and unrealistic assumption about global, spatial orientation. Despite...... these problems the self-reconfigurable robot community has successfully applied lattice automata to simple control problems. However, for more complex problems hybrid solutions based on lattice automata and distributed algorithms are used. Hence, lattice automata have shown to have potential for the control...

Mitochondrial fusion through membrane automata.

Science.gov (United States)

Giannakis, Konstantinos; Andronikos, Theodore

2015-01-01

Studies have shown that malfunctions in mitochondrial processes can be blamed for diseases. However, the mechanism behind these operations is yet not sufficiently clear. In this work we present a novel approach to describe a biomolecular model for mitochondrial fusion using notions from the membrane computing. We use a case study defined in BioAmbient calculus and we show how to translate it in terms of a P automata variant. We combine brane calculi with (mem)brane automata to produce a new scheme capable of describing simple, realistic models. We propose the further use of similar methods and the test of other biomolecular models with the same behaviour.

Restarting Automata with Auxiliary Symbols and Small Lookahead

DEFF Research Database (Denmark)

Schluter, Natalie Elaine

2012-01-01

We present a study on lookahead hierarchies for restarting automata with auxiliary symbols and small lookahead. In particular, we show that there are just two different classes of languages recognised by RRWW automata, through the restriction of lookahead size. We also show that the respective...... (left-) monotone restarting automaton models characterise the context-free languages and that the respective right-left-monotone restarting automata characterise the linear languages both with just lookahead length 2....

Reaction-Diffusion Automata Phenomenology, Localisations, Computation

CERN Document Server

Adamatzky, Andrew

2013-01-01

Reaction-diffusion and excitable media are amongst most intriguing substrates. Despite apparent simplicity of the physical processes involved the media exhibit a wide range of amazing patterns: from target and spiral waves to travelling localisations and stationary breathing patterns. These media are at the heart of most natural processes, including morphogenesis of living beings, geological formations, nervous and muscular activity, and socio-economic developments.   This book explores a minimalist paradigm of studying reaction-diffusion and excitable media using locally-connected networks of finite-state machines: cellular automata and automata on proximity graphs. Cellular automata are marvellous objects per se because they show us how to generate and manage complexity using very simple rules of dynamical transitions. When combined with the reaction-diffusion paradigm the cellular automata become an essential user-friendly tool for modelling natural systems and designing future and emergent computing arch...

Modeling and Simulation of Polarization in Internet Group Opinions Based on Cellular Automata

Directory of Open Access Journals (Sweden)

Yaofeng Zhang

2015-01-01

Full Text Available Hot events on Internet always attract many people who usually form one or several opinion camps through discussion. For the problem of polarization in Internet group opinions, we propose a new model based on Cellular Automata by considering neighbors, opinion leaders, and external influences. Simulation results show the following: (1 It is easy to form the polarization for both continuous opinions and discrete opinions when we only consider neighbors influence, and continuous opinions are more effective in speeding the polarization of group. (2 Coevolution mechanism takes more time to make the system stable, and the global coupling mechanism leads the system to consensus. (3 Opinion leaders play an important role in the development of consensus in Internet group opinions. However, both taking the opinion leaders as zealots and taking some randomly selected individuals as zealots are not conductive to the consensus. (4 Double opinion leaders with consistent opinions will accelerate the formation of group consensus, but the opposite opinions will lead to group polarization. (5 Only small external influences can change the evolutionary direction of Internet group opinions.

Simple Urban Simulation Atop Complicated Models: Multi-Scale Equation-Free Computing of Sprawl Using Geographic Automata

Directory of Open Access Journals (Sweden)

Yu Zou

2013-07-01

Full Text Available Reconciling competing desires to build urban models that can be simple and complicated is something of a grand challenge for urban simulation. It also prompts difficulties in many urban policy situations, such as urban sprawl, where simple, actionable ideas may need to be considered in the context of the messily complex and complicated urban processes and phenomena that work within cities. In this paper, we present a novel architecture for achieving both simple and complicated realizations of urban sprawl in simulation. Fine-scale simulations of sprawl geography are run using geographic automata to represent the geographical drivers of sprawl in intricate detail and over fine resolutions of space and time. We use Equation-Free computing to deploy population as a coarse observable of sprawl, which can be leveraged to run automata-based models as short-burst experiments within a meta-simulation framework.

Reasoning about real-time systems with temporal interval logic constraints on multi-state automata

Science.gov (United States)

Gabrielian, Armen

1991-01-01

Models of real-time systems using a single paradigm often turn out to be inadequate, whether the paradigm is based on states, rules, event sequences, or logic. A model-based approach to reasoning about real-time systems is presented in which a temporal interval logic called TIL is employed to define constraints on a new type of high level automata. The combination, called hierarchical multi-state (HMS) machines, can be used to model formally a real-time system, a dynamic set of requirements, the environment, heuristic knowledge about planning-related problem solving, and the computational states of the reasoning mechanism. In this framework, mathematical techniques were developed for: (1) proving the correctness of a representation; (2) planning of concurrent tasks to achieve goals; and (3) scheduling of plans to satisfy complex temporal constraints. HMS machines allow reasoning about a real-time system from a model of how truth arises instead of merely depending of what is true in a system.

PAM: Particle automata model in simulation of Fusarium graminearum pathogen expansion.

Science.gov (United States)

Wcisło, Rafał; Miller, S Shea; Dzwinel, Witold

2016-01-21

The multi-scale nature and inherent complexity of biological systems are a great challenge for computer modeling and classical modeling paradigms. We present a novel particle automata modeling metaphor in the context of developing a 3D model of Fusarium graminearum infection in wheat. The system consisting of the host plant and Fusarium pathogen cells can be represented by an ensemble of discrete particles defined by a set of attributes. The cells-particles can interact with each other mimicking mechanical resistance of the cell walls and cell coalescence. The particles can move, while some of their attributes can be changed according to prescribed rules. The rules can represent cellular scales of a complex system, while the integrated particle automata model (PAM) simulates its overall multi-scale behavior. We show that due to the ability of mimicking mechanical interactions of Fusarium tip cells with the host tissue, the model is able to simulate realistic penetration properties of the colonization process reproducing both vertical and lateral Fusarium invasion scenarios. The comparison of simulation results with micrographs from laboratory experiments shows encouraging qualitative agreement between the two. Copyright © 2015 Elsevier Ltd. All rights reserved.

An improved multi-value cellular automata model for heterogeneous bicycle traffic flow

Energy Technology Data Exchange (ETDEWEB)

Jin, Sheng [College of Civil Engineering and Architecture, Zhejiang University, Hangzhou, 310058 China (China); Qu, Xiaobo [Griffith School of Engineering, Griffith University, Gold Coast, 4222 Australia (Australia); Xu, Cheng [Department of Transportation Management Engineering, Zhejiang Police College, Hangzhou, 310053 China (China); College of Transportation, Jilin University, Changchun, 130022 China (China); Ma, Dongfang, E-mail: mdf2004@zju.edu.cn [Ocean College, Zhejiang University, Hangzhou, 310058 China (China); Wang, Dianhai [College of Civil Engineering and Architecture, Zhejiang University, Hangzhou, 310058 China (China)

2015-10-16

This letter develops an improved multi-value cellular automata model for heterogeneous bicycle traffic flow taking the higher maximum speed of electric bicycles into consideration. The update rules of both regular and electric bicycles are improved, with maximum speeds of two and three cells per second respectively. Numerical simulation results for deterministic and stochastic cases are obtained. The fundamental diagrams and multiple states effects under different model parameters are analyzed and discussed. Field observations were made to calibrate the slowdown probabilities. The results imply that the improved extended Burgers cellular automata (IEBCA) model is more consistent with the field observations than previous models and greatly enhances the realism of the bicycle traffic model. - Highlights: • We proposed an improved multi-value CA model with higher maximum speed. • Update rules are introduced for heterogeneous bicycle traffic with maximum speed 2 and 3 cells/s. • Simulation results of the proposed model are consistent with field bicycle data. • Slowdown probabilities of both regular and electric bicycles are calibrated.

An improved multi-value cellular automata model for heterogeneous bicycle traffic flow

International Nuclear Information System (INIS)

Jin, Sheng; Qu, Xiaobo; Xu, Cheng; Ma, Dongfang; Wang, Dianhai

2015-01-01

This letter develops an improved multi-value cellular automata model for heterogeneous bicycle traffic flow taking the higher maximum speed of electric bicycles into consideration. The update rules of both regular and electric bicycles are improved, with maximum speeds of two and three cells per second respectively. Numerical simulation results for deterministic and stochastic cases are obtained. The fundamental diagrams and multiple states effects under different model parameters are analyzed and discussed. Field observations were made to calibrate the slowdown probabilities. The results imply that the improved extended Burgers cellular automata (IEBCA) model is more consistent with the field observations than previous models and greatly enhances the realism of the bicycle traffic model. - Highlights: • We proposed an improved multi-value CA model with higher maximum speed. • Update rules are introduced for heterogeneous bicycle traffic with maximum speed 2 and 3 cells/s. • Simulation results of the proposed model are consistent with field bicycle data. • Slowdown probabilities of both regular and electric bicycles are calibrated

Authorship attribution based on Life-Like Network Automata.

Science.gov (United States)

Machicao, Jeaneth; Corrêa, Edilson A; Miranda, Gisele H B; Amancio, Diego R; Bruno, Odemir M

2018-01-01

The authorship attribution is a problem of considerable practical and technical interest. Several methods have been designed to infer the authorship of disputed documents in multiple contexts. While traditional statistical methods based solely on word counts and related measurements have provided a simple, yet effective solution in particular cases; they are prone to manipulation. Recently, texts have been successfully modeled as networks, where words are represented by nodes linked according to textual similarity measurements. Such models are useful to identify informative topological patterns for the authorship recognition task. However, there is no consensus on which measurements should be used. Thus, we proposed a novel method to characterize text networks, by considering both topological and dynamical aspects of networks. Using concepts and methods from cellular automata theory, we devised a strategy to grasp informative spatio-temporal patterns from this model. Our experiments revealed an outperformance over structural analysis relying only on topological measurements, such as clustering coefficient, betweenness and shortest paths. The optimized results obtained here pave the way for a better characterization of textual networks.

Authorship attribution based on Life-Like Network Automata

Science.gov (United States)

Machicao, Jeaneth; Corrêa, Edilson A.; Miranda, Gisele H. B.; Amancio, Diego R.

2018-01-01

The authorship attribution is a problem of considerable practical and technical interest. Several methods have been designed to infer the authorship of disputed documents in multiple contexts. While traditional statistical methods based solely on word counts and related measurements have provided a simple, yet effective solution in particular cases; they are prone to manipulation. Recently, texts have been successfully modeled as networks, where words are represented by nodes linked according to textual similarity measurements. Such models are useful to identify informative topological patterns for the authorship recognition task. However, there is no consensus on which measurements should be used. Thus, we proposed a novel method to characterize text networks, by considering both topological and dynamical aspects of networks. Using concepts and methods from cellular automata theory, we devised a strategy to grasp informative spatio-temporal patterns from this model. Our experiments revealed an outperformance over structural analysis relying only on topological measurements, such as clustering coefficient, betweenness and shortest paths. The optimized results obtained here pave the way for a better characterization of textual networks. PMID:29566100

Authorship attribution based on Life-Like Network Automata.

Directory of Open Access Journals (Sweden)

Jeaneth Machicao

Full Text Available The authorship attribution is a problem of considerable practical and technical interest. Several methods have been designed to infer the authorship of disputed documents in multiple contexts. While traditional statistical methods based solely on word counts and related measurements have provided a simple, yet effective solution in particular cases; they are prone to manipulation. Recently, texts have been successfully modeled as networks, where words are represented by nodes linked according to textual similarity measurements. Such models are useful to identify informative topological patterns for the authorship recognition task. However, there is no consensus on which measurements should be used. Thus, we proposed a novel method to characterize text networks, by considering both topological and dynamical aspects of networks. Using concepts and methods from cellular automata theory, we devised a strategy to grasp informative spatio-temporal patterns from this model. Our experiments revealed an outperformance over structural analysis relying only on topological measurements, such as clustering coefficient, betweenness and shortest paths. The optimized results obtained here pave the way for a better characterization of textual networks.

Predictability in cellular automata.

Science.gov (United States)

Agapie, Alexandru; Andreica, Anca; Chira, Camelia; Giuclea, Marius

2014-01-01

Modelled as finite homogeneous Markov chains, probabilistic cellular automata with local transition probabilities in (0, 1) always posses a stationary distribution. This result alone is not very helpful when it comes to predicting the final configuration; one needs also a formula connecting the probabilities in the stationary distribution to some intrinsic feature of the lattice configuration. Previous results on the asynchronous cellular automata have showed that such feature really exists. It is the number of zero-one borders within the automaton's binary configuration. An exponential formula in the number of zero-one borders has been proved for the 1-D, 2-D and 3-D asynchronous automata with neighborhood three, five and seven, respectively. We perform computer experiments on a synchronous cellular automaton to check whether the empirical distribution obeys also that theoretical formula. The numerical results indicate a perfect fit for neighbourhood three and five, which opens the way for a rigorous proof of the formula in this new, synchronous case.

Algebraic Systems and Pushdown Automata

Science.gov (United States)

Petre, Ion; Salomaa, Arto

We concentrate in this chapter on the core aspects of algebraic series, pushdown automata, and their relation to formal languages. We choose to follow here a presentation of their theory based on the concept of properness. We introduce in Sect. 2 some auxiliary notions and results needed throughout the chapter, in particular the notions of discrete convergence in semirings and C-cycle free infinite matrices. In Sect. 3 we introduce the algebraic power series in terms of algebraic systems of equations. We focus on interconnections with context-free grammars and on normal forms. We then conclude the section with a presentation of the theorems of Shamir and Chomsky-Schützenberger. We discuss in Sect. 4 the algebraic and the regulated rational transductions, as well as some representation results related to them. Section 5 is dedicated to pushdown automata and focuses on the interconnections with classical (non-weighted) pushdown automata and on the interconnections with algebraic systems. We then conclude the chapter with a brief discussion of some of the other topics related to algebraic systems and pushdown automata.

Modeling the Land Use/Cover Change in an Arid Region Oasis City Constrained by Water Resource and Environmental Policy Change using Cellular Automata Model

Science.gov (United States)

Hu, X.; Li, X.; Lu, L.

2017-12-01

Land use/cover change (LUCC) is an important subject in the research of global environmental change and sustainable development, while spatial simulation on land use/cover change is one of the key content of LUCC and is also difficult due to the complexity of the system. The cellular automata (CA) model had an irreplaceable role in simulating of land use/cover change process due to the powerful spatial computing power. However, the majority of current CA land use/cover models were binary-state model that could not provide more general information about the overall spatial pattern of land use/cover change. Here, a multi-state logistic-regression-based Markov cellular automata (MLRMCA) model and a multi-state artificial-neural-network-based Markov cellular automata (MANNMCA) model were developed and were used to simulate complex land use/cover evolutionary process in an arid region oasis city constrained by water resource and environmental policy change, the Zhangye city during the period of 1990-2010. The results indicated that the MANNMCA model was superior to MLRMCA model in simulated accuracy. These indicated that by combining the artificial neural network with CA could more effectively capture the complex relationships between the land use/cover change and a set of spatial variables. Although the MLRMCA model were also some advantages, the MANNMCA model was more appropriate for simulating complex land use/cover dynamics. The two proposed models were effective and reliable, and could reflect the spatial evolution of regional land use/cover changes. These have also potential implications for the impact assessment of water resources, ecological restoration, and the sustainable urban development in arid areas.

On Modeling Large-Scale Multi-Agent Systems with Parallel, Sequential and Genuinely Asynchronous Cellular Automata

International Nuclear Information System (INIS)

Tosic, P.T.

2011-01-01

We study certain types of Cellular Automata (CA) viewed as an abstraction of large-scale Multi-Agent Systems (MAS). We argue that the classical CA model needs to be modified in several important respects, in order to become a relevant and sufficiently general model for the large-scale MAS, and so that thus generalized model can capture many important MAS properties at the level of agent ensembles and their long-term collective behavior patterns. We specifically focus on the issue of inter-agent communication in CA, and propose sequential cellular automata (SCA) as the first step, and genuinely Asynchronous Cellular Automata (ACA) as the ultimate deterministic CA-based abstract models for large-scale MAS made of simple reactive agents. We first formulate deterministic and nondeterministic versions of sequential CA, and then summarize some interesting configuration space properties (i.e., possible behaviors) of a restricted class of sequential CA. In particular, we compare and contrast those properties of sequential CA with the corresponding properties of the classical (that is, parallel and perfectly synchronous) CA with the same restricted class of update rules. We analytically demonstrate failure of the studied sequential CA models to simulate all possible behaviors of perfectly synchronous parallel CA, even for a very restricted class of non-linear totalistic node update rules. The lesson learned is that the interleaving semantics of concurrency, when applied to sequential CA, is not refined enough to adequately capture the perfect synchrony of parallel CA updates. Last but not least, we outline what would be an appropriate CA-like abstraction for large-scale distributed computing insofar as the inter-agent communication model is concerned, and in that context we propose genuinely asynchronous CA. (author)

Recursive definition of global cellular-automata mappings

DEFF Research Database (Denmark)

Feldberg, Rasmus; Knudsen, Carsten; Rasmussen, Steen

1994-01-01

A method for a recursive definition of global cellular-automata mappings is presented. The method is based on a graphical representation of global cellular-automata mappings. For a given cellular-automaton rule the recursive algorithm defines the change of the global cellular-automaton mapping...... as the number of lattice sites is incremented. A proof of lattice size invariance of global cellular-automata mappings is derived from an approximation to the exact recursive definition. The recursive definitions are applied to calculate the fractal dimension of the set of reachable states and of the set...

A mathematical model for camera calibration based on straight lines

Directory of Open Access Journals (Sweden)

Antonio M. G. Tommaselli

2005-12-01

Full Text Available In other to facilitate the automation of camera calibration process, a mathematical model using straight lines was developed, which is based on the equivalent planes mathematical model. Parameter estimation of the developed model is achieved by the Least Squares Method with Conditions and Observations. The same method of adjustment was used to implement camera calibration with bundles, which is based on points. Experiments using simulated and real data have shown that the developed model based on straight lines gives results comparable to the conventional method with points. Details concerning the mathematical development of the model and experiments with simulated and real data will be presented and the results with both methods of camera calibration, with straight lines and with points, will be compared.

A Cellular Automata-Based Simulation Tool for Real Fire Accident Prevention

Directory of Open Access Journals (Sweden)

Jacek M. Czerniak

2018-01-01

Full Text Available Many serious real-life problems could be simulated using cellular automata theory. There were a lot of fires in public places which kill many people. Proposed method, called Cellular Automata Evaluation (CAEva in short, is using cellular automata theory and could be used for checking buildings conditions for fire accident. The tests performed on real accident showed that an appropriately configured program allows obtaining a realistic simulation of human evacuation. The authors analyze some real accidents and proved that CAEva method appears as a very promising solution, especially in the cases of building renovations or temporary unavailability of escape routes.

Linear reversible second-order cellular automata and their first-order matrix equivalents

Science.gov (United States)

Macfarlane, A. J.

2004-11-01

Linear or one-dimensional reversible second-order cellular automata, exemplified by three cases named as RCA1-3, are introduced. Displays of their evolution in discrete time steps, &{\\in}Z_2;) as for RCA1-3. MCA1-3 are tractable because it has been possible to generalize to them the heavy duty methods already well-developed for ordinary first-order cellular automata like those of Wolfram's Rules 90 and 150. While the automata MCA1-3 are thought to be of genuine interest in their own right, with untapped further mathematical potential, their treatment has been applied here to expediting derivation of a large body of general and explicit results for N(t) for RCA1-3. Amongst explicit results obtained are formulas also for each of RCA1-3 for the total weight of the configurations of the first &2^M; times, M =0, 1, 2,\\ldots.

Mathematical Modeling of Column-Base Connections under Monotonic Loading

Directory of Open Access Journals (Sweden)

Gholamreza Abdollahzadeh

2014-12-01

Full Text Available Some considerable damage to steel structures during the Hyogo-ken Nanbu Earthquake occurred. Among them, many exposed-type column bases failed in several consistent patterns, such as brittle base plate fracture, excessive bolt elongation, unexpected early bolt failure, and inferior construction work, etc. The lessons from these phenomena led to the need for improved understanding of column base behavior. Joint behavior must be modeled when analyzing semi-rigid frames, which is associated with a mathematical model of the moment–rotation curve. The most accurate model uses continuous nonlinear functions. This article presents three areas of steel joint research: (1 analysis methods of semi-rigid joints; (2 prediction methods for the mechanical behavior of joints; (3 mathematical representations of the moment–rotation curve. In the current study, a new exponential model to depict the moment–rotation relationship of column base connection is proposed. The proposed nonlinear model represents an approach to the prediction of M–θ curves, taking into account the possible failure modes and the deformation characteristics of the connection elements. The new model has three physical parameters, along with two curve-fitted factors. These physical parameters are generated from dimensional details of the connection, as well as the material properties. The M–θ curves obtained by the model are compared with published connection tests and 3D FEM research. The proposed mathematical model adequately comes close to characterizing M–θ behavior through the full range of loading/rotations. As a result, modeling of column base connections using the proposed mathematical model can give crucial beforehand information, and overcome the disadvantages of time consuming workmanship and cost of experimental studies.

Stimulus-Response Theory of Finite Automata, Technical Report No. 133.

Science.gov (United States)

Suppes, Patrick

The central aim of this paper and its projected successors is to prove in detail that stimulus-response theory, or at least a mathematically precise version, can give an account of the learning of many phrase-structure grammars. Section 2 is concerned with standard notions of finite and probabilistic automata. An automaton is defined as a device…

Autonomously Implemented Versatile Path Planning for Mobile Robots Based on Cellular Automata and Ant Colony

Directory of Open Access Journals (Sweden)

Adel Akbarimajd

2012-02-01

Full Text Available A path planning method for mobile robots based on two dimensional cellular automata is proposed. The method can be applied for environments with both concave and convex obstacles. It is also appropriate for multi-robot problems as well as dynamic environments. In order to develop the planning method, environment of the robot is decomposed to a rectangular grid and the automata is defined with four states including Robot cell, Free cell, Goal cell and Obstacle cell. Evolution rules of automata are proposed in order to direct the robot toward its goal. CA based path planner method is afterwards modified by a colony technique to be applicable for concave obstacles. Then a layered architecture is proposed to autonomously implement the planning algorithm. The architecture employs an abstraction approach which makes the complexity manageable. An important feature of the architecture is internal artifacts that have some beliefs about the world. Most actions of the robot are planned and performed with respect to these artifacts.

Learn with SAT to Minimize Büchi Automata

Directory of Open Access Journals (Sweden)

Stephan Barth

2012-10-01

Full Text Available We describe a minimization procedure for nondeterministic Büchi automata (NBA. For an automaton A another automaton A_min with the minimal number of states is learned with the help of a SAT-solver. This is done by successively computing automata A' that approximate A in the sense that they accept a given finite set of positive examples and reject a given finite set of negative examples. In the course of the procedure these example sets are successively increased. Thus, our method can be seen as an instance of a generic learning algorithm based on a "minimally adequate teacher'' in the sense of Angluin. We use a SAT solver to find an NBA for given sets of positive and negative examples. We use complementation via construction of deterministic parity automata to check candidates computed in this manner for equivalence with A. Failure of equivalence yields new positive or negative examples. Our method proved successful on complete samplings of small automata and of quite some examples of bigger automata. We successfully ran the minimization on over ten thousand automata with mostly up to ten states, including the complements of all possible automata with two states and alphabet size three and discuss results and runtimes; single examples had over 100 states.

Lower and Upper Bounds in Zone-Based Abstractions of Timed Automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Bouyer, Patricia; Larsen, Kim Guldstrand

2005-01-01

The semantics of timed automata is defined using an infinite-state transition system. For verification purposes, one usually uses zone based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds...

Cellular Automata for Modeling the field-scale erosion

International Nuclear Information System (INIS)

Diaz Suarez, Jorge; Bagarotti Marin, Angel; Ruiz Perez, Maria Elena

2008-01-01

Full text: The Cellular Automaton (CA) is a system used discrete dynamic modeling of many physical systems. Their fundamental properties are the interaction at the local level, homogeneity and parallelism. It has been used as a secondary for the simulation of large systems where the use of equations in partial derivatives is complex and costly from the computational point of view. On the other hand, the high complexity of spatial interaction in the processes involved in the erosion-transport-deposition of sediments at field level, considerably limiting the use of base models physics. The objective of this study is to model the main processes involved in erosion water supply of soils through the use of the CAMELot system, based on an extension of the original paradigm of the CA. The CAMELot system has been used in the simulation of systems of large spatial extent, where the laws of local interaction between automata have a deep physical sense. This system guarantees both the input of the necessary specifications and simulation in parallel, as the visualization and the general management of the system. They are exposed to each of the submodels used in it and the overall dynamics of the system is analyzed. (author)

Types and Automata

DEFF Research Database (Denmark)

Schwartzbach, Michael Ignatieff; Meineche Smidt, Erik

A hierarchical type system for imperative programming languages gives rise to various computational problems, such as type equivalence, type ordering, etc. We present a particular class of finite automata which are shown to be isomorphic to type equations. All the relevant type concepts turn out...... to have well-known automata analogues, such as language equality, language inclusion, etc. This provides optimal or best known algorithms for the type system, by a process of translating type equations to automata, solving the analogous problem, and translating the result back to type equations. Apart...

REDUNDANT ELECTRIC MOTOR DRIVE CONTROL UNIT DESIGN USING AUTOMATA-BASED APPROACH

Directory of Open Access Journals (Sweden)

Yuri Yu. Yankin

2014-11-01

Full Text Available Implementation of redundant unit for motor drive control based on programmable logic devices is discussed. Continuous redundancy method is used. As compared to segregated standby redundancy and whole system standby redundancy, such method provides preservation of all unit functions in case of redundancy and gives the possibility for continuous monitoring of major and redundant elements. Example of that unit is given. Electric motor drive control channel block diagram contains two control units – the major and redundant; it also contains four power supply units. Control units programming was carried out using automata-based approach. Electric motor drive control channel model was developed; it provides complex simulation of control state-machine and power converter. Through visibility and hierarchy of finite state machines debug time was shortened as compared to traditional programming. Control state-machine description using hardware description language is required for its synthesis with FPGA-devices vendor design software. This description was generated automatically by MATLAB software package. To verify results two prototype control units, two prototype power supply units, and device mock-up were developed and manufactured. Units were installed in the device mock-up. Prototype units were created in accordance with requirements claimed to deliverable hardware. Control channel simulation and tests results in the perfect state and during imitation of major element fault are presented. Automata-based approach made it possible to observe and debug control state-machine transitions during simulation of transient processes, occurring at imitation of faults. Results of this work can be used in development of fault tolerant electric motor drive control channels.

Analysis for Embedded Systems: Experiments with Priced Timed Automata

DEFF Research Database (Denmark)

Ovatman, Tolga; Brekling, Aske Wiid; Hansen, Michael Reichhardt

2010-01-01

costs of those models. In order to achieve this, a basic model is built using priced timed automata and some resource consumption scenarios are verified. Even though the experiments are performed on small and basic models, we believe we have taken a basis step in showing that it is promising to use...... priced timed automata and Uppaal Cora as a model checking tool in reasoning about resource consumption of embedded systems....

Theory of automata, formal languages and computation

CERN Document Server

Xavier, SPE

2004-01-01

This book is aimed at providing an introduction to the basic models of computability to the undergraduate students. This book is devoted to Finite Automata and their properties. Pushdown Automata provides a class of models and enables the analysis of context-free languages. Turing Machines have been introduced and the book discusses computability and decidability. A number of problems with solutions have been provided for each chapter. A lot of exercises have been given with hints/answers to most of these tutorial problems.

Execution spaces for simple higher dimensional automata

DEFF Research Database (Denmark)

Raussen, Martin

2012-01-01

Higher dimensional automata (HDA) are highly expressive models for concurrency in Computer Science, cf van Glabbeek (Theor Comput Sci 368(1–2): 168–194, 2006). For a topologist, they are attractive since they can be modeled as cubical complexes—with an inbuilt restriction for directions of allowa......Higher dimensional automata (HDA) are highly expressive models for concurrency in Computer Science, cf van Glabbeek (Theor Comput Sci 368(1–2): 168–194, 2006). For a topologist, they are attractive since they can be modeled as cubical complexes—with an inbuilt restriction for directions...

A Markov Process Inspired Cellular Automata Model of Road Traffic

OpenAIRE

Wang, Fa; Li, Li; Hu, Jianming; Ji, Yan; Yao, Danya; Zhang, Yi; Jin, Xuexiang; Su, Yuelong; Wei, Zheng

2008-01-01

To provide a more accurate description of the driving behaviors in vehicle queues, a namely Markov-Gap cellular automata model is proposed in this paper. It views the variation of the gap between two consequent vehicles as a Markov process whose stationary distribution corresponds to the observed distribution of practical gaps. The multiformity of this Markov process provides the model enough flexibility to describe various driving behaviors. Two examples are given to show how to specialize i...

Advanced spatial metrics analysis in cellular automata land use and cover change modeling

International Nuclear Information System (INIS)

Zamyatin, Alexander; Cabral, Pedro

2011-01-01

This paper proposes an approach for a more effective definition of cellular automata transition rules for landscape change modeling using an advanced spatial metrics analysis. This approach considers a four-stage methodology based on: (i) the search for the appropriate spatial metrics with minimal correlations; (ii) the selection of the appropriate neighborhood size; (iii) the selection of the appropriate technique for spatial metrics application; and (iv) the analysis of the contribution level of each spatial metric for joint use. The case study uses an initial set of 7 spatial metrics of which 4 are selected for modeling. Results show a better model performance when compared to modeling without any spatial metrics or with the initial set of 7 metrics.

Iterons, fractals and computations of automata

Science.gov (United States)

Siwak, Paweł

1999-03-01

Processing of strings by some automata, when viewed on space-time (ST) diagrams, reveals characteristic soliton-like coherent periodic objects. They are inherently associated with iterations of automata mappings thus we call them the iterons. In the paper we present two classes of one-dimensional iterons: particles and filtrons. The particles are typical for parallel (cellular) processing, while filtrons, introduced in (32) are specific for serial processing of strings. In general, the images of iterated automata mappings exhibit not only coherent entities but also the fractals, and quasi-periodic and chaotic dynamics. We show typical images of such computations: fractals, multiplication by a number, and addition of binary numbers defined by a Turing machine. Then, the particles are presented as iterons generated by cellular automata in three computations: B/U code conversion (13, 29), majority classification (9), and in discrete version of the FPU (Fermi-Pasta-Ulam) dynamics (7, 23). We disclose particles by a technique of combinational recoding of ST diagrams (as opposed to sequential recoding). Subsequently, we recall the recursive filters based on FCA (filter cellular automata) window operators, and considered by Park (26), Ablowitz (1), Fokas (11), Fuchssteiner (12), Bruschi (5) and Jiang (20). We present the automata equivalents to these filters (33). Some of them belong to the class of filter automata introduced in (30). We also define and illustrate some properties of filtrons. Contrary to particles, the filtrons interact nonlocally in the sense that distant symbols may influence one another. Thus their interactions are very unusual. Some examples have been given in (32). Here we show new examples of filtron phenomena: multifiltron solitonic collisions, attracting and repelling filtrons, trapped bouncing filtrons (which behave like a resonance cavity) and quasi filtrons.

Cellular automata-based artificial life system of horizontal gene transfer

Directory of Open Access Journals (Sweden)

Ji-xin Liu

2016-02-01

Full Text Available Mutation and natural selection is the core of Darwin's idea about evolution. Many algorithms and models are based on this idea. However, in the evolution of prokaryotes, more and more researches have indicated that horizontal gene transfer (HGT would be much more important and universal than the authors had imagined. Owing to this mechanism, the prokaryotes not only become adaptable in nearly any environment on Earth, but also form a global genetic bank and a super communication network with all the genes of the prokaryotic world. Under this background, they present a novel cellular automata model general gene transfer to simulate and study the vertical gene transfer and HGT in the prokaryotes. At the same time, they use Schrodinger's life theory to formulate some evaluation indices and to discuss the intelligence and cognition of prokaryotes which is derived from HGT.

Non deterministic finite automata for power systems fault diagnostics

Directory of Open Access Journals (Sweden)

LINDEN, R.

2009-06-01

Full Text Available This paper introduces an application based on finite non-deterministic automata for power systems diagnosis. Automata for the simpler faults are presented and the proposed system is compared with an established expert system.

Multi-Robot Motion Planning: A Timed Automata Approach

DEFF Research Database (Denmark)

Quottrup, Michael Melholt; Bak, Thomas; Izadi-Zamanabadi, Roozbeh

2004-01-01

This paper describes how a network of interacting timed automata can be used to model, analyze, and verify motion planning problems in a scenario with multiple robotic vehicles. The method presupposes an infra-structure of robots with feed-back controllers obeying simple restriction on a planar...... grid. The automata formalism merely presents a high-level model of environment, robots and control, but allows composition and formal symbolic reasoning about coordinated solutions. Composition is achieved through synchronization, and the verification software UPPAAL is used for a symbolic verification...... then subsequently be used as a high-level motion plan for the robots. This paper reports on the timed automata framework, results of two verification experiments, promise of the approach, and gives a perspective for future research....

Multi-Robot Motion Planning: A Timed Automata Approach

DEFF Research Database (Denmark)

Quottrup, Michael Melholt; Bak, Thomas; Izadi-Zamanabadi, Roozbeh

This paper describes how a network of interacting timed automata can be used to model, analyze, and verify motion planning problems in a scenario with multiple robotic vehicles. The method presupposes an infra-structure of robots with feed-back controllers obeying simple restriction on a planar...... grid. The automata formalism merely presents a high-level model of environment, robots and control, but allows composition and formal symbolic reasoning about coordinated solutions. Composition is achieved through synchronization, and the verification software UPPAAL is used for a symbolic verification...... then subsequently be used as a high-level motion plan for the robots. This paper reports on the timed automata framework, results of two verification experiments, promise of the approach, and gives a perspective for future research....

Deterministic Automata for Unordered Trees

Directory of Open Access Journals (Sweden)

Adrien Boiret

2014-08-01

Full Text Available Automata for unordered unranked trees are relevant for defining schemas and queries for data trees in Json or Xml format. While the existing notions are well-investigated concerning expressiveness, they all lack a proper notion of determinism, which makes it difficult to distinguish subclasses of automata for which problems such as inclusion, equivalence, and minimization can be solved efficiently. In this paper, we propose and investigate different notions of "horizontal determinism", starting from automata for unranked trees in which the horizontal evaluation is performed by finite state automata. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers from coNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as CMso.

Boundary Induced Phase Transition in Cellular Automata Models of Pedestrian Flow

Czech Academy of Sciences Publication Activity Database

Bukáček, M.; Hrabák, Pavel

2016-01-01

Roč. 11, č. 4 (2016), s. 327-338 ISSN 1557-5969 R&D Projects: GA ČR GA13-13502S Institutional support: RVO:67985556 Keywords : Adaptive time-span * Cellular automata model * Floor-field * Pedestrian flow * Phase transition * Principle of bonds Subject RIV: BD - Theory of Information Impact factor: 0.696, year: 2016

Multi-Robot Motion Planning: A Timed Automata Approach

OpenAIRE

Quottrup, Michael Melholt; Bak, Thomas; Izadi-Zamanabadi, Roozbeh

2004-01-01

This paper describes how a network of interacting timed automata can be used to model, analyze, and verify motion planning problems in a scenario with multiple robotic vehicles. The method presupposes an infra-structure of robots with feed-back controllers obeying simple restriction on a planar grid. The automata formalism merely presents a high-level model of environment, robots and control, but allows composition and formal symbolic reasoning about coordinated solutions. Composition is achi...

Linearizable cellular automata

International Nuclear Information System (INIS)

Nobe, Atsushi; Yura, Fumitaka

2007-01-01

The initial value problem for a class of reversible elementary cellular automata with periodic boundaries is reduced to an initial-boundary value problem for a class of linear systems on a finite commutative ring Z 2 . Moreover, a family of such linearizable cellular automata is given

Virtual Stationary Automata for Mobile Networks

National Research Council Canada - National Science Library

Dolev, Shlomi; Gilbert, Seth; Lahiani, Limor; Lynch, Nancy; Nolte, Tina

2005-01-01

We define a programming abstraction for mobile networks called the Virtual Stationary Automata programming layer, consisting of real mobile clients, virtual timed I/O automata called virtual stationary automata (VSAs...

Confluence reduction for Markov automata

NARCIS (Netherlands)

Timmer, Mark; van de Pol, Jan Cornelis; Stoelinga, Mariëlle Ida Antoinette

Markov automata are a novel formalism for specifying systems exhibiting nondeterminism, probabilistic choices and Markovian rates. Recently, the process algebra MAPA was introduced to efficiently model such systems. As always, the state space explosion threatens the analysability of the models

Confluence Reduction for Markov Automata

NARCIS (Netherlands)

Timmer, Mark; van de Pol, Jan Cornelis; Stoelinga, Mariëlle Ida Antoinette; Braberman, Victor; Fribourg, Laurent

Markov automata are a novel formalism for specifying systems exhibiting nondeterminism, probabilistic choices and Markovian rates. Recently, the process algebra MAPA was introduced to efficiently model such systems. As always, the state space explosion threatens the analysability of the models

Simulation of a plane wavefront propagating in cardiac tissue using a cellular automata model

International Nuclear Information System (INIS)

Barbosa, Carlos R Hall

2003-01-01

We present a detailed description of a cellular automata model for the propagation of action potential in a planar cardiac tissue, which is very fast and easy to use. The model incorporates anisotropy in the electrical conductivity and a spatial variation of the refractory time. The transmembrane potential distribution is directly derived from the cell states, and the intracellular and extracellular potential distributions are calculated for the particular case of a plane wavefront. Once the potential distributions are known, the associated current densities are calculated by Ohm's law, and the magnetic field is determined at a plane parallel to the cardiac tissue by applying the law of Biot and Savart. The results obtained for propagation speed and for magnetic field amplitude with the cellular automata model are compared with values predicted by the bidomain formulation, for various angles between wavefront propagation and fibre direction, characterizing excellent agreement between the models

A mathematical framework for agent based models of complex biological networks.

Science.gov (United States)

Hinkelmann, Franziska; Murrugarra, David; Jarrah, Abdul Salam; Laubenbacher, Reinhard

2011-07-01

Agent-based modeling and simulation is a useful method to study biological phenomena in a wide range of fields, from molecular biology to ecology. Since there is currently no agreed-upon standard way to specify such models, it is not always easy to use published models. Also, since model descriptions are not usually given in mathematical terms, it is difficult to bring mathematical analysis tools to bear, so that models are typically studied through simulation. In order to address this issue, Grimm et al. proposed a protocol for model specification, the so-called ODD protocol, which provides a standard way to describe models. This paper proposes an addition to the ODD protocol which allows the description of an agent-based model as a dynamical system, which provides access to computational and theoretical tools for its analysis. The mathematical framework is that of algebraic models, that is, time-discrete dynamical systems with algebraic structure. It is shown by way of several examples how this mathematical specification can help with model analysis. This mathematical framework can also accommodate other model types such as Boolean networks and the more general logical models, as well as Petri nets.

Optimal scheduling using priced timed automata

DEFF Research Database (Denmark)

Behrmann, Gerd; Larsen, Kim Guldstrand; Rasmussen, Jacob Illum

2005-01-01

This contribution reports on the considerable effort made recently towards extending and applying well-established timed automata technology to optimal scheduling and planning problems. The effort of the authors in this direction has to a large extent been carried out as part of the European...... projects VHS [20] and AMETIST [16] and are available in the recently released UPPAAL CORA [12], a variant of the real-time verification tool UPPAAL [18, 5] specialized for cost-optimal reachability for the extended model of so-called priced timed automata....

Simulation of earthquakes with cellular automata

Directory of Open Access Journals (Sweden)

P. G. Akishin

1998-01-01

Full Text Available The relation between cellular automata (CA models of earthquakes and the Burridge–Knopoff (BK model is studied. It is shown that the CA proposed by P. Bak and C. Tang,although they have rather realistic power spectra, do not correspond to the BK model. We present a modification of the CA which establishes the correspondence with the BK model.An analytical method of studying the evolution of the BK-like CA is proposed. By this method a functional quadratic in stress release, which can be regarded as an analog of the event energy, is constructed. The distribution of seismic events with respect to this “energy” shows rather realistic behavior, even in two dimensions. Special attention is paid to two-dimensional automata; the physical restrictions on compression and shear stiffnesses are imposed.

Land use change modeling through scenario-based cellular automata Markov: improving spatial forecasting.

Science.gov (United States)

Jahanishakib, Fatemeh; Mirkarimi, Seyed Hamed; Salmanmahiny, Abdolrassoul; Poodat, Fatemeh

2018-05-08

Efficient land use management requires awareness of past changes, present actions, and plans for future developments. Part of these requirements is achieved using scenarios that describe a future situation and the course of changes. This research aims to link scenario results with spatially explicit and quantitative forecasting of land use development. To develop land use scenarios, SMIC PROB-EXPERT and MORPHOL methods were used. It revealed eight scenarios as the most probable. To apply the scenarios, we considered population growth rate and used a cellular automata-Markov chain (CA-MC) model to implement the quantified changes described by each scenario. For each scenario, a set of landscape metrics was used to assess the ecological integrity of land use classes in terms of fragmentation and structural connectivity. The approach enabled us to develop spatial scenarios of land use change and detect their differences for choosing the most integrated landscape pattern in terms of landscape metrics. Finally, the comparison between paired forecasted scenarios based on landscape metrics indicates that scenarios 1-1, 2-2, 3-2, and 4-1 have a more suitable integrity. The proposed methodology for developing spatial scenarios helps executive managers to create scenarios with many repetitions and customize spatial patterns in real world applications and policies.

Beyond Language Equivalence on Visibly Pushdown Automata

DEFF Research Database (Denmark)

Srba, Jiri

2009-01-01

We study (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds for a number of studied...... preorders and equivalences like simulation, completed simulation, ready simulation, 2-nested simulation preorders/equivalences and bisimulation equivalence. Our main results are that all the mentioned equivalences and preorders are EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly...... one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for visibly one-counter automata improves also the previously known DP-hardness results for ordinary one-counter automata and one-counter nets. Finally, we study regularity checking problems for visibly pushdown automata...

Maximizing the Adjacent Possible in Automata Chemistries.

Science.gov (United States)

Hickinbotham, Simon; Clark, Edward; Nellis, Adam; Stepney, Susan; Clarke, Tim; Young, Peter

2016-01-01

Automata chemistries are good vehicles for experimentation in open-ended evolution, but they are by necessity complex systems whose low-level properties require careful design. To aid the process of designing automata chemistries, we develop an abstract model that classifies the features of a chemistry from a physical (bottom up) perspective and from a biological (top down) perspective. There are two levels: things that can evolve, and things that cannot. We equate the evolving level with biology and the non-evolving level with physics. We design our initial organisms in the biology, so they can evolve. We design the physics to facilitate evolvable biologies. This architecture leads to a set of design principles that should be observed when creating an instantiation of the architecture. These principles are Everything Evolves, Everything's Soft, and Everything Dies. To evaluate these ideas, we present experiments in the recently developed Stringmol automata chemistry. We examine the properties of Stringmol with respect to the principles, and so demonstrate the usefulness of the principles in designing automata chemistries.

Simulating physics with cellular automata

Energy Technology Data Exchange (ETDEWEB)

Vichniac, G Y

1984-01-01

Cellular automata are dynamical systems where space, time, and variables are discrete. They are shown on two-dimensional examples to be capable of non-numerical simulations of physics. They are useful for faithful parallel processing of lattice models. At another level, they exhibit behaviours and illustrate concepts that are unmistakably physical, such as non-ergodicity and order parameters, frustration, relaxation to chaos through period doublings, a conspicuous arrow of time in reversible microscopic dynamics, causality and light-cone, and non-separability. In general, they constitute exactly computable models for complex phenomena and large-scale correlations that result from very simple short-range interactions. The author studies their space, time, and intrinsic symmetries and the corresponding conservation laws, with an emphasis on the conservation of information obeyed by reversible cellular automata. 60 references.

An energy and cost efficient majority-based RAM cell in quantum-dot cellular automata

Directory of Open Access Journals (Sweden)

Milad Bagherian Khosroshahy

Full Text Available Nanotechnologies, notably quantum-dot cellular automata, have achieved major attentions for their prominent features as compared to the conventional CMOS circuitry. Quantum-dot cellular automata, particularly owning to its considerable reduction in size, high switching speed and ultra-low energy consumption, is considered as a potential alternative for the CMOS technology. As the memory unit is one of the most essential components in a digital system, designing a well-optimized QCA random access memory (RAM cell is an important area of research. In this paper, a new five-input majority gate is presented which is suitable for implementing efficient single-layer QCA circuits. In addition, a new RAM cell with set and reset capabilities is designed based on the proposed majority gate, which has an efficient and low-energy structure. The functionality, performance and energy consumption of the proposed designs are evaluated based on the QCADesigner and QCAPro tools. According to the simulation results, the proposed RAM design leads to on average 38% lower total energy dissipation, 25% smaller area, 20% lower cell count, 28% lower delay and 60% lower QCA cost as compared to its previous counterparts. Keywords: Quantum-dot cellular automata (QCA, Majority gate, Random access memory (RAM, Energy efficiency

Last-position elimination-based learning automata.

Science.gov (United States)

Zhang, Junqi; Wang, Cheng; Zhou, MengChu

2014-12-01

An update scheme of the state probability vector of actions is critical for learning automata (LA). The most popular is the pursuit scheme that pursues the estimated optimal action and penalizes others. This paper proposes a reverse philosophy that leads to last-position elimination-based learning automata (LELA). The action graded last in terms of the estimated performance is penalized by decreasing its state probability and is eliminated when its state probability becomes zero. All active actions, that is, actions with nonzero state probability, equally share the penalized state probability from the last-position action at each iteration. The proposed LELA is characterized by the relaxed convergence condition for the optimal action, the accelerated step size of the state probability update scheme for the estimated optimal action, and the enriched sampling for the estimated nonoptimal actions. The proof of the ϵ-optimal property for the proposed algorithm is presented. Last-position elimination is a widespread philosophy in the real world and has proved to be also helpful for the update scheme of the learning automaton via the simulations of well-known benchmark environments. In the simulations, two versions of the LELA, using different selection strategies of the last action, are compared with the classical pursuit algorithms Discretized Pursuit Reward-Inaction (DP(RI)) and Discretized Generalized Pursuit Algorithm (DGPA). Simulation results show that the proposed schemes achieve significantly faster convergence and higher accuracy than the classical ones. Specifically, the proposed schemes reduce the interval to find the best parameter for a specific environment in the classical pursuit algorithms. Thus, they can have their parameter tuning easier to perform and can save much more time when applied to a practical case. Furthermore, the convergence curves and the corresponding variance coefficient curves of the contenders are illustrated to characterize their

Cellular automata models for diffusion of information and highway traffic flow

Science.gov (United States)

Fuks, Henryk

In the first part of this work we study a family of deterministic models for highway traffic flow which generalize cellular automaton rule 184. This family is parameterized by the speed limit m and another parameter k that represents degree of 'anticipatory driving'. We compare two driving strategies with identical maximum throughput: 'conservative' driving with high speed limit and 'anticipatory' driving with low speed limit. Those two strategies are evaluated in terms of accident probability. We also discuss fundamental diagrams of generalized traffic rules and examine limitations of maximum achievable throughput. Possible modifications of the model are considered. For rule 184, we present exact calculations of the order parameter in a transition from the moving phase to the jammed phase using the method of preimage counting, and use this result to construct a solution to the density classification problem. In the second part we propose a probabilistic cellular automaton model for the spread of innovations, rumors, news, etc., in a social system. We start from simple deterministic models, for which exact expressions for the density of adopters are derived. For a more realistic model, based on probabilistic cellular automata, we study the influence of a range of interaction R on the shape of the adoption curve. When the probability of adoption is proportional to the local density of adopters, and individuals can drop the innovation with some probability p, the system exhibits a second order phase transition. Critical line separating regions of parameter space in which asymptotic density of adopters is positive from the region where it is equal to zero converges toward the mean-field line when the range of the interaction increases. In a region between R=1 critical line and the mean-field line asymptotic density of adopters depends on R, becoming zero if R is too small (smaller than some critical value). This result demonstrates the importance of connectivity in

Solving multiconstraint assignment problems using learning automata.

Science.gov (United States)

Horn, Geir; Oommen, B John

2010-02-01

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. This feature, where we permit possibly contradictory constraints, distinguishes this paper from the state of the art. Indeed, we are aware of no learning automata (or other heuristic) solutions which solve this problem in its most general setting. 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

Research of the method of pseudo-random number generation based on asynchronous cellular automata with several active cells

Directory of Open Access Journals (Sweden)

Bilan Stepan

2017-01-01

Full Text Available To date, there are many tasks that are aimed at studying the dynamic changes in physical processes. These tasks do not give advance known result. The solution of such problems is based on the construction of a dynamic model of the object. Successful structural and functional implementation of the object model can give a positive result in time. This approach uses the task of constructing artificial biological objects. To solve such problems, pseudo-random number generators are used, which also find wide application for information protection tasks. Such generators should have good statistical properties and give a long repetition period of the generated pseudo-random bit sequence. This work is aimed at improving these characteristics. The paper considers the method of forming pseudo-random sequences of numbers on the basis of aperiodic cellular automata with two active cells. A pseudo-random number generator is proposed that generates three bit sequences. The first two bit sequences are formed by the corresponding two active cells in the cellular automaton. The third bit sequence is the result of executing the XOR function over the bits of the first two sequences and it has better characteristics compared to them. The use of cellular automata with two active cells allowed to improve the statistical properties of the formed bit sequence, as well as its repetition period. This is proved by using graphical tests for generators built based on cellular automata using the neighborhoods of von Neumann and Moore. The tests showed high efficiency of the generator based on an asynchronous cellular automaton with the neighborhood of Moore. The proposed pseudo-random number generators have good statistical properties, which makes it possible to use them in information security systems, as well as for simulation tasks of various dynamic processes.

Facilitating arrhythmia simulation: the method of quantitative cellular automata modeling and parallel running

Directory of Open Access Journals (Sweden)

Mondry Adrian

2004-08-01

Full Text Available Abstract Background Many arrhythmias are triggered by abnormal electrical activity at the ionic channel and cell level, and then evolve spatio-temporally within the heart. To understand arrhythmias better and to diagnose them more precisely by their ECG waveforms, a whole-heart model is required to explore the association between the massively parallel activities at the channel/cell level and the integrative electrophysiological phenomena at organ level. Methods We have developed a method to build large-scale electrophysiological models by using extended cellular automata, and to run such models on a cluster of shared memory machines. We describe here the method, including the extension of a language-based cellular automaton to implement quantitative computing, the building of a whole-heart model with Visible Human Project data, the parallelization of the model on a cluster of shared memory computers with OpenMP and MPI hybrid programming, and a simulation algorithm that links cellular activity with the ECG. Results We demonstrate that electrical activities at channel, cell, and organ levels can be traced and captured conveniently in our extended cellular automaton system. Examples of some ECG waveforms simulated with a 2-D slice are given to support the ECG simulation algorithm. A performance evaluation of the 3-D model on a four-node cluster is also given. Conclusions Quantitative multicellular modeling with extended cellular automata is a highly efficient and widely applicable method to weave experimental data at different levels into computational models. This process can be used to investigate complex and collective biological activities that can be described neither by their governing differentiation equations nor by discrete parallel computation. Transparent cluster computing is a convenient and effective method to make time-consuming simulation feasible. Arrhythmias, as a typical case, can be effectively simulated with the methods

Continuity controlled Hybrid Automata

NARCIS (Netherlands)

Bergstra, J.A.; Middelburg, C.A.

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation

Continuity Controlled Hybrid Automata

NARCIS (Netherlands)

Bergstra, J.A.; Middelburg, C.A.

2004-01-01

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of

Experiments with automata compression

NARCIS (Netherlands)

Daciuk, J.; Yu, S; Daley, M; Eramian, M G

2001-01-01

Several compression methods of finite-state automata are presented and evaluated. Most compression methods used here are already described in the literature. However, their impact on the size of automata has not been described yet. We fill that gap, presenting results of experiments carried out on

Continuity controlled hybrid automata

NARCIS (Netherlands)

Bergstra, J.A.; Middelburg, C.A.

2004-01-01

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of

Continuity controlled hybrid automata

NARCIS (Netherlands)

Bergstra, J.A.; Middelburg, C.A.

2006-01-01

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of

Timed Safety Automata and Logic Conformance

National Research Council Canada - National Science Library

Young, Frank

1999-01-01

Timed Logic Conformance (TLC) is used to verify the behavioral and timing properties of detailed digital circuits against abstract circuit specifications when both are modeled as Timed Safety Automata (TSA...

The Study Of Properties Of The Word Of Mouth Marketing Using Cellular Automata

Directory of Open Access Journals (Sweden)

Kowalska-Styczeń Agnieszka

2014-02-01

Full Text Available This article presents the possibility of using cellular automata, to study the properties of word of mouth (w-o-m marketing. Cellular automata allow to analyze the dynamics of changes in views and attitudes in social groups based on local interactions between people in small groups of friends, family members etc. The proposed paper shows the possibility of modelling the dynamics of word of mouth mechanism, if the basic assumptions of this process are: different size groups where this phenomenon occurs, and varied access to information. On the competing firms market, the dependence of the w-o-m mechanism dynamics on the model parameters is shown

Simulation of Two-Way Pushdown Automata Revisited

Directory of Open Access Journals (Sweden)

Robert Glück

2013-09-01

Full Text Available The linear-time simulation of 2-way deterministic pushdown automata (2DPDA by the Cook and Jones constructions is revisited. Following the semantics-based approach by Jones, an interpreter is given which, when extended with random-access memory, performs a linear-time simulation of 2DPDA. The recursive interpreter works without the dump list of the original constructions, which makes Cook's insight into linear-time simulation of exponential-time automata more intuitive and the complexity argument clearer. The simulation is then extended to 2-way nondeterministic pushdown automata (2NPDA to provide for a cubic-time recognition of context-free languages. The time required to run the final construction depends on the degree of nondeterminism. The key mechanism that enables the polynomial-time simulations is the sharing of computations by memoization.

Probabilistic cellular automata: Some statistical mechanical considerations

International Nuclear Information System (INIS)

Lebowitz, J.L.; Maes, C.; Speer, E.R.

1990-01-01

Spin systems evolving in continuous or discrete time under the action of stochastic dynamics are used to model phenomena as diverse as the structure of alloys and the functioning of neural networks. While in some cases the dynamics are secondary, designed to produce a specific stationary measure whose properties one is interested in studying, there are other cases in which the only available information is the dynamical rule. Prime examples of the former are computer simulations, via Glauber dynamics, of equilibrium Gibbs measures with a specified interaction potential. Examples of the latter include various types of majority rule dynamics used as models for pattern recognition and for error-tolerant computations. The present note discusses ways in which techniques found useful in equilibrium statistical mechanics can be applied to a particular class of models of the latter types. These are cellular automata with noise: systems in which the spins are updated stochastically at integer times, simultaneously at all sites of some regular lattice. These models were first investigated in detail in the Soviet literature of the late sixties and early seventies. They are now generally referred to as Stochastic or Probabilistic Cellular Automata (PCA), and may be considered to include deterministic automata (CA) as special limits. 16 refs., 3 figs

Elements of automata theory and the theory of Markov chains. [Self-organizing control systems

Energy Technology Data Exchange (ETDEWEB)

Lind, M

1975-03-01

Selected topics from automata theory and the theory of Markov chains are treated. In particular, finite-memory automata are discussed in detail, and the results are used to formulate an automation model of a class of continuous systems. Stochastic automata are introduced as a natural generalization of the deterministic automaton. Markov chains are shown to be closely related to stochastic automata. Results from Markov chain theory are thereby directly applicable to analysis of stochastic automata. This report provides the theoretical foundation for the investigation in Riso Report No. 315 of a class of self-organizing control systems. (25 figures) (auth)

Generating inferences from knowledge structures based on general automata

Energy Technology Data Exchange (ETDEWEB)

Koenig, E C

1983-01-01

The author shows that the model for knowledge structures for computers based on general automata accommodates procedures for establishing inferences. Algorithms are presented which generate inferences as output of a computer when its sentence input names appropriate knowledge elements contained in an associated knowledge structure already stored in the memory of the computer. The inferences are found to have either a single graph tuple or more than one graph tuple of associated knowledge. Six algorithms pertain to a single graph tuple and a seventh pertains to more than one graph tuple of associated knowledge. A named term is either the automaton, environment, auxiliary receptor, principal receptor, auxiliary effector, or principal effector. The algorithm pertaining to more than one graph tuple requires that the input sentence names the automaton, transformation response, and environment of one of the tuples of associated knowledge in a sequence of tuples. Interaction with the computer may be either in a conversation or examination mode. The algorithms are illustrated by an example. 13 references.

On Probabilistic Automata in Continuous Time

DEFF Research Database (Denmark)

Eisentraut, Christian; Hermanns, Holger; Zhang, Lijun

2010-01-01

We develop a compositional behavioural model that integrates a variation of probabilistic automata into a conservative extension of interactive Markov chains. The model is rich enough to embody the semantics of generalised stochastic Petri nets. We define strong and weak bisimulations and discuss...

Automata theory and its applications

CERN Document Server

Khoussainov, Bakhadyr

2001-01-01

The theory of finite automata on finite stings, infinite strings, and trees has had a dis­ tinguished history. First, automata were introduced to represent idealized switching circuits augmented by unit delays. This was the period of Shannon, McCullouch and Pitts, and Howard Aiken, ending about 1950. Then in the 1950s there was the work of Kleene on representable events, of Myhill and Nerode on finite coset congruence relations on strings, of Rabin and Scott on power set automata. In the 1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of two successors. The latter was a mystery until the introduction of forgetful determinacy games by Gurevich and Harrington in 1982. Each of these developments has successful and prospective applications in computer science. They should all be part of every computer scientist's toolbox. Suppose that we take a computer scientist's ...

Picture languages formal models for picture recognition

CERN Document Server

Rosenfeld, Azriel

1979-01-01

Computer Science and Applied Mathematics: Picture Languages: Formal Models for Picture Recognition treats pictorial pattern recognition from the formal standpoint of automata theory. This book emphasizes the capabilities and relative efficiencies of two types of automata-array automata and cellular array automata, with respect to various array recognition tasks. The array automata are simple processors that perform sequences of operations on arrays, while the cellular array automata are arrays of processors that operate on pictures in a highly parallel fashion, one processor per picture element. This compilation also reviews a collection of results on two-dimensional sequential and parallel array acceptors. Some of the analogous one-dimensional results and array grammars and their relation to acceptors are likewise covered in this text. This publication is suitable for researchers, professionals, and specialists interested in pattern recognition and automata theory.

Mathematics Instructional Model Based on Realistic Mathematics Education to Promote Problem Solving Ability at Junior High School Padang

OpenAIRE

Edwin Musdi

2016-01-01

This research aims to develop a mathematics instructional model based realistic mathematics education (RME) to promote students' problem-solving abilities. The design research used Plomp models, which consists of preliminary phase, development or proto-typing phase and assessment phase.  At this study, only the first two phases conducted. The first phase, a preliminary investigation, carried out with a literature study to examine the theory-based instructional learning RME model, characterist...

Simulations of living cell origins using a cellular automata model.

Science.gov (United States)

Ishida, Takeshi

2014-04-01

Understanding the generalized mechanisms of cell self-assembly is fundamental for applications in various fields, such as mass producing molecular machines in nanotechnology. Thus, the details of real cellular reaction networks and the necessary conditions for self-organized cells must be elucidated. We constructed a 2-dimensional cellular automata model to investigate the emergence of biological cell formation, which incorporated a looped membrane and a membrane-bound information system (akin to a genetic code and gene expression system). In particular, with an artificial reaction system coupled with a thermal system, the simultaneous formation of a looped membrane and an inner reaction process resulted in a more stable structure. These double structures inspired the primitive biological cell formation process from chemical evolution stage. With a model to simulate cellular self-organization in a 2-dimensional cellular automata model, 3 phenomena could be realized: (1) an inner reaction system developed as an information carrier precursor (akin to DNA); (2) a cell border emerged (akin to a cell membrane); and (3) these cell structures could divide into 2. This double-structured cell was considered to be a primary biological cell. The outer loop evolved toward a lipid bilayer membrane, and inner polymeric particles evolved toward precursor information carriers (evolved toward DNA). This model did not completely clarify all the necessary and sufficient conditions for biological cell self-organization. Further, our virtual cells remained unstable and fragile. However, the "garbage bag model" of Dyson proposed that the first living cells were deficient; thus, it would be reasonable that the earliest cells were more unstable and fragile than the simplest current unicellular organisms.

An authenticated image encryption scheme based on chaotic maps and memory cellular automata

Science.gov (United States)

Bakhshandeh, Atieh; Eslami, Ziba

2013-06-01

This paper introduces a new image encryption scheme based on chaotic maps, cellular automata and permutation-diffusion architecture. In the permutation phase, a piecewise linear chaotic map is utilized to confuse the plain-image and in the diffusion phase, we employ the Logistic map as well as a reversible memory cellular automata to obtain an efficient and secure cryptosystem. The proposed method admits advantages such as highly secure diffusion mechanism, computational efficiency and ease of implementation. A novel property of the proposed scheme is its authentication ability which can detect whether the image is tampered during the transmission or not. This is particularly important in applications where image data or part of it contains highly sensitive information. Results of various analyses manifest high security of this new method and its capability for practical image encryption.

A cellular automata model for traffic flow based on kinetics theory, vehicles capabilities and driver reactions

Science.gov (United States)

Guzmán, H. A.; Lárraga, M. E.; Alvarez-Icaza, L.; Carvajal, J.

2018-02-01

In this paper, a reliable cellular automata model oriented to faithfully reproduce deceleration and acceleration according to realistic reactions of drivers, when vehicles with different deceleration capabilities are considered is presented. The model focuses on describing complex traffic phenomena by coding in its rules the basic mechanisms of drivers behavior, vehicles capabilities and kinetics, while preserving simplicity. In particular, vehiclés kinetics is based on uniform accelerated motion, rather than in impulsive accelerated motion as in most existing CA models. Thus, the proposed model calculates in an analytic way three safe preserving distances to determine the best action a follower vehicle can take under a worst case scenario. Besides, the prediction analysis guarantees that under the proper assumptions, collision between vehicles may not happen at any future time. Simulations results indicate that all interactions of heterogeneous vehicles (i.e., car-truck, truck-car, car-car and truck-truck) are properly reproduced by the model. In addition, the model overcomes one of the major limitations of CA models for traffic modeling: the inability to perform smooth approach to slower or stopped vehicles. Moreover, the model is also capable of reproducing most empirical findings including the backward speed of the downstream front of the traffic jam, and different congested traffic patterns induced by a system with open boundary conditions with an on-ramp. Like most CA models, integer values are used to make the model run faster, which makes the proposed model suitable for real time traffic simulation of large networks.

Two Project-Based Strategies in an Interdisciplinary Mathematical Modeling in Biology Course

Science.gov (United States)

Ludwig, Patrice; Tongen, Anthony; Walton, Brian

2018-01-01

James Madison University faculty team-teach an interdisciplinary mathematical modeling course for mathematics and biology students. We have used two different project-based approaches to emphasize the mathematical concepts taught in class, while also exposing students to new areas of mathematics not formally covered in class. The first method…

A full computation-relevant topological dynamics classification of elementary cellular automata.

Science.gov (United States)

Schüle, Martin; Stoop, Ruedi

2012-12-01

Cellular automata are both computational and dynamical systems. We give a complete classification of the dynamic behaviour of elementary cellular automata (ECA) in terms of fundamental dynamic system notions such as sensitivity and chaoticity. The "complex" ECA emerge to be sensitive, but not chaotic and not eventually weakly periodic. Based on this classification, we conjecture that elementary cellular automata capable of carrying out complex computations, such as needed for Turing-universality, are at the "edge of chaos."

Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information.

Science.gov (United States)

Liu, Desheng; Huang, Zhiping; Zhang, Yimeng; Guo, Xiaojun; Su, Shaojing

2016-01-01

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n2). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft's algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.

Fuzzy tree automata and syntactic pattern recognition.

Science.gov (United States)

Lee, E T

1982-04-01

An approach of representing patterns by trees and processing these trees by fuzzy tree automata is described. Fuzzy tree automata are defined and investigated. The results include that the class of fuzzy root-to-frontier recognizable ¿-trees is closed under intersection, union, and complementation. Thus, the class of fuzzy root-to-frontier recognizable ¿-trees forms a Boolean algebra. Fuzzy tree automata are applied to processing fuzzy tree representation of patterns based on syntactic pattern recognition. The grade of acceptance is defined and investigated. Quantitative measures of ``approximate isosceles triangle,'' ``approximate elongated isosceles triangle,'' ``approximate rectangle,'' and ``approximate cross'' are defined and used in the illustrative examples of this approach. By using these quantitative measures, a house, a house with high roof, and a church are also presented as illustrative examples. In addition, three fuzzy tree automata are constructed which have the capability of processing the fuzzy tree representations of ``fuzzy houses,'' ``houses with high roofs,'' and ``fuzzy churches,'' respectively. The results may have useful applications in pattern recognition, image processing, artificial intelligence, pattern database design and processing, image science, and pictorial information systems.

An Asynchronous Cellular Automata-Based Adaptive Illumination Facility

Science.gov (United States)

Bandini, Stefania; Bonomi, Andrea; Vizzari, Giuseppe; Acconci, Vito

The term Ambient Intelligence refers to electronic environments that are sensitive and responsive to the presence of people; in the described scenario the environment itself is endowed with a set of sensors (to perceive humans or other physical entities such as dogs, bicycles, etc.), interacting with a set of actuators (lights) that choose their actions (i.e. state of illumination) in an attempt improve the overall experience of these users. The model for the interaction and action of sensors and actuators is an asynchronous Cellular Automata (CA) with memory, supporting a self-organization of the system as a response to the presence and movements of people inside it. The paper will introduce the model, as well as an ad hoc user interface for the specification of the relevant parameters of the CA transition rule that determines the overall system behaviour.

Analysis of creative mathematic thinking ability in problem based learning model based on self-regulation learning

Science.gov (United States)

Munahefi, D. N.; Waluya, S. B.; Rochmad

2018-03-01

The purpose of this research identified the effectiveness of Problem Based Learning (PBL) models based on Self Regulation Leaning (SRL) on the ability of mathematical creative thinking and analyzed the ability of mathematical creative thinking of high school students in solving mathematical problems. The population of this study was students of grade X SMA N 3 Klaten. The research method used in this research was sequential explanatory. Quantitative stages with simple random sampling technique, where two classes were selected randomly as experimental class was taught with the PBL model based on SRL and control class was taught with expository model. The selection of samples at the qualitative stage was non-probability sampling technique in which each selected 3 students were high, medium, and low academic levels. PBL model with SRL approach effectived to students’ mathematical creative thinking ability. The ability of mathematical creative thinking of low academic level students with PBL model approach of SRL were achieving the aspect of fluency and flexibility. Students of academic level were achieving fluency and flexibility aspects well. But the originality of students at the academic level was not yet well structured. Students of high academic level could reach the aspect of originality.

A cellular automata approach to chemical reactions : 1 reaction controlled systems

NARCIS (Netherlands)

Korte, de A.C.J.; Brouwers, H.J.H.

2013-01-01

A direct link between the chemical reaction controlled (shrinking core) model and cellular automata, to study the dissolution of particles, is derived in this paper. Previous research on first and second order reactions is based on the concentration of the reactant. The present paper describes the

Mathematical modeling of acid-base physiology.

Science.gov (United States)

Occhipinti, Rossana; Boron, Walter F

2015-01-01

pH is one of the most important parameters in life, influencing virtually every biological process at the cellular, tissue, and whole-body level. Thus, for cells, it is critical to regulate intracellular pH (pHi) and, for multicellular organisms, to regulate extracellular pH (pHo). pHi regulation depends on the opposing actions of plasma-membrane transporters that tend to increase pHi, and others that tend to decrease pHi. In addition, passive fluxes of uncharged species (e.g., CO2, NH3) and charged species (e.g., HCO3(-), [Formula: see text] ) perturb pHi. These movements not only influence one another, but also perturb the equilibria of a multitude of intracellular and extracellular buffers. Thus, even at the level of a single cell, perturbations in acid-base reactions, diffusion, and transport are so complex that it is impossible to understand them without a quantitative model. Here we summarize some mathematical models developed to shed light onto the complex interconnected events triggered by acids-base movements. We then describe a mathematical model of a spherical cells-which to our knowledge is the first one capable of handling a multitude of buffer reactions-that our team has recently developed to simulate changes in pHi and pHo caused by movements of acid-base equivalents across the plasma membrane of a Xenopus oocyte. Finally, we extend our work to a consideration of the effects of simultaneous CO2 and HCO3(-) influx into a cell, and envision how future models might extend to other cell types (e.g., erythrocytes) or tissues (e.g., renal proximal-tubule epithelium) important for whole-body pH homeostasis. Copyright © 2015 Elsevier Ltd. All rights reserved.

Multipebble Simulations for Alternating Automata

Science.gov (United States)

Clemente, Lorenzo; Mayr, Richard

We study generalized simulation relations for alternating Büchi automata (ABA), as well as alternating finite automata. Having multiple pebbles allows the Duplicator to "hedge her bets" and delay decisions in the simulation game, thus yielding a coarser simulation relation. We define (k 1,k 2)-simulations, with k 1/k 2 pebbles on the left/right, respectively. This generalizes previous work on ordinary simulation (i.e., (1,1)-simulation) for nondeterministic Büchi automata (NBA)[4] in and ABA in [5], and (1,k)-simulation for NBA in [3].

Using cellular automata for parallel simulation of laser dynamics with dynamic load balancing

NARCIS (Netherlands)

Guisado, J.L.; Fernández de Vega, F.; Jiménez Morales, F.; Iskra, K.A.; Sloot, P.M.A.

2008-01-01

We present an analysis of the feasibility of executing a parallel bioinspired model of laser dynamics, based on cellular automata (CA), on the usual target platform of this kind of applications: a heterogeneous non-dedicated cluster. As this model employs a synchronous CA, using the single program,

MATHEMATICAL MODEL MANIPULATOR ROBOTS

Directory of Open Access Journals (Sweden)

O. N. Krakhmalev

2015-12-01

Full Text Available A mathematical model to describe the dynamics of manipulator robots. Mathematical model are the implementation of the method based on the Lagrange equation and using the transformation matrices of elastic coordinates. Mathematical model make it possible to determine the elastic deviations of manipulator robots from programmed motion trajectories caused by elastic deformations in hinges, which are taken into account in directions of change of the corresponding generalized coordinates. Mathematical model is approximated and makes it possible to determine small elastic quasi-static deviations and elastic vibrations. The results of modeling the dynamics by model are compared to the example of a two-link manipulator system. The considered model can be used when performing investigations of the mathematical accuracy of the manipulator robots.

An algorithm for learning real-time automata

NARCIS (Netherlands)

Verwer, S.E.; De Weerdt, M.M.; Witteveen, C.

2007-01-01

We describe an algorithm for learning simple timed automata, known as real-time automata. The transitions of real-time automata can have a temporal constraint on the time of occurrence of the current symbol relative to the previous symbol. The learning algorithm is similar to the redblue fringe

Random networks of Boolean cellular automata

Energy Technology Data Exchange (ETDEWEB)

Miranda, Enrique [Comision Nacional de Energia Atomica, San Carlos de Bariloche (Argentina). Centro Atomico Bariloche

1990-01-01

Some recent results about random networks of Boolean automata -the Kauffman model- are reviewed. The structure of configuration space is explored. Ultrametricity between cycles is analyzed and the effects of noise in the dynamics are studied. (Author).

Random networks of Boolean cellular automata

International Nuclear Information System (INIS)

Miranda, Enrique

1990-01-01

Some recent results about random networks of Boolean automata -the Kauffman model- are reviewed. The structure of configuration space is explored. Ultrametricity between cycles is analyzed and the effects of noise in the dynamics are studied. (Author)

Decentralized indirect methods for learning automata games.

Science.gov (United States)

Tilak, Omkar; Martin, Ryan; Mukhopadhyay, Snehasis

2011-10-01

We discuss the application of indirect learning methods in zero-sum and identical payoff learning automata games. We propose a novel decentralized version of the well-known pursuit learning algorithm. Such a decentralized algorithm has significant computational advantages over its centralized counterpart. The theoretical study of such a decentralized algorithm requires the analysis to be carried out in a nonstationary environment. We use a novel bootstrapping argument to prove the convergence of the algorithm. To our knowledge, this is the first time that such analysis has been carried out for zero-sum and identical payoff games. Extensive simulation studies are reported, which demonstrate the proposed algorithm's fast and accurate convergence in a variety of game scenarios. We also introduce the framework of partial communication in the context of identical payoff games of learning automata. In such games, the automata may not communicate with each other or may communicate selectively. This comprehensive framework has the capability to model both centralized and decentralized games discussed in this paper.

Development of syntax of intuition-based learning model in solving mathematics problems

Science.gov (United States)

Yeni Heryaningsih, Nok; Khusna, Hikmatul

2018-01-01

The aim of the research was to produce syntax of Intuition Based Learning (IBL) model in solving mathematics problem for improving mathematics students’ achievement that valid, practical and effective. The subject of the research were 2 classes in grade XI students of SMAN 2 Sragen, Central Java. The type of the research was a Research and Development (R&D). Development process adopted Plomp and Borg & Gall development model, they were preliminary investigation step, design step, realization step, evaluation and revision step. Development steps were as follow: (1) Collected the information and studied of theories in Preliminary Investigation step, studied about intuition, learning model development, students condition, and topic analysis, (2) Designed syntax that could bring up intuition in solving mathematics problem and then designed research instruments. They were several phases that could bring up intuition, Preparation phase, Incubation phase, Illumination phase and Verification phase, (3) Realized syntax of Intuition Based Learning model that has been designed to be the first draft, (4) Did validation of the first draft to the validator, (5) Tested the syntax of Intuition Based Learning model in the classrooms to know the effectiveness of the syntax, (6) Conducted Focus Group Discussion (FGD) to evaluate the result of syntax model testing in the classrooms, and then did the revision on syntax IBL model. The results of the research were produced syntax of IBL model in solving mathematics problems that valid, practical and effective. The syntax of IBL model in the classroom were, (1) Opening with apperception, motivations and build students’ positive perceptions, (2) Teacher explains the material generally, (3) Group discussion about the material, (4) Teacher gives students mathematics problems, (5) Doing exercises individually to solve mathematics problems with steps that could bring up students’ intuition: Preparations, Incubation, Illumination, and

Confluence reduction for Markov automata (extended version)

NARCIS (Netherlands)

Timmer, Mark; van de Pol, Jan Cornelis; Stoelinga, Mariëlle Ida Antoinette

Markov automata are a novel formalism for specifying systems exhibiting nondeterminism, probabilistic choices and Markovian rates. Recently, the process algebra MAPA was introduced to efficiently model such systems. As always, the state space explosion threatens the analysability of the models

Dynamic and quantitative method of analyzing service consistency evolution based on extended hierarchical finite state automata.

Science.gov (United States)

Fan, Linjun; Tang, Jun; Ling, Yunxiang; Li, Benxian

2014-01-01

This paper is concerned with the dynamic evolution analysis and quantitative measurement of primary factors that cause service inconsistency in service-oriented distributed simulation applications (SODSA). Traditional methods are mostly qualitative and empirical, and they do not consider the dynamic disturbances among factors in service's evolution behaviors such as producing, publishing, calling, and maintenance. Moreover, SODSA are rapidly evolving in terms of large-scale, reusable, compositional, pervasive, and flexible features, which presents difficulties in the usage of traditional analysis methods. To resolve these problems, a novel dynamic evolution model extended hierarchical service-finite state automata (EHS-FSA) is constructed based on finite state automata (FSA), which formally depict overall changing processes of service consistency states. And also the service consistency evolution algorithms (SCEAs) based on EHS-FSA are developed to quantitatively assess these impact factors. Experimental results show that the bad reusability (17.93% on average) is the biggest influential factor, the noncomposition of atomic services (13.12%) is the second biggest one, and the service version's confusion (1.2%) is the smallest one. Compared with previous qualitative analysis, SCEAs present good effectiveness and feasibility. This research can guide the engineers of service consistency technologies toward obtaining a higher level of consistency in SODSA.

Dynamic and Quantitative Method of Analyzing Service Consistency Evolution Based on Extended Hierarchical Finite State Automata

Directory of Open Access Journals (Sweden)

Linjun Fan

2014-01-01

Full Text Available This paper is concerned with the dynamic evolution analysis and quantitative measurement of primary factors that cause service inconsistency in service-oriented distributed simulation applications (SODSA. Traditional methods are mostly qualitative and empirical, and they do not consider the dynamic disturbances among factors in service’s evolution behaviors such as producing, publishing, calling, and maintenance. Moreover, SODSA are rapidly evolving in terms of large-scale, reusable, compositional, pervasive, and flexible features, which presents difficulties in the usage of traditional analysis methods. To resolve these problems, a novel dynamic evolution model extended hierarchical service-finite state automata (EHS-FSA is constructed based on finite state automata (FSA, which formally depict overall changing processes of service consistency states. And also the service consistency evolution algorithms (SCEAs based on EHS-FSA are developed to quantitatively assess these impact factors. Experimental results show that the bad reusability (17.93% on average is the biggest influential factor, the noncomposition of atomic services (13.12% is the second biggest one, and the service version’s confusion (1.2% is the smallest one. Compared with previous qualitative analysis, SCEAs present good effectiveness and feasibility. This research can guide the engineers of service consistency technologies toward obtaining a higher level of consistency in SODSA.

Construction of fuzzy automata by fuzzy experiments

International Nuclear Information System (INIS)

Mironov, A.

1994-01-01

The solving the problem of canonical realization of partial reaction morphisms (PRM) for automata in toposes and fuzzy automata is addressed. This problem extends the optimal construction problem for finite deterministic automata by experiments. In the present paper the conception of canonical realization of PRM for automata in toposes is introduced and the sufficient conditions for the existence of canonical realizations for PRM in toposes are presented. As a consequence of this result the existence of canonical realizations for PRM in the category of fuzzy sets over arbitrary complete chain is proven

Construction of fuzzy automata by fuzzy experiments

Energy Technology Data Exchange (ETDEWEB)

Mironov, A [Moscow Univ. (Russian Federation). Dept. of Mathematics and Computer Science

1994-12-31

The solving the problem of canonical realization of partial reaction morphisms (PRM) for automata in toposes and fuzzy automata is addressed. This problem extends the optimal construction problem for finite deterministic automata by experiments. In the present paper the conception of canonical realization of PRM for automata in toposes is introduced and the sufficient conditions for the existence of canonical realizations for PRM in toposes are presented. As a consequence of this result the existence of canonical realizations for PRM in the category of fuzzy sets over arbitrary complete chain is proven.

Treatment Analysis in a Cancer Stem Cell Context Using a Tumor Growth Model Based on Cellular Automata.

Science.gov (United States)

Monteagudo, Ángel; Santos, José

2015-01-01

Cancer can be viewed as an emergent behavior in terms of complex system theory and artificial life, Cellular Automata (CA) being the tool most used for studying and characterizing the emergent behavior. Different approaches with CA models were used to model cancer growth. The use of the abstract model of acquired cancer hallmarks permits the direct modeling at cellular level, where a cellular automaton defines the mitotic and apoptotic behavior of cells, and allows for an analysis of different dynamics of the cellular system depending on the presence of the different hallmarks. A CA model based on the presence of hallmarks in the cells, which includes a simulation of the behavior of Cancer Stem Cells (CSC) and their implications for the resultant growth behavior of the multicellular system, was employed. This modeling of cancer growth, in the avascular phase, was employed to analyze the effect of cancer treatments in a cancer stem cell context. The model clearly explains why, after treatment against non-stem cancer cells, the regrowth capability of CSCs generates a faster regrowth of tumor behavior, and also shows that a continuous low-intensity treatment does not favor CSC proliferation and differentiation, thereby allowing an unproblematic control of future tumor regrowth. The analysis performed indicates that, contrary to the current attempts at CSC control, trying to make CSC proliferation more difficult is an important point to consider, especially in the immediate period after a standard treatment for controlling non-stem cancer cell proliferation.

A federation of simulations based on cellular automata in cyber-physical systems

Directory of Open Access Journals (Sweden)

Hoang Van Tran

2016-02-01

Full Text Available In cyber-physical system (CPS, cooperation between a variety of computational and physical elements usually poses difficulties to current modelling and simulation tools. Although much research has proposed to address those challenges, most solutions do not completely cover uncertain interactions in CPS. In this paper, we present a new approach to federate simulations for CPS. A federation is a combination of, and coordination between simulations upon a standard of communication. In addition, a mixed simulation is defined as several parallel simulations federated in a common time progress. Such simulations run on the models of physical systems, which are built based on cellular automata theory. The experimental results are performed on a federation of three simulations of forest fire spread, river pollution diffusion and wireless sensor network. The obtained results can be utilized to observe and predict the behaviours of physical systems in their interactions.

Associating current knowledge with that of past experience based on knowledge about automata

Energy Technology Data Exchange (ETDEWEB)

Koenig, E C

1982-01-01

Important to the performance of interactive systems is the ability of its members to associate current knowledge with knowledge of past experience. Knowledge association results in greater detail of a current knowledge and is demonstrated through the use of examples. It is based on knowledge about automata and the knowledge structures are in the form of graphs. 11 references.

Factorization, reduction and embedding in integrable cellular automata

International Nuclear Information System (INIS)

Kuniba, Atsuo; Takagi, Taichiro; Takenouchi, Akira

2004-01-01

Factorized dynamics in soliton cellular automata with quantum group symmetry is identified with a motion of particles and anti-particles exhibiting pair creation and annihilation. An embedding scheme is presented showing that the D (1) n -automaton contains, as certain subsectors, the box-ball systems and all the other automata associated with the crystal bases of non-exceptional affine Lie algebras. The results extend the earlier ones to higher representations by a certain reduction and to a wider class of boundary conditions

Cellular Automata and the Humanities.

Science.gov (United States)

Gallo, Ernest

1994-01-01

The use of cellular automata to analyze several pre-Socratic hypotheses about the evolution of the physical world is discussed. These hypotheses combine characteristics of both rigorous and metaphoric language. Since the computer demands explicit instructions for each step in the evolution of the automaton, such models can reveal conceptual…

Outer-totalistic cellular automata on graphs

International Nuclear Information System (INIS)

Marr, Carsten; Huett, Marc-Thorsten

2009-01-01

We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics

Interface Input/Output Automata

DEFF Research Database (Denmark)

Larsen, Kim Guldstrand; Nyman, Ulrik; Wasowski, Andrzej

2006-01-01

Building on the theory of interface automata by de Alfaro and Henzinger we design an interface language for Lynch’s I/O, a popular formalism used in the development of distributed asynchronous systems, not addressed by previous interface research. We introduce an explicit separation of assumptions...... a method for solving systems of relativized behavioral inequalities as used in our setup and draw a formal correspondence between our work and interface automata....

Performance Evaluation of Components Using a Granularity-based Interface Between Real-Time Calculus and Timed Automata

Directory of Open Access Journals (Sweden)

Karine Altisen

2010-06-01

Full Text Available To analyze complex and heterogeneous real-time embedded systems, recent works have proposed interface techniques between real-time calculus (RTC and timed automata (TA, in order to take advantage of the strengths of each technique for analyzing various components. But the time to analyze a state-based component modeled by TA may be prohibitively high, due to the state space explosion problem. In this paper, we propose a framework of granularity-based interfacing to speed up the analysis of a TA modeled component. First, we abstract fine models to work with event streams at coarse granularity. We perform analysis of the component at multiple coarse granularities and then based on RTC theory, we derive lower and upper bounds on arrival patterns of the fine output streams using the causality closure algorithm. Our framework can help to achieve tradeoffs between precision and analysis time.

Secure information release in timed automata

DEFF Research Database (Denmark)

Vasilikos, Panagiotis; Nielson, Flemming; Nielson, Hanne Riis

2018-01-01

. In this paper, we develop a formal approach of information flow for timed automata that allows intentional information leaks. The security of a timed automaton is then defined using a bisimulation relation that takes account of the non-determinism and the clocks of timed automata. Finally, we define...... of security goals for confidentiality and integrity. Notions of security based on Information flow control, such as non-interference, provide strong guarantees that no information is leaked; however, many cyberphysical systems leak intentionally some information in order to achieve their purposes...... an algorithm that traverses a timed automaton and imposes information flow constraints on it and we prove that our algorithm is sound with respect to our security notion....

Verification of Continuous Dynamical Systems by Timed Automata

DEFF Research Database (Denmark)

Sloth, Christoffer; Wisniewski, Rafael

2011-01-01

This paper presents a method for abstracting continuous dynamical systems by timed automata. The abstraction is based on partitioning the state space of a dynamical system using positive invariant sets, which form cells that represent locations of a timed automaton. The abstraction is intended......, which is generated utilizing sub-level sets of Lyapunov functions, as they are positive invariant sets. It is shown that this partition generates sound and complete abstractions. Furthermore, the complete abstractions can be composed of multiple timed automata, allowing parallelization...

Automata Learning through Counterexample Guided Abstraction Refinement

DEFF Research Database (Denmark)

Aarts, Fides; Heidarian, Faranak; Kuppens, Harco

2012-01-01

to a small set of abstract events that can be handled by automata learning tools. In this article, we show how such abstractions can be constructed fully automatically for a restricted class of extended finite state machines in which one can test for equality of data parameters, but no operations on data...... are allowed. Our approach uses counterexample-guided abstraction refinement: whenever the current abstraction is too coarse and induces nondeterministic behavior, the abstraction is refined automatically. Using Tomte, a prototype tool implementing our algorithm, we have succeeded to learn – fully......Abstraction is the key when learning behavioral models of realistic systems. Hence, in most practical applications where automata learning is used to construct models of software components, researchers manually define abstractions which, depending on the history, map a large set of concrete events...

Particles and Patterns in Cellular Automata

International Nuclear Information System (INIS)

Jen, E.; Das, R.; Beasley, C.E.

1999-01-01

This is the final report of a three-year, Laboratory Directed Research and Development (LDRD) project at Los Alamos National Laboratory (LANL). Our objective has been to develop tools for studying particle interactions in a class of dynamical systems characterized by discreteness, determinism, local interaction, and an inherently parallel form of evolution. These systems can be described by cellular automata (CA) and the behavior we studied has improved our understanding of the nature of patterns generated by CAs, their ability to perform global computations, and their relationship to continuous dynamical systems. We have also developed a rule-table mathematics that enables one to custom-design CA rule tables to generate patterns of specified types, or to perform specified computational tasks

Monitor-Based Statistical Model Checking for Weighted Metric Temporal Logic

DEFF Research Database (Denmark)

Bulychev, Petr; David, Alexandre; Larsen, Kim Guldstrand

2012-01-01

We present a novel approach and implementation for ana- lysing weighted timed automata (WTA) with respect to the weighted metric temporal logic (WMTL≤ ). Based on a stochastic semantics of WTAs, we apply statistical model checking (SMC) to estimate and test probabilities of satisfaction with desi......We present a novel approach and implementation for ana- lysing weighted timed automata (WTA) with respect to the weighted metric temporal logic (WMTL≤ ). Based on a stochastic semantics of WTAs, we apply statistical model checking (SMC) to estimate and test probabilities of satisfaction...

Execution spaces for simple higher dimensional automata

DEFF Research Database (Denmark)

Raussen, Martin

Higher Dimensional Automata (HDA) are highly expressive models for concurrency in Computer Science, cf van Glabbeek [26]. For a topologist, they are attractive since they can be modeled as cubical complexes - with an inbuilt restriction for directions´of allowable (d-)paths. In Raussen [25], we...

A Cellular Automata Model of Infection Control on Medical Implants

Science.gov (United States)

Prieto-Langarica, Alicia; Kojouharov, Hristo; Chen-Charpentier, Benito; Tang, Liping

2011-01-01

S. epidermidis infections on medically implanted devices are a common problem in modern medicine due to the abundance of the bacteria. Once inside the body, S. epidermidis gather in communities called biofilms and can become extremely hard to eradicate, causing the patient serious complications. We simulate the complex S. epidermidis-Neutrophils interactions in order to determine the optimum conditions for the immune system to be able to contain the infection and avoid implant rejection. Our cellular automata model can also be used as a tool for determining the optimal amount of antibiotics for combating biofilm formation on medical implants. PMID:23543851

On path hypercompositions in graphs and automata

Directory of Open Access Journals (Sweden)

Massouros Christos G.

2016-01-01

Full Text Available The paths in graphs define hypercompositions in the set of their vertices and therefore it is feasible to associate hypercompositional structures to each graph. Similarly, the strings of letters from their alphabet, define hypercompositions in the automata, which in turn define the associated hypergroups to the automata. The study of the associated hypercompositional structures gives results in both, graphs and automata theory.

An Investigation of Mathematical Modeling with Pre-Service Secondary Mathematics Teachers

Science.gov (United States)

Thrasher, Emily Plunkett

2016-01-01

The goal of this thesis was to investigate and enhance our understanding of what occurs while pre-service mathematics teachers engage in a mathematical modeling unit that is broadly based upon mathematical modeling as defined by the Common Core State Standards for Mathematics (National Governors Association Center for Best Practices & Council…

Design based Investigation on Construction of Mathematical Modelling Problems: Example of Financial Content

Directory of Open Access Journals (Sweden)

Melike TURAL SÖNMEZ

2017-12-01

Full Text Available The purpose of this study is to examine the construction of mathematical modelling problems process in the content of financial literacy. It is also aimed to create design proposals for construction of mathematical modelling problems. A design based research method was used in this study. The participants were three seventh grade students, six finance experts and nine mathematics education experts. Data collection tools were transcription of video and tapes group discussions, presentations and worksheets during mathematical modelling activities, and participant experts’ feedback form about mathematical modelling problems. There were three stages in this study. First stage was application of preliminary study. This stage gave information about convenience of problems to grade level, students’ timing for solution of problems, clarity of problems and students’ background about content. In second stage, finance experts commented on convenience of mathematical modelling problems to financial literacy standards. In third stage, mathematics education experts commented on convenience of problems to students’ grade level, mathematical modelling principles and seventh grade mathematics lesson objectives. They also gave suggestion on progress. The frequency value of theme in feedback forms was calculated and experts’ expressions were given as citation. It was given suggestion about stages and application of the design guide

Network reliability assessment using a cellular automata approach

International Nuclear Information System (INIS)

Rocco S, Claudio M.; Moreno, Jose Ali

2002-01-01

Two cellular automata (CA) models that evaluate the s-t connectedness and shortest path in a network are presented. CA based algorithms enhance the performance of classical algorithms, since they allow a more reliable and straightforward parallel implementation resulting in a dynamic network evaluation, where changes in the connectivity and/or link costs can readily be incorporated avoiding recalculation from scratch. The paper also demonstrates how these algorithms can be applied for network reliability evaluation (based on Monte-Carlo approach) and for finding s-t path with maximal reliability

Effects of Initial Symmetry on the Global Symmetry of One-Dimensional Legal Cellular Automata

Directory of Open Access Journals (Sweden)

Ikuko Tanaka

2015-09-01

Full Text Available To examine the development of pattern formation from the viewpoint of symmetry, we applied a two-dimensional discrete Walsh analysis to a one-dimensional cellular automata model under two types of regular initial conditions. The amount of symmetropy of cellular automata (CA models under regular and random initial conditions corresponds to three Wolfram’s classes of CAs, identified as Classes II, III, and IV. Regular initial conditions occur in two groups. One group that makes a broken, regular pattern formation has four types of symmetry, whereas the other group that makes a higher hierarchy pattern formation has only two types. Additionally, both final pattern formations show an increased amount of symmetropy as time passes. Moreover, the final pattern formations are affected by iterations of base rules of CA models of chaos dynamical systems. The growth design formations limit possibilities: the ratio of developing final pattern formations under a regular initial condition decreases in the order of Classes III, II, and IV. This might be related to the difference in degree in reference to surrounding conditions. These findings suggest that calculations of symmetries of the structures of one-dimensional cellular automata models are useful for revealing rules of pattern generation for animal bodies.

Treatment Analysis in a Cancer Stem Cell Context Using a Tumor Growth Model Based on Cellular Automata.

Directory of Open Access Journals (Sweden)

Ángel Monteagudo

Full Text Available Cancer can be viewed as an emergent behavior in terms of complex system theory and artificial life, Cellular Automata (CA being the tool most used for studying and characterizing the emergent behavior. Different approaches with CA models were used to model cancer growth. The use of the abstract model of acquired cancer hallmarks permits the direct modeling at cellular level, where a cellular automaton defines the mitotic and apoptotic behavior of cells, and allows for an analysis of different dynamics of the cellular system depending on the presence of the different hallmarks. A CA model based on the presence of hallmarks in the cells, which includes a simulation of the behavior of Cancer Stem Cells (CSC and their implications for the resultant growth behavior of the multicellular system, was employed. This modeling of cancer growth, in the avascular phase, was employed to analyze the effect of cancer treatments in a cancer stem cell context. The model clearly explains why, after treatment against non-stem cancer cells, the regrowth capability of CSCs generates a faster regrowth of tumor behavior, and also shows that a continuous low-intensity treatment does not favor CSC proliferation and differentiation, thereby allowing an unproblematic control of future tumor regrowth. The analysis performed indicates that, contrary to the current attempts at CSC control, trying to make CSC proliferation more difficult is an important point to consider, especially in the immediate period after a standard treatment for controlling non-stem cancer cell proliferation.

Study of spatially extended dynamical systems using probabilistic cellular automata

International Nuclear Information System (INIS)

Vanag, Vladimir K

1999-01-01

Spatially extended dynamical systems are ubiquitous and include such things as insect and animal populations; complex chemical, technological, and geochemical processes; humanity itself, and much more. It is clearly desirable to have a certain universal tool with which the highly complex behaviour of nonlinear dynamical systems can be analyzed and modelled. For this purpose, cellular automata seem to be good candidates. In the present review, emphasis is placed on the possibilities that various types of probabilistic cellular automata (PCA), such as DSMC (direct simulation Monte Carlo) and LGCA (lattice-gas cellular automata), offer. The methods are primarily designed for modelling spatially extended dynamical systems with inner fluctuations accounted for. For the Willamowskii-Roessler and Oregonator models, PCA applications to the following problems are illustrated: the effect of fluctuations on the dynamics of nonlinear systems; Turing structure formation; the effect of hydrodynamic modes on the behaviour of nonlinear chemical systems (stirring effects); bifurcation changes in the dynamical regimes of complex systems with restricted geometry or low spatial dimension; and the description of chemical systems in microemulsions. (reviews of topical problems)

Formal languages, automata and numeration systems introduction to combinatorics on words

CERN Document Server

Rigo, Michel

2014-01-01

Formal Languages, Automaton and Numeration Systems presents readers with a review of research related to formal language theory, combinatorics on words or numeration systems, such as Words, DLT (Developments in Language Theory), ICALP, MFCS (Mathematical Foundation of Computer Science), Mons Theoretical Computer Science Days, Numeration, CANT (Combinatorics, Automata and Number Theory). Combinatorics on words deals with problems that can be stated in a non-commutative monoid, such as subword complexity of finite or infinite words, construction and properties of infinite words, unavoidabl

Finite mathematics models and applications

CERN Document Server

Morris, Carla C

2015-01-01

Features step-by-step examples based on actual data and connects fundamental mathematical modeling skills and decision making concepts to everyday applicability Featuring key linear programming, matrix, and probability concepts, Finite Mathematics: Models and Applications emphasizes cross-disciplinary applications that relate mathematics to everyday life. The book provides a unique combination of practical mathematical applications to illustrate the wide use of mathematics in fields ranging from business, economics, finance, management, operations research, and the life and social sciences.

A Review on Block Matching Motion Estimation and Automata Theory based Approaches for Fractal Coding

Directory of Open Access Journals (Sweden)

Shailesh Kamble

2016-12-01

Full Text Available Fractal compression is the lossy compression technique in the field of gray/color image and video compression. It gives high compression ratio, better image quality with fast decoding time but improvement in encoding time is a challenge. This review paper/article presents the analysis of most significant existing approaches in the field of fractal based gray/color images and video compression, different block matching motion estimation approaches for finding out the motion vectors in a frame based on inter-frame coding and intra-frame coding i.e. individual frame coding and automata theory based coding approaches to represent an image/sequence of images. Though different review papers exist related to fractal coding, this paper is different in many sense. One can develop the new shape pattern for motion estimation and modify the existing block matching motion estimation with automata coding to explore the fractal compression technique with specific focus on reducing the encoding time and achieving better image/video reconstruction quality. This paper is useful for the beginners in the domain of video compression.

Mathematical modelling

DEFF Research Database (Denmark)

Blomhøj, Morten

2004-01-01

Developing competences for setting up, analysing and criticising mathematical models are normally seen as relevant only from and above upper secondary level. The general belief among teachers is that modelling activities presuppose conceptual understanding of the mathematics involved. Mathematical...... roots for the construction of important mathematical concepts. In addition competences for setting up, analysing and criticising modelling processes and the possible use of models is a formative aim in this own right for mathematics teaching in general education. The paper presents a theoretical...... modelling, however, can be seen as a practice of teaching that place the relation between real life and mathematics into the centre of teaching and learning mathematics, and this is relevant at all levels. Modelling activities may motivate the learning process and help the learner to establish cognitive...

Language Emptiness of Continuous-Time Parametric Timed Automata

DEFF Research Database (Denmark)

Benes, Nikola; Bezdek, Peter; Larsen, Kim Guldstrand

2015-01-01

Parametric timed automata extend the standard timed automata with the possibility to use parameters in the clock guards. In general, if the parameters are real-valued, the problem of language emptiness of such automata is undecidable even for various restricted subclasses. We thus focus on the case...... where parameters are assumed to be integer-valued, while the time still remains continuous. On the one hand, we show that the problem remains undecidable for parametric timed automata with three clocks and one parameter. On the other hand, for the case with arbitrary many clocks where only one......-time semantics only. To the best of our knowledge, this is the first positive result in the case of continuous-time and unbounded integer parameters, except for the rather simple case of single-clock automata....

Minimal entropy approximation for cellular automata

International Nuclear Information System (INIS)

Fukś, Henryk

2014-01-01

We present a method for the construction of approximate orbits of measures under the action of cellular automata which is complementary to the local structure theory. The local structure theory is based on the idea of Bayesian extension, that is, construction of a probability measure consistent with given block probabilities and maximizing entropy. If instead of maximizing entropy one minimizes it, one can develop another method for the construction of approximate orbits, at the heart of which is the iteration of finite-dimensional maps, called minimal entropy maps. We present numerical evidence that the minimal entropy approximation sometimes outperforms the local structure theory in characterizing the properties of cellular automata. The density response curve for elementary CA rule 26 is used to illustrate this claim. (paper)

Data Automata in Scala

Science.gov (United States)

Havelund, Klaus

2014-01-01

The field of runtime verification has during the last decade seen a multitude of systems for monitoring event sequences (traces) emitted by a running system. The objective is to ensure correctness of a system by checking its execution traces against formal specifications representing requirements. A special challenge is data parameterized events, where monitors have to keep track of the combination of control states as well as data constraints, relating events and the data they carry across time points. This poses a challenge wrt. efficiency of monitors, as well as expressiveness of logics. Data automata is a form of automata where states are parameterized with data, supporting monitoring of data parameterized events. We describe the full details of a very simple API in the Scala programming language, an internal DSL (Domain-Specific Language), implementing data automata. The small implementation suggests a design pattern. Data automata allow transition conditions to refer to other states than the source state, and allow target states of transitions to be inlined, offering a temporal logic flavored notation. An embedding of a logic in a high-level language like Scala in addition allows monitors to be programmed using all of Scala's language constructs, offering the full flexibility of a programming language. The framework is demonstrated on an XML processing scenario previously addressed in related work.

Connection machine: a computer architecture based on cellular automata

Energy Technology Data Exchange (ETDEWEB)

Hillis, W D

1984-01-01

This paper describes the connection machine, a programmable computer based on cellular automata. The essential idea behind the connection machine is that a regular locally-connected cellular array can be made to behave as if the processing cells are connected into any desired topology. When the topology of the machine is chosen to match the topology of the application program, the result is a fast, powerful computing engine. The connection machine was originally designed to implement knowledge retrieval operations in artificial intelligence programs, but the hardware and the programming techniques are apparently applicable to a much larger class of problems. A machine with 100000 processing cells is currently being constructed. 27 references.

Spin networks, quantum automata and link invariants

International Nuclear Information System (INIS)

Garnerone, Silvano; Marzuoli, Annalisa; Rasetti, Mario

2006-01-01

The spin network simulator model represents a bridge between (generalized) circuit schemes for standard quantum computation and approaches based on notions from Topological Quantum Field Theories (TQFT). More precisely, when working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum automata which in turn represent discrete versions of topological quantum computation models. Such a quantum combinatorial scheme, which essentially encodes SU(2) Racah-Wigner algebra and its braided counterpart, is particularly suitable to address problems in topology and group theory and we discuss here a finite states-quantum automaton able to accept the language of braid group in view of applications to the problem of estimating link polynomials in Chern-Simons field theory

Linear reversible second-order cellular automata and their first-order matrix equivalents

International Nuclear Information System (INIS)

Macfarlane, A J

2004-01-01

Linear or one-dimensional reversible second-order cellular automata, exemplified by three cases named as RCA1-3, are introduced. Displays of their evolution in discrete time steps, t=0, 1, 2, ..., from their simplest initial states and on the basis of updating rules in modulo 2 arithmetic, are presented. In these, shaded and unshaded squares denote cells whose cell variables are equal to one and zero respectively. This paper is devoted to finding general formulas for, and explicit numerical evaluations of, the weights N(t) of the states or configurations of RCA1-3, i.e. the total number of shaded cells in tth line of their displays. This is achieved by means of the replacement of RCA1-3 by the equivalent linear first-order matrix automata MCA1-3, for which the cell variables are 2x2 matrices, instead of just numbers (element of Z 2 ) as for RCA1-3. MCA1-3 are tractable because it has been possible to generalize to them the heavy duty methods already well-developed for ordinary first-order cellular automata like those of Wolfram's Rules 90 and 150. While the automata MCA1-3 are thought to be of genuine interest in their own right, with untapped further mathematical potential, their treatment has been applied here to expediting derivation of a large body of general and explicit results for N(t) for RCA1-3. Amongst explicit results obtained are formulas also for each of RCA1-3 for the total weight of the configurations of the first 2 M times, M=0, 1, 2, ..

Cell Based GIS as Cellular Automata for Disaster Spreading Predictions and Required Data Systems

Directory of Open Access Journals (Sweden)

Kohei Arai

2013-03-01

Full Text Available A method for prediction and simulation based on the Cell Based Geographic Information System(GIS as Cellular Automata (CA is proposed together with required data systems, in particular metasearch engine usage in an unified way. It is confirmed that the proposed cell based GIS as CA has flexible usage of the attribute information that is attached to the cell in concert with location information and does work for disaster spreading simulation and prediction.

Subsequence Automata with Default Transitions

DEFF Research Database (Denmark)

Bille, Philip; Gørtz, Inge Li; Skjoldjensen, Frederik Rye

2016-01-01

of states and transitions) of the subsequence automaton is O(nσ) and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with default transitions, that is, special transitions to be taken only if none of the regular transitions match the current character, and which do...... not consume the current character. We show that with default transitions, much smaller subsequence automata are possible, and provide a full trade-off between the size of the automaton and the delay, i.e., the maximum number of consecutive default transitions followed before consuming a character......(nσ) and delay O(1), thus matching the bound for the standard subsequence automaton construction. The key component of our result is a novel hierarchical automata construction of independent interest....

Applying Mathematical Optimization Methods to an ACT-R Instance-Based Learning Model.

Science.gov (United States)

Said, Nadia; Engelhart, Michael; Kirches, Christian; Körkel, Stefan; Holt, Daniel V

2016-01-01

Computational models of cognition provide an interface to connect advanced mathematical tools and methods to empirically supported theories of behavior in psychology, cognitive science, and neuroscience. In this article, we consider a computational model of instance-based learning, implemented in the ACT-R cognitive architecture. We propose an approach for obtaining mathematical reformulations of such cognitive models that improve their computational tractability. For the well-established Sugar Factory dynamic decision making task, we conduct a simulation study to analyze central model parameters. We show how mathematical optimization techniques can be applied to efficiently identify optimal parameter values with respect to different optimization goals. Beyond these methodological contributions, our analysis reveals the sensitivity of this particular task with respect to initial settings and yields new insights into how average human performance deviates from potential optimal performance. We conclude by discussing possible extensions of our approach as well as future steps towards applying more powerful derivative-based optimization methods.

Applying Mathematical Optimization Methods to an ACT-R Instance-Based Learning Model.

Directory of Open Access Journals (Sweden)

Nadia Said

Full Text Available Computational models of cognition provide an interface to connect advanced mathematical tools and methods to empirically supported theories of behavior in psychology, cognitive science, and neuroscience. In this article, we consider a computational model of instance-based learning, implemented in the ACT-R cognitive architecture. We propose an approach for obtaining mathematical reformulations of such cognitive models that improve their computational tractability. For the well-established Sugar Factory dynamic decision making task, we conduct a simulation study to analyze central model parameters. We show how mathematical optimization techniques can be applied to efficiently identify optimal parameter values with respect to different optimization goals. Beyond these methodological contributions, our analysis reveals the sensitivity of this particular task with respect to initial settings and yields new insights into how average human performance deviates from potential optimal performance. We conclude by discussing possible extensions of our approach as well as future steps towards applying more powerful derivative-based optimization methods.

An Interface Theory for Input/Output Automata

DEFF Research Database (Denmark)

Larsen, Kim Guldstrand; Nyman, Ulrik; Wasowski, Andrzej

Building on the theory of interface automata by de~Alfaro and Henzinger we design an interface language for Lynch's Input/Output Automata, a popular formalism used in the development of distributed asynchronous systems, not addressed by previous interface research. We introduce an explicit....... We also present a method for solving systems of relativized behavioral inequalities as used in our setup and draw a formal correspondence between our work and interface automata. Proofs are provided in an appendix....

Nonsynchronous updating in the multiverse of cellular automata.

Science.gov (United States)

Reia, Sandro M; Kinouchi, Osame

2015-04-01

In this paper we study updating effects on cellular automata rule space. We consider a subset of 6144 order-3 automata from the space of 262144 bidimensional outer-totalistic rules. We compare synchronous to asynchronous and sequential updatings. Focusing on two automata, we discuss how update changes destroy typical structures of these rules. Besides, we show that the first-order phase transition in the multiverse of synchronous cellular automata, revealed with the use of a recently introduced control parameter, seems to be robust not only to changes in update schema but also to different initial densities.

Nonsynchronous updating in the multiverse of cellular automata

Science.gov (United States)

Reia, Sandro M.; Kinouchi, Osame

2015-04-01

In this paper we study updating effects on cellular automata rule space. We consider a subset of 6144 order-3 automata from the space of 262144 bidimensional outer-totalistic rules. We compare synchronous to asynchronous and sequential updatings. Focusing on two automata, we discuss how update changes destroy typical structures of these rules. Besides, we show that the first-order phase transition in the multiverse of synchronous cellular automata, revealed with the use of a recently introduced control parameter, seems to be robust not only to changes in update schema but also to different initial densities.

Optimised determinisation and completion of finite tree automata

DEFF Research Database (Denmark)

Gallagher, John Patrick; Ajspur, Mai; Kafle, Bishoksan

2018-01-01

Determinisation and completion of finite tree automata are important operations with applications in program analysis and verification. However, the complexity of the classical procedures for determinisation and completion is high. They are not practical procedures for manipulating tree automata...... beyond very small ones. In this paper we develop an algorithm for determinisation and completion of finite tree automata, whose worst-case complexity remains unchanged, but which performs far better than existing algorithms in practice. The critical aspect of the algorithm is that the transitions...... an experimental evaluation of the algorithm on a large set of tree automata examples....

The Design of Fault Tolerant Quantum Dot Cellular Automata Based Logic

Science.gov (United States)

Armstrong, C. Duane; Humphreys, William M.; Fijany, Amir

2002-01-01

As transistor geometries are reduced, quantum effects begin to dominate device performance. At some point, transistors cease to have the properties that make them useful computational components. New computing elements must be developed in order to keep pace with Moore s Law. Quantum dot cellular automata (QCA) represent an alternative paradigm to transistor-based logic. QCA architectures that are robust to manufacturing tolerances and defects must be developed. We are developing software that allows the exploration of fault tolerant QCA gate architectures by automating the specification, simulation, analysis and documentation processes.

Mathematics Instructional Model Based on Realistic Mathematics Education to Promote Problem Solving Ability at Junior High School Padang

Directory of Open Access Journals (Sweden)

Edwin Musdi

2016-02-01

Full Text Available This research aims to develop a mathematics instructional model based realistic mathematics education (RME to promote students' problem-solving abilities. The design research used Plomp models, which consists of preliminary phase, development or proto-typing phase and assessment phase.  At this study, only the first two phases conducted. The first phase, a preliminary investigation, carried out with a literature study to examine the theory-based instructional learning RME model, characteristics of learners, learning management descriptions by junior high school mathematics teacher and relevant research. The development phase is done by developing a draft model (an early prototype model that consists of the syntax, the social system, the principle of reaction, support systems, and the impact and effects of instructional support. Early prototype model contain a draft model, lesson plans, worksheets, and assessments. Tesssmer formative evaluation model used to revise the model. In this study only phase of one to one evaluation conducted. In the ppreliminary phase has produced a theory-based learning RME model, a description of the characteristics of learners in grade VIII Junior High School Padang and the description of teacher teaching in the classroom. The result showed that most students were still not be able to solve the non-routine problem. Teachers did not optimally facilitate students to develop problem-solving skills of students. It was recommended that the model can be applied in the classroom.

Mathematical model of rolling an elastic wheel over deformable support base

Science.gov (United States)

Volskaia, V. N.; Zhileykin, M. M.; Zakharov, A. Y.

2018-02-01

One of the main direction of economic growth in Russia remains to be a speedy development of north and northeast regions that are the constituents of the 60 percent of the country territory. The further development of these territories requires new methods and technologies for solving transport and technological problems when off-road transportation of cargoes and people is conducting. One of the fundamental methods of patency prediction is imitation modeling of wheeled vehicles movement in different operating conditions. Both deformable properties of tires and physical and mechanical properties of the ground: normal tire deflection and gauge depth; variation of contact patch area depending on the load and pressure of air in the tire; existence of hysteresis losses in the tire material which are influencing on the rolling resistance due to friction processes between tire and ground in the contact patch; existence of the tangential reaction from the ground by entire contact area influence on the tractive patency. Nowadays there are two main trends in theoretical research of interaction wheeled propulsion device with ground: analytical method involving mathematical description of explored process and finite element method based on computational modeling. Mathematical models of interaction tire with the ground are used both in processes of interaction individual wheeled propulsion device with ground and researches of mobile vehicle dynamical models operated in specific road and climate conditions. One of the most significant imperfection of these models is the description of interaction wheel with flat deformable support base whereas profile of real support base surface has essential height of unevenness which is commensurate with radius of the wheel. The description of processes taking place in the ground under influence of the wheeled propulsion device using the finite element method is relatively new but most applicable lately. The application of this method allows

Improved Undecidability Results for Reachability Games on Recursive Timed Automata

Directory of Open Access Journals (Sweden)

Shankara Narayanan Krishna

2014-08-01

Full Text Available We study reachability games on recursive timed automata (RTA that generalize Alur-Dill timed automata with recursive procedure invocation mechanism similar to recursive state machines. It is known that deciding the winner in reachability games on RTA is undecidable for automata with two or more clocks, while the problem is decidable for automata with only one clock. Ouaknine and Worrell recently proposed a time-bounded theory of real-time verification by claiming that restriction to bounded-time recovers decidability for several key decision problem related to real-time verification. We revisited games on recursive timed automata with time-bounded restriction in the hope of recovering decidability. However, we found that the problem still remains undecidable for recursive timed automata with three or more clocks. Using similar proof techniques we characterize a decidability frontier for a generalization of RTA to recursive stopwatch automata.

An Automata Based Intrusion Detection Method for Internet of Things

Directory of Open Access Journals (Sweden)

Yulong Fu

2017-01-01

Full Text Available Internet of Things (IoT transforms network communication to Machine-to-Machine (M2M basis and provides open access and new services to citizens and companies. It extends the border of Internet and will be developed as one part of the future 5G networks. However, as the resources of IoT’s front devices are constrained, many security mechanisms are hard to be implemented to protect the IoT networks. Intrusion detection system (IDS is an efficient technique that can be used to detect the attackers when cryptography is broken, and it can be used to enforce the security of IoT networks. In this article, we analyzed the intrusion detection requirements of IoT networks and then proposed a uniform intrusion detection method for the vast heterogeneous IoT networks based on an automata model. The proposed method can detect and report the possible IoT attacks with three types: jam-attack, false-attack, and reply-attack automatically. We also design an experiment to verify the proposed IDS method and examine the attack of RADIUS application.

Team Automata for Security (A Survey)

NARCIS (Netherlands)

ter Beek, Maurice H.; Lenzini, Gabriele; Petrocchi, Marinella

Kleijn presented a survey of the use of team automata for the specification and analysis of phenomena from the field of computer supported cooperative work, in particular notions related to groupware systems. We present a survey of the use of team automata for the specification and analysis of some

Subsequence automata with default transitions

DEFF Research Database (Denmark)

Bille, Philip; Gørtz, Inge Li; Skjoldjensen, Frederik Rye

2017-01-01

of states and transitions) of the subsequence automaton is O(nσ) and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with default transitions, that is, special transitions to be taken only if none of the regular transitions match the current character, and which do...... not consume the current character. We show that with default transitions, much smaller subsequence automata are possible, and provide a full trade-off between the size of the automaton and the delay, i.e., the maximum number of consecutive default transitions followed before consuming a character......(1), thus matching the bound for the standard subsequence automaton construction. Finally, we generalize the result to multiple strings. The key component of our result is a novel hierarchical automata construction of independent interest....

On Determinism and Unambiguity of Weighted Two-way Automata

Directory of Open Access Journals (Sweden)

Vincent Carnino

2014-05-01

Full Text Available In this paper, we first study the conversion of weighted two-way automata to one-way automata. We show that this conversion preserves the unambiguity but does not preserve the determinism. Yet, we prove that the conversion of an unambiguous weighted one-way automaton into a two-way automaton leads to a deterministic two-way automaton. As a consequence, we prove that unambiguous weighted two-way automata are equivalent to deterministic weighted two-way automata in commutative semirings.

A Local Land Use Competition Cellular Automata Model and Its Application

Directory of Open Access Journals (Sweden)

Jun Yang

2016-06-01

Full Text Available Cellular automaton (CA is an important method in land use and cover change studies, however, the majority of research focuses on the discovery of macroscopic factors affecting LUCC, which results in ignoring the local effects within the neighborhoods. This paper introduces a Local Land Use Competition Cellular Automata (LLUC-CA model, based on local land use competition, land suitability evaluation, demand analysis of the different land use types, and multi-target land use competition allocation algorithm to simulate land use change at a micro level. The model is applied to simulate land use changes at Jinshitan National Tourist Holiday Resort from 1988 to 2012. The results show that the simulation accuracies were 64.46%, 77.21%, 85.30% and 99.14% for the agricultural land, construction land, forestland and water, respectively. In addition, comparing the simulation results of the LLUC-CA and CA-Markov model with the real land use data, their overall spatial accuracies were found to be 88.74% and 86.82%, respectively. In conclusion, the results from this study indicated that the model was an acceptable method for the simulation of large-scale land use changes, and the approach used here is applicable to analyzing the land use change driven forces and assist in decision-making.

Reconfigurable control of a power plant deaerator using learning automata

International Nuclear Information System (INIS)

Garcia, H.E.; Ray, A.; Edwards, R.M.

1991-01-01

A deaerating feedwater heater, equipped with a water level controller and a pressure controller, has been chosen to investigate the feasibility of a reconfigurable control scheme for power plants by incorporating the concept of learning automata. In this paper simulation results based on a model of the Experimental Breeder Reactor (EBR-II) at the Argonne National Laboratory site in Idaho are presented to demonstrate the efficacy of the reconfigurable control scheme

Developing Teaching Material Based on Realistic Mathematics Andoriented to the Mathematical Reasoning and Mathematical Communication

OpenAIRE

Habsah, Fitria

2017-01-01

This research aims to produce mathematics textbook for grade VII junior high school students based on realistic mathematics and oriented to the mathematical reasoning and mathematical communication. The quality is determined based on Nieveen criteria, including validity, practicality, and effectiveness.This study was a research and development and used Borg & Gall model. The subject of this research were the students of SMPN 2 Pujon-Kabupaten Malang, that is 30 students in an experimental cla...

Stochastic cellular automata model of neurosphere growth: Roles of proliferative potential, contact inhibition, cell death, and phagocytosis.

Science.gov (United States)

Sipahi, Rifat; Zupanc, Günther K H

2018-05-14

Neural stem and progenitor cells isolated from the central nervous system form, under specific culture conditions, clonal cell clusters known as neurospheres. The neurosphere assay has proven to be a powerful in vitro system to study the behavior of such cells and the development of their progeny. However, the theory of neurosphere growth has remained poorly understood. To overcome this limitation, we have, in the present paper, developed a cellular automata model, with which we examined the effects of proliferative potential, contact inhibition, cell death, and clearance of dead cells on growth rate, final size, and composition of neurospheres. Simulations based on this model indicated that the proliferative potential of the founder cell and its progenitors has a major influence on neurosphere size. On the other hand, contact inhibition of proliferation limits the final size, and reduces the growth rate, of neurospheres. The effect of this inhibition is particularly dramatic when a stem cell becomes encapsulated by differentiated or other non-proliferating cells, thereby suppressing any further mitotic division - despite the existing proliferative potential of the stem cell. Conversely, clearance of dead cells through phagocytosis is predicted to accelerate growth by reducing contact inhibition. A surprising prediction derived from our model is that cell death, while resulting in a decrease in growth rate and final size of neurospheres, increases the degree of differentiation of neurosphere cells. It is likely that the cellular automata model developed as part of the present investigation is applicable to the study of tissue growth in a wide range of systems. Copyright © 2018 Elsevier Ltd. All rights reserved.

Design of Efficient Mirror Adder in Quantum- Dot Cellular Automata

Science.gov (United States)

Mishra, Prashant Kumar; Chattopadhyay, Manju K.

2018-03-01

Lower power consumption is an essential demand for portable multimedia system using digital signal processing algorithms and architectures. Quantum dot cellular automata (QCA) is a rising nano technology for the development of high performance ultra-dense low power digital circuits. QCA based several efficient binary and decimal arithmetic circuits are implemented, however important improvements are still possible. This paper demonstrate Mirror Adder circuit design in QCA. We present comparative study of mirror adder cells designed using conventional CMOS technique and mirror adder cells designed using quantum-dot cellular automata. QCA based mirror adders are better in terms of area by order of three.

An energy and cost efficient majority-based RAM cell in quantum-dot cellular automata

Science.gov (United States)

Khosroshahy, Milad Bagherian; Moaiyeri, Mohammad Hossein; Navi, Keivan; Bagherzadeh, Nader

Nanotechnologies, notably quantum-dot cellular automata, have achieved major attentions for their prominent features as compared to the conventional CMOS circuitry. Quantum-dot cellular automata, particularly owning to its considerable reduction in size, high switching speed and ultra-low energy consumption, is considered as a potential alternative for the CMOS technology. As the memory unit is one of the most essential components in a digital system, designing a well-optimized QCA random access memory (RAM) cell is an important area of research. In this paper, a new five-input majority gate is presented which is suitable for implementing efficient single-layer QCA circuits. In addition, a new RAM cell with set and reset capabilities is designed based on the proposed majority gate, which has an efficient and low-energy structure. The functionality, performance and energy consumption of the proposed designs are evaluated based on the QCADesigner and QCAPro tools. According to the simulation results, the proposed RAM design leads to on average 38% lower total energy dissipation, 25% smaller area, 20% lower cell count, 28% lower delay and 60% lower QCA cost as compared to its previous counterparts.

Using Mathematical Modeling and Set-Based Design Principles to Recommend an Existing CVL Design

Science.gov (United States)

2017-09-01

MATHEMATICAL MODELING AND SET-BASED DESIGN PRINCIPLES TO RECOMMEND AN EXISTING CVL DESIGN by William H. Ehlies September 2017 Thesis Advisor...Office of Management and Budget, Paperwork Reduction Project (0704-0188) Washington, DC 20503. 1. AGENCY USE ONLY (Leave blank) 2. REPORT DATE...September 2017 3. REPORT TYPE AND DATES COVERED Master’s thesis 4. TITLE AND SUBTITLE USING MATHEMATICAL MODELING AND SET-BASED DESIGN PRINCIPLES

An introduction to mathematical modeling

CERN Document Server

Bender, Edward A

2000-01-01

Employing a practical, ""learn by doing"" approach, this first-rate text fosters the development of the skills beyond the pure mathematics needed to set up and manipulate mathematical models. The author draws on a diversity of fields - including science, engineering, and operations research - to provide over 100 reality-based examples. Students learn from the examples by applying mathematical methods to formulate, analyze, and criticize models. Extensive documentation, consisting of over 150 references, supplements the models, encouraging further research on models of particular interest. The

Self-organized perturbations enhance class IV behavior and 1/f power spectrum in elementary cellular automata.

Science.gov (United States)

Nakajima, Kohei; Haruna, Taichi

2011-09-01

In this paper, we propose a new class of cellular automata based on the modification of its state space. It is introduced to model a computation which is exposed to an environment. We formalized the computation as extension and projection processes of its state space and resulting misidentifications of the state. This is motivated to embed the role of an environment into the system itself, which naturally induces self-organized internal perturbations rather than the usual external perturbations. Implementing this structure into the elementary cellular automata, we characterized its effect by means of input entropy and power spectral analysis. As a result, the cellular automata with this structure showed robust class IV behavior and a 1/f power spectrum in a wide range of rule space comparative to the notion of the edge of chaos. Copyright © 2011 Elsevier Ireland Ltd. All rights reserved.

Characterizations and computational complexity of systolic trellis automata

Energy Technology Data Exchange (ETDEWEB)

Ibarra, O H; Kim, S M

1984-03-01

Systolic trellis automata are simple models for VLSI. The authors characterize the computing power of these models in terms of turing machines. The characterizations are useful in proving new results as well as giving simpler proofs of known results. They also derive lower and upper bounds on the computational complexity of the models. 18 references.

Additive Cellular Automata and Volume Growth

Directory of Open Access Journals (Sweden)

Thomas B. Ward

2000-08-01

Full Text Available Abstract: A class of dynamical systems associated to rings of S-integers in rational function fields is described. General results about these systems give a rather complete description of the well-known dynamics in one-dimensional additive cellular automata with prime alphabet, including simple formulæ for the topological entropy and the number of periodic configurations. For these systems the periodic points are uniformly distributed along some subsequence with respect to the maximal measure, and in particular are dense. Periodic points may be constructed arbitrarily close to a given configuration, and rationality of the dynamical zeta function is characterized. Throughout the emphasis is to place this particular family of cellular automata into the wider context of S-integer dynamical systems, and to show how the arithmetic of rational function fields determines their behaviour. Using a covering space the dynamics of additive cellular automata are related to a form of hyperbolicity in completions of rational function fields. This expresses the topological entropy of the automata directly in terms of volume growth in the covering space.

Wavefront cellular learning automata.

Science.gov (United States)

Moradabadi, Behnaz; Meybodi, Mohammad Reza

2018-02-01

This paper proposes a new cellular learning automaton, called a wavefront cellular learning automaton (WCLA). The proposed WCLA has a set of learning automata mapped to a connected structure and uses this structure to propagate the state changes of the learning automata over the structure using waves. In the WCLA, after one learning automaton chooses its action, if this chosen action is different from the previous action, it can send a wave to its neighbors and activate them. Each neighbor receiving the wave is activated and must choose a new action. This structure for the WCLA is necessary in many dynamic areas such as social networks, computer networks, grid computing, and web mining. In this paper, we introduce the WCLA framework as an optimization tool with diffusion capability, study its behavior over time using ordinary differential equation solutions, and present its accuracy using expediency analysis. To show the superiority of the proposed WCLA, we compare the proposed method with some other types of cellular learning automata using two benchmark problems.

Wavefront cellular learning automata

Science.gov (United States)

Moradabadi, Behnaz; Meybodi, Mohammad Reza

2018-02-01

This paper proposes a new cellular learning automaton, called a wavefront cellular learning automaton (WCLA). The proposed WCLA has a set of learning automata mapped to a connected structure and uses this structure to propagate the state changes of the learning automata over the structure using waves. In the WCLA, after one learning automaton chooses its action, if this chosen action is different from the previous action, it can send a wave to its neighbors and activate them. Each neighbor receiving the wave is activated and must choose a new action. This structure for the WCLA is necessary in many dynamic areas such as social networks, computer networks, grid computing, and web mining. In this paper, we introduce the WCLA framework as an optimization tool with diffusion capability, study its behavior over time using ordinary differential equation solutions, and present its accuracy using expediency analysis. To show the superiority of the proposed WCLA, we compare the proposed method with some other types of cellular learning automata using two benchmark problems.

Change of Land Use/Cover in Tianjin City Based on the Markov and Cellular Automata Models

Directory of Open Access Journals (Sweden)

Ruci Wang

2017-05-01

Full Text Available In recent years, urban areas have been expanding rapidly in the world, especially in developing countries. With this rapid urban growth, several environmental and social problems have appeared. Better understanding of land use and land cover (LULC change will facilitate urban planning and constrain these potential problems. As one of the four municipalities in China, Tianjin has experienced rapid urbanization and such trend is expected to continue. Relying on remote sensing (RS and geographical information system (GIS tools, this study investigates LULC change in Tianjin city. First, we used RS to generate classification maps for 1995, 2005, and 2015. Then, simulation models were applied to evaluate the LULC changes. Analysis of the 1995, 2005, and 2015 LULC maps shows that more than 10% of the cropland areas were transformed into built-up areas. Finally, by employing the Markov model and cellular automata (CA model, the LULC in 2025 and 2035 were simulated and forecasted. Our analysis contributes to the understanding of the development process in the Tianjin area, which will facilitate future planning, as well as constraining the potential negative consequences brought by future LULC changes.

Cellular automata model for urban road traffic flow considering pedestrian crossing street

Science.gov (United States)

Zhao, Han-Tao; Yang, Shuo; Chen, Xiao-Xu

2016-11-01

In order to analyze the effect of pedestrians' crossing street on vehicle flows, we investigated traffic characteristics of vehicles and pedestrians. Based on that, rules of lane changing, acceleration, deceleration, randomization and update are modified. Then we established two urban two-lane cellular automata models of traffic flow, one of which is about sections with non-signalized crosswalk and the other is on uncontrolled sections with pedestrians crossing street at random. MATLAB is used for numerical simulation of the different traffic conditions; meanwhile space-time diagram and relational graphs of traffic flow parameters are generated and then comparatively analyzed. Simulation results indicate that when vehicle density is lower than around 25 vehs/(km lane), pedestrians have modest impact on traffic flow, whereas when vehicle density is higher than about 60 vehs/(km lane), traffic speed and volume will decrease significantly especially on sections with non-signal-controlled crosswalk. The results illustrate that the proposed models reconstruct the traffic flow's characteristic with the situation where there are pedestrians crossing and can provide some practical reference for urban traffic management.

Observability of Automata Networks: Fixed and Switching Cases.

Science.gov (United States)

Li, Rui; Hong, Yiguang; Wang, Xingyuan

2018-04-01

Automata networks are a class of fully discrete dynamical systems, which have received considerable interest in various different areas. This brief addresses the observability of automata networks and switched automata networks in a unified framework, and proposes simple necessary and sufficient conditions for observability. The results are achieved by employing methods from symbolic computation, and are suited for implementation using computer algebra systems. Several examples are presented to demonstrate the application of the results.

Mathematical Modeling and Pure Mathematics

Science.gov (United States)

Usiskin, Zalman

2015-01-01

Common situations, like planning air travel, can become grist for mathematical modeling and can promote the mathematical ideas of variables, formulas, algebraic expressions, functions, and statistics. The purpose of this article is to illustrate how the mathematical modeling that is present in everyday situations can be naturally embedded in…

PREFACE: Physics-Based Mathematical Models for Nanotechnology

Science.gov (United States)

Voon, Lok C. Lew Yan; Melnik, Roderick; Willatzen, Morten

2008-03-01

stain-resistant clothing, but with thousands more anticipated. The focus of this interdisciplinary workshop was on determining what kind of new theoretical and computational tools will be needed to advance the science and engineering of nanomaterials and nanostructures. Thanks to the stimulating environment of the BIRS, participants of the workshop had plenty of opportunity to exchange new ideas on one of the main topics of this workshop—physics-based mathematical models for the description of low-dimensional semiconductor nanostructures (LDSNs) that are becoming increasingly important in technological innovations. The main objective of the workshop was to bring together some of the world leading experts in the field from each of the key research communities working on different aspects of LDSNs in order to (a) summarize the state-of-the-art models and computational techniques for modeling LDSNs, (b) identify critical problems of major importance that require solution and prioritize them, (c) analyze feasibility of existing mathematical and computational methodologies for the solution of some such problems, and (d) use some of the workshop working sessions to explore promising approaches in addressing identified challenges. With the possibility of growing practically any shape and size of heterostructures, it becomes essential to understand the mathematical properties of quantum-confined structures including properties of bulk states, interface states, and surface states as a function of shape, size, and internal strain. This workshop put strong emphasis on discussions of the new mathematics needed in nanotechnology especially in relation to geometry and material-combination optimization of device properties such as electronic, optical, and magnetic properties. The problems that were addressed at this meeting are of immense importance in determining such quantum-mechanical properties and the group of invited participants covered very well all the relevant disciplines

Multi-Core Emptiness Checking of Timed Büchi Automata using Inclusion Abstraction

DEFF Research Database (Denmark)

Laarman, Alfons; Olesen, Mads Chr.; Dalsgaard, Andreas

2013-01-01

This paper contributes to the multi-core model checking of timed automata (TA) with respect to liveness properties, by investigating checking of TA Büchi emptiness under the very coarse inclusion abstraction or zone subsumption, an open problem in this field. We show that in general Büchi emptiness...... parallel LTL model checking algorithm for timed automata. The algorithms are implemented in LTSmin, and experimental evaluations show the effectiveness and scalability of both contributions: subsumption halves the number of states in the real-world FDDI case study, and the multi-core algorithm yields...

The implementation of multiple intelligences based teaching model to improve mathematical problem solving ability for student of junior high school

Science.gov (United States)

Fasni, Nurli; Fatimah, Siti; Yulanda, Syerli

2017-05-01

This research aims to achieve some purposes such as: to know whether mathematical problem solving ability of students who have learned mathematics using Multiple Intelligences based teaching model is higher than the student who have learned mathematics using cooperative learning; to know the improvement of the mathematical problem solving ability of the student who have learned mathematics using Multiple Intelligences based teaching model., to know the improvement of the mathematical problem solving ability of the student who have learned mathematics using cooperative learning; to know the attitude of the students to Multiple Intelligences based teaching model. The method employed here is quasi-experiment which is controlled by pre-test and post-test. The population of this research is all of VII grade in SMP Negeri 14 Bandung even-term 2013/2014, later on two classes of it were taken for the samples of this research. A class was taught using Multiple Intelligences based teaching model and the other one was taught using cooperative learning. The data of this research were gotten from the test in mathematical problem solving, scale questionnaire of the student attitudes, and observation. The results show the mathematical problem solving of the students who have learned mathematics using Multiple Intelligences based teaching model learning is higher than the student who have learned mathematics using cooperative learning, the mathematical problem solving ability of the student who have learned mathematics using cooperative learning and Multiple Intelligences based teaching model are in intermediate level, and the students showed the positive attitude in learning mathematics using Multiple Intelligences based teaching model. As for the recommendation for next author, Multiple Intelligences based teaching model can be tested on other subject and other ability.

Dualities for multi-state probabilistic cellular automata

International Nuclear Information System (INIS)

López, F Javier; Sanz, Gerardo; Sobottka, Marcelo

2008-01-01

In this paper a new form of duality for probabilistic cellular automata (PCA) is introduced. Using this duality, an ergodicity result for processes having a dual is proved. Also, conditions on the probabilities defining the evolution of the processes for the existence of a dual are provided. The results are applied to wide classes of PCA which include multi-opinion voter models, competition models and the Domany–Kinzel model

Mathematical Modelling Approach in Mathematics Education

Science.gov (United States)

Arseven, Ayla

2015-01-01

The topic of models and modeling has come to be important for science and mathematics education in recent years. The topic of "Modeling" topic is especially important for examinations such as PISA which is conducted at an international level and measures a student's success in mathematics. Mathematical modeling can be defined as using…

Modeling of the inhomogeneity of grain refinement during combined metal forming process by finite element and cellular automata methods

Energy Technology Data Exchange (ETDEWEB)

Majta, Janusz; Madej, Łukasz; Svyetlichnyy, Dmytro S.; Perzyński, Konrad; Kwiecień, Marcin, E-mail: mkwiecie@agh.edu.pl; Muszka, Krzysztof

2016-08-01

The potential of discrete cellular automata technique to predict the grain refinement in wires produced using combined metal forming process is presented and discussed within the paper. The developed combined metal forming process can be treated as one of the Severe Plastic Deformation (SPD) techniques that consists of three different modes of deformation: asymmetric drawing with bending, namely accumulated angular drawing (AAD), wire drawing (WD) and wire flattening (WF). To accurately replicate complex stress state both at macro and micro scales during subsequent deformations two stage modeling approach was used. First, the Finite Element Method (FEM), implemented in commercial ABAQUS software, was applied to simulate entire combined forming process at the macro scale level. Then, based on FEM results, the Cellular Automata (CA) method was applied for simulation of grain refinement at the microstructure level. Data transferred between FEM and CA methods included set of files with strain tensor components obtained from selected integration points in the macro scale model. As a result of CA simulation, detailed information on microstructure evolution during severe plastic deformation conditions was obtained, namely: changes of shape and sizes of modeled representative volume with imposed microstructure, changes of the number of grains, subgrains and dislocation cells, development of grain boundaries angle distribution as well as changes in the pole figures. To evaluate CA model predictive capabilities, results of computer simulation were compared with scanning electron microscopy and electron back scattered diffraction images (SEM/EBSD) studies of samples after AAD+WD+WF process.

Canalization and control in automata networks: body segmentation in Drosophila melanogaster.

Directory of Open Access Journals (Sweden)

Manuel Marques-Pita

Full Text Available We present schema redescription as a methodology to characterize canalization in automata networks used to model biochemical regulation and signalling. In our formulation, canalization becomes synonymous with redundancy present in the logic of automata. This results in straightforward measures to quantify canalization in an automaton (micro-level, which is in turn integrated into a highly scalable framework to characterize the collective dynamics of large-scale automata networks (macro-level. This way, our approach provides a method to link micro- to macro-level dynamics--a crux of complexity. Several new results ensue from this methodology: uncovering of dynamical modularity (modules in the dynamics rather than in the structure of networks, identification of minimal conditions and critical nodes to control the convergence to attractors, simulation of dynamical behaviour from incomplete information about initial conditions, and measures of macro-level canalization and robustness to perturbations. We exemplify our methodology with a well-known model of the intra- and inter cellular genetic regulation of body segmentation in Drosophila melanogaster. We use this model to show that our analysis does not contradict any previous findings. But we also obtain new knowledge about its behaviour: a better understanding of the size of its wild-type attractor basin (larger than previously thought, the identification of novel minimal conditions and critical nodes that control wild-type behaviour, and the resilience of these to stochastic interventions. Our methodology is applicable to any complex network that can be modelled using automata, but we focus on biochemical regulation and signalling, towards a better understanding of the (decentralized control that orchestrates cellular activity--with the ultimate goal of explaining how do cells and tissues 'compute'.

Canalization and control in automata networks: body segmentation in Drosophila melanogaster.

Science.gov (United States)

Marques-Pita, Manuel; Rocha, Luis M

2013-01-01

We present schema redescription as a methodology to characterize canalization in automata networks used to model biochemical regulation and signalling. In our formulation, canalization becomes synonymous with redundancy present in the logic of automata. This results in straightforward measures to quantify canalization in an automaton (micro-level), which is in turn integrated into a highly scalable framework to characterize the collective dynamics of large-scale automata networks (macro-level). This way, our approach provides a method to link micro- to macro-level dynamics--a crux of complexity. Several new results ensue from this methodology: uncovering of dynamical modularity (modules in the dynamics rather than in the structure of networks), identification of minimal conditions and critical nodes to control the convergence to attractors, simulation of dynamical behaviour from incomplete information about initial conditions, and measures of macro-level canalization and robustness to perturbations. We exemplify our methodology with a well-known model of the intra- and inter cellular genetic regulation of body segmentation in Drosophila melanogaster. We use this model to show that our analysis does not contradict any previous findings. But we also obtain new knowledge about its behaviour: a better understanding of the size of its wild-type attractor basin (larger than previously thought), the identification of novel minimal conditions and critical nodes that control wild-type behaviour, and the resilience of these to stochastic interventions. Our methodology is applicable to any complex network that can be modelled using automata, but we focus on biochemical regulation and signalling, towards a better understanding of the (decentralized) control that orchestrates cellular activity--with the ultimate goal of explaining how do cells and tissues 'compute'.

Random complex automata: Analogy with spin glasses

International Nuclear Information System (INIS)

Flyvbjerg, H.

1986-12-01

Ab initio properties of random networks of automata have been studied statistically. A strikingly high degree of similarity is demonstrated between the multivalley structure of the basins of attraction of Kauffman's model and that of infinite range spin glasses. Results from simulations as well as exact analytical results are presented. (orig.)

Hybrid automata models of cardiac ventricular electrophysiology for real-time computational applications.

Science.gov (United States)

Andalam, Sidharta; Ramanna, Harshavardhan; Malik, Avinash; Roop, Parthasarathi; Patel, Nitish; Trew, Mark L

2016-08-01

Virtual heart models have been proposed for closed loop validation of safety-critical embedded medical devices, such as pacemakers. These models must react in real-time to off-the-shelf medical devices. Real-time performance can be obtained by implementing models in computer hardware, and methods of compiling classes of Hybrid Automata (HA) onto FPGA have been developed. Models of ventricular cardiac cell electrophysiology have been described using HA which capture the complex nonlinear behavior of biological systems. However, many models that have been used for closed-loop validation of pacemakers are highly abstract and do not capture important characteristics of the dynamic rate response. We developed a new HA model of cardiac cells which captures dynamic behavior and we implemented the model in hardware. This potentially enables modeling the heart with over 1 million dynamic cells, making the approach ideal for closed loop testing of medical devices.

Discount-Optimal Infinite Runs in Priced Timed Automata

DEFF Research Database (Denmark)

Fahrenberg, Uli; Larsen, Kim Guldstrand

2009-01-01

We introduce a new discounting semantics for priced timed automata. Discounting provides a way to model optimal-cost problems for infinite traces and has applications in optimal scheduling and other areas. In the discounting semantics, prices decrease exponentially, so that the contribution...

Improving the Timed Automata Approach to Biological Pathway Dynamics

NARCIS (Netherlands)

Langerak, R.; Pol, Jaco van de; Post, Janine N.; Schivo, Stefano; Aceto, Luca; Bacci, Giorgio; Bacci, Giovanni; Ingólfsdóttir, Anna; Legay, Axel; Mardare, Radu

2017-01-01

Biological systems such as regulatory or gene networks can be seen as a particular type of distributed systems, and for this reason they can be modeled within the Timed Automata paradigm, which was developed in the computer science context. However, tools designed to model distributed systems often

Mathematical modelling

CERN Document Server

2016-01-01

This book provides a thorough introduction to the challenge of applying mathematics in real-world scenarios. Modelling tasks rarely involve well-defined categories, and they often require multidisciplinary input from mathematics, physics, computer sciences, or engineering. In keeping with this spirit of modelling, the book includes a wealth of cross-references between the chapters and frequently points to the real-world context. The book combines classical approaches to modelling with novel areas such as soft computing methods, inverse problems, and model uncertainty. Attention is also paid to the interaction between models, data and the use of mathematical software. The reader will find a broad selection of theoretical tools for practicing industrial mathematics, including the analysis of continuum models, probabilistic and discrete phenomena, and asymptotic and sensitivity analysis.

Information Flow for Timed Automata

DEFF Research Database (Denmark)

Nielson, Flemming; Nielson, Hanne Riis; Vasilikos, Panagiotis

2017-01-01

One of the key demands of cyberphysical systems is that they meet their safety goals. Timed Automata has established itself as a formalism for modelling and analysing the real-time safety aspects of cyberphysical systems. Increasingly it is also demanded that cyberphysical systems meet a number o...... of security goals for confidentiality and integrity. Information Flow Control is an approach to ensuring that there are no flows of information that violate the stated security policy....

Finite Action-Set Learning Automata for Economic Dispatch Considering Electric Vehicles and Renewable Energy Sources

Directory of Open Access Journals (Sweden)

Junpeng Zhu

2014-07-01

Full Text Available The coming interaction between a growing electrified vehicle fleet and the desired growth in renewable energy provides new insights into the economic dispatch (ED problem. This paper presents an economic dispatch model that considers electric vehicle charging, battery exchange stations, and wind farms. This ED model is a high-dimensional, non-linear, and stochastic problem and its solution requires powerful methods. A new finite action-set learning automata (FALA-based approach that has the ability to adapt to a stochastic environment is proposed. The feasibility of the proposed approach is demonstrated in a modified IEEE 30 bus system. It is compared with continuous action-set learning automata and particle swarm optimization-based approaches in terms of convergence characteristics, computational efficiency, and solution quality. Simulation results show that the proposed FALA-based approach was indeed capable of more efficiently obtaining the approximately optimal solution. In addition, by using an optimal dispatch schedule for the interaction between electric vehicle stations and power systems, it is possible to reduce the gap between demand and power generation at different times of the day.

Characterizing emergent properties of immunological systems with multi-cellular rule-based computational modeling.

Science.gov (United States)

Chavali, Arvind K; Gianchandani, Erwin P; Tung, Kenneth S; Lawrence, Michael B; Peirce, Shayn M; Papin, Jason A

2008-12-01

The immune system is comprised of numerous components that interact with one another to give rise to phenotypic behaviors that are sometimes unexpected. Agent-based modeling (ABM) and cellular automata (CA) belong to a class of discrete mathematical approaches in which autonomous entities detect local information and act over time according to logical rules. The power of this approach lies in the emergence of behavior that arises from interactions between agents, which would otherwise be impossible to know a priori. Recent work exploring the immune system with ABM and CA has revealed novel insights into immunological processes. Here, we summarize these applications to immunology and, particularly, how ABM can help formulate hypotheses that might drive further experimental investigations of disease mechanisms.

Modeling of the competition life cycle using the software complex of cellular automata PyCAlab

Science.gov (United States)

Berg, D. B.; Beklemishev, K. A.; Medvedev, A. N.; Medvedeva, M. A.

2015-11-01

The aim of the work is to develop a numerical model of the life cycle of competition on the basis of software complex cellular automata PyCAlab. The model is based on the general patterns of growth of various systems in resource-limited settings. At examples it is shown that the period of transition from an unlimited growth of the market agents to the stage of competitive growth takes quite a long time and may be characterized as monotonic. During this period two main strategies of competitive selection coexist: 1) capture of maximum market space with any reasonable costs; 2) saving by reducing costs. The obtained results allow concluding that the competitive strategies of companies must combine two mentioned types of behavior, and this issue needs to be given adequate attention in the academic literature on management. The created numerical model may be used for market research when developing of the strategies for promotion of new goods and services.

Developing a cellular automata model of urban growth to inform spatial policy for flood mitigation : A case study in Kampala, Uganda

NARCIS (Netherlands)

Pérez-Molina, Eduardo; Sliuzas, R.V.; Flacke, J.; Jetten, V.G.

2017-01-01

Urban growth may intensify local flooding problems. Understanding the spatially explicit flood consequences of possible future land cover patterns contributes to inform policy for mitigating these impacts. A cellular automata model has been coupled with the openLISEM integrated flood modeling tool

Soliton cellular automata associated with crystal bases

International Nuclear Information System (INIS)

Hatayama, Goro; Kuniba, Atsuo; Takagi, Taichiro

2000-01-01

We introduce a class of cellular automata associated with crystals of irreducible finite dimensional representations of quantum affine algebras U' q (g-circumflex n ). They have solitons labeled by crystals of the smaller algebra U' q (g-circumflex n-1 ). We prove stable propagation of one soliton for g-circumflex n =A (2) 2n-1 ,A (2) 2n ,B (1) n ,C (1) n ,D (1) n and D (2) n+1 . For g-circumflex n =C (1) n , we also prove that the scattering matrices of two solitons coincide with the combinatorial R matrices of U' q (C (1) n-1 )-crystals

Annual Perspectives in Mathematics Education 2016: Mathematical Modeling and Modeling Mathematics

Science.gov (United States)

Hirsch, Christian R., Ed.; McDuffie, Amy Roth, Ed.

2016-01-01

Mathematical modeling plays an increasingly important role both in real-life applications--in engineering, business, the social sciences, climate study, advanced design, and more--and within mathematics education itself. This 2016 volume of "Annual Perspectives in Mathematics Education" ("APME") focuses on this key topic from a…

Creating Clinical Fuzzy Automata with Fuzzy Arden Syntax.

Science.gov (United States)

de Bruin, Jeroen S; Steltzer, Heinz; Rappelsberger, Andrea; Adlassnig, Klaus-Peter

2017-01-01

Formal constructs for fuzzy sets and fuzzy logic are incorporated into Arden Syntax version 2.9 (Fuzzy Arden Syntax). With fuzzy sets, the relationships between measured or observed data and linguistic terms are expressed as degrees of compatibility that model the unsharpness of the boundaries of linguistic terms. Propositional uncertainty due to incomplete knowledge of relationships between clinical linguistic concepts is modeled with fuzzy logic. Fuzzy Arden Syntax also supports the construction of fuzzy state monitors. The latter are defined as monitors that employ fuzzy automata to observe gradual transitions between different stages of disease. As a use case, we re-implemented FuzzyARDS, a previously published clinical monitoring system for patients suffering from acute respiratory distress syndrome (ARDS). Using the re-implementation as an example, we show how key concepts of fuzzy automata, i.e., fuzzy states and parallel fuzzy state transitions, can be implemented in Fuzzy Arden Syntax. The results showed that fuzzy state monitors can be implemented in a straightforward manner.

Mathematic-Graphical Formalization of Switch Point Control Circuit Function

Directory of Open Access Journals (Sweden)

Juraj Zdansky

2004-01-01

Full Text Available This article describes authors designed method then enables mathematic – graphical formalization of system’s functional specification. The result of this method is algebraic system – finite automata that is written in transition table. This transition table is possible to overwrite to graphic form (state diagram or to mathematic form (transition and output function. This method is described by example of switch point control circuit.

Optimal Conditional Reachability for Multi-Priced Timed Automata

DEFF Research Database (Denmark)

Larsen, Kim Guldstrand; Rasmussen, Jacob Illum

2005-01-01

In this paper, we prove decidability of the optimal conditional reachability problem for multi-priced timed automata, an extension of timed automata with multiple cost variables evolving according to given rates for each location. More precisely, we consider the problem of determining the minimal...

Field validation of a free-agent cellular automata model of fire spread with fire–atmosphere coupling

Science.gov (United States)

Gary Achtemeier

2012-01-01

A cellular automata fire model represents ‘elements’ of fire by autonomous agents. A few simple algebraic expressions substituted for complex physical and meteorological processes and solved iteratively yield simulations for ‘super-diffusive’ fire spread and coupled surface-layer (2-m) fire–atmosphere processes. Pressure anomalies, which are integrals of the thermal...

AUTOMATA PROGRAMS CONSTRUCTION FROM SPECIFICATION WITH AN ANT COLONY OPTIMIZATION ALGORITHM BASED ON MUTATION GRAPH

Directory of Open Access Journals (Sweden)

Daniil S. Chivilikhin

2014-11-01

Full Text Available The procedure of testing traditionally used in software engineering cannot guarantee program correctness; therefore verification is used at the excess requirements to programs reliability. Verification makes it possible to check certain properties of programs in all possible computational states; however, this process is very complex. In the model checking method a model of the program is built (often, manually and requirements in terms of temporal logic are formulated. Such temporal properties of the model can be checked automatically. The main issue in this framework is the gap between the program and its model. Automata-based programming paradigm gives the possibility to overcome this limitation. In this paradigm, program logic is represented using finite-state machines. The advantage of finite-state machines is that their models can be constructed automatically. The paper deals with the application of mutation-based ant colony optimization algorithm to the problem of finite-state machine construction from their specification, defined by test scenarios and temporal properties. The presented approach has been tested on the elevator doors control problem as well as on randomly generated data. Obtained results show the ant colony algorithm is two-three times faster than the previously used genetic algorithm. The proposed approach can be recommended for inferring control programs for critical systems.

Cellular-automata-based learning network for pattern recognition

Science.gov (United States)

Tzionas, Panagiotis G.; Tsalides, Phillippos G.; Thanailakis, Adonios

1991-11-01

Most classification techniques either adopt an approach based directly on the statistical characteristics of the pattern classes involved, or they transform the patterns in a feature space and try to separate the point clusters in this space. An alternative approach based on memory networks has been presented, its novelty being that it can be implemented in parallel and it utilizes direct features of the patterns rather than statistical characteristics. This study presents a new approach for pattern classification using pseudo 2-D binary cellular automata (CA). This approach resembles the memory network classifier in the sense that it is based on an adaptive knowledge based formed during a training phase, and also in the fact that both methods utilize pattern features that are directly available. The main advantage of this approach is that the sensitivity of the pattern classifier can be controlled. The proposed pattern classifier has been designed using 1.5 micrometers design rules for an N-well CMOS process. Layout has been achieved using SOLO 1400. Binary pseudo 2-D hybrid additive CA (HACA) is described in the second section of this paper. The third section describes the operation of the pattern classifier and the fourth section presents some possible applications. The VLSI implementation of the pattern classifier is presented in the fifth section and, finally, the sixth section draws conclusions from the results obtained.

An Efficient Translation of Timed-Arc Petri Nets to Networks of Timed Automata

DEFF Research Database (Denmark)

Byg, Joakim; Jørgensen, Kenneth Yrke; Srba, Jiri

2009-01-01

Bounded timed-arc Petri nets with read-arcs were recently proven equivalent to networks of timed automata, though the Petri net model cannot express urgent behaviour and the described mutual trans- lations are rather inefficient. We propose an extension of timed-arc Petri nets with invariants...... to enforce urgency and with transport arcs to generalise the read-arcs. We also describe a novel translation from the extended timed-arc Petri net model to networks of timed automata. The translation is implemented in the tool TAPAAL and it uses UPPAAL as the verification engine. Our experiments confirm...... the efficiency of the translation and in some cases the translated models verify significantly faster than the native UPPAAL models do....

Parallel Implementation of Triangular Cellular Automata for Computing Two-Dimensional Elastodynamic Response on Arbitrary Domains

Science.gov (United States)

Leamy, Michael J.; Springer, Adam C.

In this research we report parallel implementation of a Cellular Automata-based simulation tool for computing elastodynamic response on complex, two-dimensional domains. Elastodynamic simulation using Cellular Automata (CA) has recently been presented as an alternative, inherently object-oriented technique for accurately and efficiently computing linear and nonlinear wave propagation in arbitrarily-shaped geometries. The local, autonomous nature of the method should lead to straight-forward and efficient parallelization. We address this notion on symmetric multiprocessor (SMP) hardware using a Java-based object-oriented CA code implementing triangular state machines (i.e., automata) and the MPI bindings written in Java (MPJ Express). We use MPJ Express to reconfigure our existing CA code to distribute a domain's automata to cores present on a dual quad-core shared-memory system (eight total processors). We note that this message passing parallelization strategy is directly applicable to computer clustered computing, which will be the focus of follow-on research. Results on the shared memory platform indicate nearly-ideal, linear speed-up. We conclude that the CA-based elastodynamic simulator is easily configured to run in parallel, and yields excellent speed-up on SMP hardware.

Cyclic cellular automata in 3D

International Nuclear Information System (INIS)

Reiter, Clifford A.

2011-01-01

Highlights: → We explore the self-organization of cyclic cellular automata in 3D. → Von Neumann, Moore and two types of intermediate neighborhoods are investigated. → Random neighborhoods self organize through phases into complex nested structures. → Demons are seen to have many alternatives in 3D. - Abstract: Cyclic cellular automata in two dimensions have long been intriguing because they self organize into spirals and that behavior can be analyzed. The form for the patterns that develop is highly dependent upon the form of the neighborhood. We extend this work to three dimensional cyclic cellular automata and observe self organization dependent upon the neighborhood type. This includes neighborhood types intermediate between Von Neumann and Moore neighborhoods. We also observe that the patterns include nested shells with the appropriate forms but that the nesting is far more complex than the spirals that occur in two dimensions.

Unifying Model-Based and Reactive Programming within a Model-Based Executive

Science.gov (United States)

Williams, Brian C.; Gupta, Vineet; Norvig, Peter (Technical Monitor)

1999-01-01

Real-time, model-based, deduction has recently emerged as a vital component in AI's tool box for developing highly autonomous reactive systems. Yet one of the current hurdles towards developing model-based reactive systems is the number of methods simultaneously employed, and their corresponding melange of programming and modeling languages. This paper offers an important step towards unification. We introduce RMPL, a rich modeling language that combines probabilistic, constraint-based modeling with reactive programming constructs, while offering a simple semantics in terms of hidden state Markov processes. We introduce probabilistic, hierarchical constraint automata (PHCA), which allow Markov processes to be expressed in a compact representation that preserves the modularity of RMPL programs. Finally, a model-based executive, called Reactive Burton is described that exploits this compact encoding to perform efficIent simulation, belief state update and control sequence generation.

Cellular automaton modeling of biological pattern formation characterization, examples, and analysis

CERN Document Server

Deutsch, Andreas

2017-01-01

This text explores the use of cellular automata in modeling pattern formation in biological systems. It describes several mathematical modeling approaches utilizing cellular automata that can be used to study the dynamics of interacting cell systems both in simulation and in practice. New in this edition are chapters covering cell migration, tissue development, and cancer dynamics, as well as updated references and new research topic suggestions that reflect the rapid development of the field. The book begins with an introduction to pattern-forming principles in biology and the various mathematical modeling techniques that can be used to analyze them. Cellular automaton models are then discussed in detail for different types of cellular processes and interactions, including random movement, cell migration, adhesive cell interaction, alignment and cellular swarming, growth processes, pigment cell pattern formation, tissue development, tumor growth and invasion, and Turing-type patterns and excitable media. In ...

The sensitivity research of multiparameter biosensors based on HEMT by the mathematic modeling method

Science.gov (United States)

Tikhomirov, V. G.; Gudkov, A. G.; Agasieva, S. V.; Gorlacheva, E. N.; Shashurin, V. D.; Zybin, A. A.; Evseenkov, A. S.; Parnes, Y. M.

2017-11-01

The numerical impact modeling of some external effects on the CVC of biosensors based on AlGaN/GaN heterostructures (HEMT) was carried out. The mathematical model was created that allowed to predict the behavior of the drain current depending on condition changes on the heterostructure surface in the gate region and to start the process of directed construction optimization of the biosensors based on AlGaN/GaN HEMT with the aim of improving their performance. The calculation of the drain current of the biosensor construction was carried out to confirm the reliability of the developed mathematical model and obtained results.

Spatiotemporal Simulation of Tourist Town Growth Based on the Cellular Automata Model: The Case of Sanpo Town in Hebei Province

Directory of Open Access Journals (Sweden)

Jun Yang

2013-01-01

Full Text Available Spatiotemporal simulation of tourist town growth is important for research on land use/cover change under the influence of urbanization. Many scholars have shown great interest in the unique pattern of driving urban development with tourism development. Based on the cellular automata (CA model, we simulated and predicted the spatiotemporal growth of Sanpo town in Hebei Province, using the tourism urbanization growth model. Results showed that (1 average annual growth rate of the entire region was 1.5 Ha2 per year from 2005 to 2010, 4 Ha2 per year from 2010 to 2015, and 2.5 Ha2 per year from 2015 to 2020; (2 urban growth rate increased yearly, with regional differences, and had a high degree of correlation with the Euclidean distance of town center, traffic route, attractions, and other factors; (3 Gougezhuang, an important village center in the west of the town, demonstrated traffic advantages and increased growth rate since 2010; (4 Magezhuang village has the largest population in the region, so economic advantages have driven the development of rural urbanization. It showed that CA had high reliability in simulating the spatiotemporal evolution of tourist town, which assists the study of spatiotemporal growth under urbanization and rational protection of tourism resources.

Stochastic modeling for dynamics of HIV-1 infection using cellular automata: A review.

Science.gov (United States)

Precharattana, Monamorn

2016-02-01

Recently, the description of immune response by discrete models has emerged to play an important role to study the problems in the area of human immunodeficiency virus type 1 (HIV-1) infection, leading to AIDS. As infection of target immune cells by HIV-1 mainly takes place in the lymphoid tissue, cellular automata (CA) models thus represent a significant step in understanding when the infected population is dispersed. Motivated by these, the studies of the dynamics of HIV-1 infection using CA in memory have been presented to recognize how CA have been developed for HIV-1 dynamics, which issues have been studied already and which issues still are objectives in future studies.

A novel image encryption algorithm using chaos and reversible cellular automata

Science.gov (United States)

Wang, Xingyuan; Luan, Dapeng

2013-11-01

In this paper, a novel image encryption scheme is proposed based on reversible cellular automata (RCA) combining chaos. In this algorithm, an intertwining logistic map with complex behavior and periodic boundary reversible cellular automata are used. We split each pixel of image into units of 4 bits, then adopt pseudorandom key stream generated by the intertwining logistic map to permute these units in confusion stage. And in diffusion stage, two-dimensional reversible cellular automata which are discrete dynamical systems are applied to iterate many rounds to achieve diffusion on bit-level, in which we only consider the higher 4 bits in a pixel because the higher 4 bits carry almost the information of an image. Theoretical analysis and experimental results demonstrate the proposed algorithm achieves a high security level and processes good performance against common attacks like differential attack and statistical attack. This algorithm belongs to the class of symmetric systems.

Cellular Automata Modelling of Photo-Induced Oxidation Processes in Molecularly Doped Polymers

Directory of Open Access Journals (Sweden)

David M. Goldie

2016-11-01

Full Text Available The possibility of employing cellular automata (CA to model photo-induced oxidation processes in molecularly doped polymers is explored. It is demonstrated that the oxidation dynamics generated using CA models exhibit stretched-exponential behavior. This dynamical characteristic is in general agreement with an alternative analysis conducted using standard rate equations provided the molecular doping levels are sufficiently low to prohibit the presence of safe-sites which are impenetrable to dissolved oxygen. The CA models therefore offer the advantage of exploring the effect of dopant agglomeration which is difficult to assess from standard rate equation solutions. The influence of UV-induced bleaching or darkening upon the resulting oxidation dynamics may also be easily incorporated into the CA models and these optical effects are investigated for various photo-oxidation product scenarios. Output from the CA models is evaluated for experimental photo-oxidation data obtained from a series of hydrazone-doped polymers.

Hierarchy among Automata on Linear Orderings

OpenAIRE

Bruyère , Véronique; Carton , Olivier

2005-01-01

In a preceding paper, automata and rational expressions have been introduced for words indexed by linear orderings, together with a Kleene-like theorem. We here pursue this work by proposing a hierarchy among the rational sets. Each class of the hierarchy is defined by a subset of the rational operations that can be used. We then characterize any class by an appropriate class of automata, leading to a Kleene theorem inside the class. A characterization by particular classes of orderings is al...

Mathematical modeling

CERN Document Server

Eck, Christof; Knabner, Peter

2017-01-01

Mathematical models are the decisive tool to explain and predict phenomena in the natural and engineering sciences. With this book readers will learn to derive mathematical models which help to understand real world phenomena. At the same time a wealth of important examples for the abstract concepts treated in the curriculum of mathematics degrees are given. An essential feature of this book is that mathematical structures are used as an ordering principle and not the fields of application. Methods from linear algebra, analysis and the theory of ordinary and partial differential equations are thoroughly introduced and applied in the modeling process. Examples of applications in the fields electrical networks, chemical reaction dynamics, population dynamics, fluid dynamics, elasticity theory and crystal growth are treated comprehensively.

Operational State Complexity of Deterministic Unranked Tree Automata

Directory of Open Access Journals (Sweden)

Xiaoxue Piao

2010-08-01

Full Text Available We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper and lower bounds of both weakly and strongly deterministic tree automata are obtained. For tree concatenation we establish a tight upper bound that is of a different order than the known state complexity of concatenation of regular string languages. We show that (n+1 ( (m+12^n-2^(n-1 -1 vertical states are sufficient, and necessary in the worst case, to recognize the concatenation of tree languages recognized by (strongly or weakly deterministic automata with, respectively, m and n vertical states.

Entropies of the automata networks with additive rule

Institute of Scientific and Technical Information of China (English)

Guo－qingGU; GeCHEN; 等

1996-01-01

The matrix presentation for automata networks with additive rule are described.A set of entropy theorems of additive automata network are proved and an analytic formula of its entropy is built.For example,we proved that the topological entropy is identically equal to metric entropy for an additive antomata network.

Quantum mechanics of lattice gas automata: One-particle plane waves and potentials

International Nuclear Information System (INIS)

Meyer, D.A.

1997-01-01

Classical lattice gas automata effectively simulate physical processes, such as diffusion and fluid flow (in certain parameter regimes), despite their simplicity at the microscale. Motivated by current interest in quantum computation we recently defined quantum lattice gas automata; in this paper we initiate a project to analyze which physical processes these models can effectively simulate. Studying the single particle sector of a one-dimensional quantum lattice gas we find discrete analogs of plane waves and wave packets, and then investigate their behavior in the presence of inhomogeneous potentials. copyright 1997 The American Physical Society

Mathematical modelling of two-phase flows

International Nuclear Information System (INIS)

Komen, E.M.J.; Stoop, P.M.

1992-11-01

A gradual shift from methods based on experimental correlations to methods based on mathematical models to study 2-phase flows can be observed. The latter can be used to predict dynamical behaviour of 2-phase flows. This report discusses various mathematical models for the description of 2-phase flows. An important application of these models can be found in thermal-hydraulic computer codes used for analysis of the thermal-hydraulic behaviour of water cooled nuclear power plants. (author). 17 refs., 7 figs., 6 tabs

Designing of Holistic Mathematic Education Model Based-"System Among" at Low Grade Elementary School

Science.gov (United States)

Hayati, R.; Fauzan, A.; Iswari, M.; Khaidir, A.

2018-04-01

The purpose of this study was to develop a model of Holistic Mathematics Education (HME) among systems based on low-grade primary school students so that students have a solid foundation when entering a higher behavior. This type of research is desaign research developed by Plomp to have three stages, namely the preliminary research, development or prototyping phase, and assessement Phase. This research resulted in a model Holistic Mathematics Education (HME) -based system is among the primary school students low grade consists of 10 stages, namely 1) Recap through the neighborhood, 2) Discussion groups by exploiting the environment, 3) Demonstration Group, 4) Exercise individuals, 5) mathematical modeling, 6) Demonstration of individuals, 7) Reflections, 8) impressions and messages, and giving meaning, 9) Celebrations and 10) A thorough assessment. Furthermore, this model also produces 7 important components that should be developed teacher, namely 1) constructivism, 2) the nature of nature, 3) independence, 4) parable, 5) inquiry, 6) cooperation, and 7) strengthening. This model will produce a model in the form of books, student books and teacher's guide book as a support system that can help users in its application.

Basic Ideas to Approach Metastability in Probabilistic Cellular Automata

NARCIS (Netherlands)

Cirillo, Emilio N. M.; Nardi, Francesca R.; Spitoni, Cristian

2016-01-01

Cellular Automata are discrete--time dynamical systems on a spatially extended discrete space which provide paradigmatic examples of nonlinear phenomena. Their stochastic generalizations, i.e., Probabilistic Cellular Automata, are discrete time Markov chains on lattice with finite single--cell

Density-conserving affine continuous cellular automata solving the relaxed density classification problem

International Nuclear Information System (INIS)

Wolnik, Barbara; Dembowski, Marcin; Bołt, Witold; Baetens, Jan M; De Baets, Bernard

2017-01-01

The focus of this paper is on the density classification problem in the context of affine continuous cellular automata. Although such cellular automata cannot solve this problem in the classical sense, most density-conserving affine continuous cellular automata with a unit neighborhood radius are valid solutions of a slightly relaxed version of this problem. This result follows from a detailed study of the dynamics of the density-conserving affine continuous cellular automata that we introduce. (paper)

Importance Sampling for Stochastic Timed Automata

DEFF Research Database (Denmark)

Jegourel, Cyrille; Larsen, Kim Guldstrand; Legay, Axel

2016-01-01

We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise cha......We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state...

Conceptualising inquiry based education in mathematics

DEFF Research Database (Denmark)

Blomhøj, Morten; Artigue, Michéle

2013-01-01

of inquiry as a pedagogical concept in the work of Dewey (e.g. 1916, 1938) to analyse and discuss its migration to science and mathematics education. For conceptualizing inquiry-based mathematics education (IBME) it is important to analyse how this concept resonates with already well-established theoretical...... frameworks in mathematics education. Six such frameworks are analysed from the perspective of inquiry: the problem-solving tradition, the Theory of Didactical Situations, the Realistic Mathematics Education programme, the mathematical modelling perspective, the Anthropological Theory of Didactics...

Effect of asynchronous updating on the stability of cellular automata

International Nuclear Information System (INIS)

Baetens, J.M.; Van der Weeën, P.; De Baets, B.

2012-01-01

Highlights: ► An upper bound on the Lyapunov exponent of asynchronously updated CA is established. ► The employed update method has repercussions on the stability of CAs. ► A decision on the employed update method should be taken with care. ► Substantial discrepancies arise between synchronously and asynchronously updated CA. ► Discrepancies between different asynchronous update schemes are less pronounced. - Abstract: Although cellular automata (CAs) were conceptualized as utter discrete mathematical models in which the states of all their spatial entities are updated simultaneously at every consecutive time step, i.e. synchronously, various CA-based models that rely on so-called asynchronous update methods have been constructed in order to overcome the limitations that are tied up with the classical way of evolving CAs. So far, only a few researchers have addressed the consequences of this way of updating on the evolved spatio-temporal patterns, and the reachable stationary states. In this paper, we exploit Lyapunov exponents to determine to what extent the stability of the rules within a family of totalistic CAs is affected by the underlying update method. For that purpose, we derive an upper bound on the maximum Lyapunov exponent of asynchronously iterated CAs, and show its validity, after which we present a comparative study between the Lyapunov exponents obtained for five different update methods, namely one synchronous method and four well-established asynchronous methods. It is found that the stability of CAs is seriously affected if one of the latter methods is employed, whereas the discrepancies arising between the different asynchronous methods are far less pronounced and, finally, we discuss the repercussions of our findings on the development of CA-based models.

Pre-Service Teachers' Developing Conceptions about the Nature and Pedagogy of Mathematical Modeling in the Context of a Mathematical Modeling Course

Science.gov (United States)

Cetinkaya, Bulent; Kertil, Mahmut; Erbas, Ayhan Kursat; Korkmaz, Himmet; Alacaci, Cengiz; Cakiroglu, Erdinc

2016-01-01

Adopting a multitiered design-based research perspective, this study examines pre-service secondary mathematics teachers' developing conceptions about (a) the nature of mathematical modeling in simulations of "real life" problem solving, and (b) pedagogical principles and strategies needed to teach mathematics through modeling. Unlike…

Surjective cellular automata with zero entropy are almost one-to-one

International Nuclear Information System (INIS)

Moothathu, T.K.S.

2011-01-01

Highlights: → We use information about maps with zero entropy from Ergodic Theory. → Surjective cellular automata with zero entropy are almost one-to-one. → Surjective, additive cellular automata with zero entropy are injective. - Abstract: We show that any one-dimensional surjective cellular automata whose entropy is zero with respect to the uniform Bernoulli measure must be almost one-to-one.

Teaching Mathematical Modeling in Mathematics Education

Science.gov (United States)

Saxena, Ritu; Shrivastava, Keerty; Bhardwaj, Ramakant

2016-01-01

Mathematics is not only a subject but it is also a language consisting of many different symbols and relations. Taught as a compulsory subject up the 10th class, students are then able to choose whether or not to study mathematics as a main subject. The present paper discusses mathematical modeling in mathematics education. The article provides…

Cellular Automata in Topology Optimization of Continuum Structures ...

African Journals Online (AJOL)

In this paper, an optimization algorithm based on cellular automata (CA) is developed for topology optimization of continuum structures with shear and flexural behavior. The design domain is divided into small triangle elements and each cell is considered as a finite element. The stress analysis is performed by the Constant ...

Irreversibility and dissipation in finite-state automata

International Nuclear Information System (INIS)

Ganesh, Natesh; Anderson, Neal G.

2013-01-01

Irreversibility and dissipation in finite-state automata (FSA) are considered from a physical-information-theoretic perspective. A quantitative measure for the computational irreversibility of finite automata is introduced, and a fundamental lower bound on the average energy dissipated per state transition is obtained and expressed in terms of FSA irreversibility. The irreversibility measure and energy bound are germane to any realization of a deterministic automaton that faithfully registers abstract FSA states in distinguishable states of a physical system coupled to a thermal environment, and that evolves via a sequence of interactions with an external system holding a physical instantiation of a random input string. The central result, which is shown to follow from quantum dynamics and entropic inequalities alone, can be regarded as a generalization of Landauer's Principle applicable to FSAs and tailorable to specified automata. Application to a simple FSA is illustrated.

Resource-Optimal Scheduling Using Priced Timed Automata

DEFF Research Database (Denmark)

Larsen, Kim Guldstrand; Rasmussen, Jacob Illum; Subramani, K.

2004-01-01

In this paper, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata can be exploited in order to substantially improve the performance of the current algorithm. The idea is rooted in duality of linear......-80 percent performance gain. As a main application area, we show how to solve energy-optimal task graph scheduling problems using the framework of priced timed automata....

Control of Petri Nets by finite automata

Energy Technology Data Exchange (ETDEWEB)

Burkhard, H D

1983-01-01

Petri Nets are considered where the firings are controlled by finite automata. The control may be distributed to various automata working over disjoint sets of transitions. To avoid deadlocks and conflicts for the whole system the distribution of control must be organised in an appropriate manner. The existence of deadlocks and conflicts is shown to be undecidable in general, but conflict resolving and deadlock free controls can be constructed for given nets. 10 references.

Motion Planning in Multi-robot Systems using Timed Automata

DEFF Research Database (Denmark)

Andersen, Michael. S.; Jensen, Rune S.; Bak, Thomas

This paper dscribes how interacting timed automata can be used to model, analyze, and verify motion planning problems for systems with multiple mobile robots. The method assumes an infra-structure of simple unicycle type robots, moving om a planar grid. The motion of the robots, including simple...... kinematics, is captured in an automata formalism that allows formal composition and symbolic reasoning. The verification software UppAal is used to verify specification requirements formulated in computational tree logic (CTL), generating all feasible trajectories that satisfy specifications. The results...... of the planning are demonstrateted in a testbed that allows execution of the planned paths and motion primitives by synchronizing the planning results from UppAal with actual robotic vehicles. The planning problem may be modified online by moving obstacles in the physical environment, which causes a re...

Data-based mathematical modeling of vectorial transport across double-transfected polarized cells.

Science.gov (United States)

Bartholomé, Kilian; Rius, Maria; Letschert, Katrin; Keller, Daniela; Timmer, Jens; Keppler, Dietrich

2007-09-01

Vectorial transport of endogenous small molecules, toxins, and drugs across polarized epithelial cells contributes to their half-life in the organism and to detoxification. To study vectorial transport in a quantitative manner, an in vitro model was used that includes polarized MDCKII cells stably expressing the recombinant human uptake transporter OATP1B3 in their basolateral membrane and the recombinant ATP-driven efflux pump ABCC2 in their apical membrane. These double-transfected cells enabled mathematical modeling of the vectorial transport of the anionic prototype substance bromosulfophthalein (BSP) that has frequently been used to examine hepatobiliary transport. Time-dependent analyses of (3)H-labeled BSP in the basolateral, intracellular, and apical compartments of cells cultured on filter membranes and efflux experiments in cells preloaded with BSP were performed. A mathematical model was fitted to the experimental data. Data-based modeling was optimized by including endogenous transport processes in addition to the recombinant transport proteins. The predominant contributions to the overall vectorial transport of BSP were mediated by OATP1B3 (44%) and ABCC2 (28%). Model comparison predicted a previously unrecognized endogenous basolateral efflux process as a negative contribution to total vectorial transport, amounting to 19%, which is in line with the detection of the basolateral efflux pump Abcc4 in MDCKII cells. Rate-determining steps in the vectorial transport were identified by calculating control coefficients. Data-based mathematical modeling of vectorial transport of BSP as a model substance resulted in a quantitative description of this process and its components. The same systems biology approach may be applied to other cellular systems and to different substances.

Cellular automata model for traffic flow with safe driving conditions

International Nuclear Information System (INIS)

Lárraga María Elena; Alvarez-Icaza Luis

2014-01-01

In this paper, a recently introduced cellular automata (CA) model is used for a statistical analysis of the inner microscopic structure of synchronized traffic flow. The analysis focuses on the formation and dissolution of clusters or platoons of vehicles, as the mechanism that causes the presence of this synchronized traffic state with a high flow. This platoon formation is one of the most interesting phenomena observed in traffic flows and plays an important role both in manual and automated highway systems (AHS). Simulation results, obtained from a single-lane system under periodic boundary conditions indicate that in the density region where the synchronized state is observed, most vehicles travel together in platoons with approximately the same speed and small spatial distances. The examination of velocity variations and individual vehicle gaps shows that the flow corresponding to the synchronized state is stable, safe and highly correlated. Moreover, results indicate that the observed platoon formation in real traffic is reproduced in simulations by the relation between vehicle headway and velocity that is embedded in the dynamics definition of the CA model. (general)

Teaching mathematical modelling through project work

DEFF Research Database (Denmark)

Blomhøj, Morten; Kjeldsen, Tinne Hoff

2006-01-01

are reported in manners suitable for internet publication for colleagues. The reports and the related discussions reveal interesting dilemmas concerning the teaching of mathematical modelling and how to cope with these through “setting the scene” for the students modelling projects and through dialogues......The paper presents and analyses experiences from developing and running an in-service course in project work and mathematical modelling for mathematics teachers in the Danish gymnasium, e.g. upper secondary level, grade 10-12. The course objective is to support the teachers to develop, try out...... in their own classes, evaluate and report a project based problem oriented course in mathematical modelling. The in-service course runs over one semester and includes three seminars of 3, 1 and 2 days. Experiences show that the course objectives in general are fulfilled and that the course projects...

Comparison of learning models based on mathematics logical intelligence in affective domain

Science.gov (United States)

Widayanto, Arif; Pratiwi, Hasih; Mardiyana

2018-04-01

The purpose of this study was to examine the presence or absence of different effects of multiple treatments (used learning models and logical-mathematical intelligence) on the dependent variable (affective domain of mathematics). This research was quasi experimental using 3x3 of factorial design. The population of this research was VIII grade students of junior high school in Karanganyar under the academic year 2017/2018. Data collected in this research was analyzed by two ways analysis of variance with unequal cells using 5% of significance level. The result of the research were as follows: (1) Teaching and learning with model TS lead to better achievement in affective domain than QSH, teaching and learning with model QSH lead to better achievement in affective domain than using DI; (2) Students with high mathematics logical intelligence have better achievement in affective domain than students with low mathematics logical intelligence have; (3) In teaching and learning mathematics using learning model TS, students with moderate mathematics logical intelligence have better achievement in affective domain than using DI; and (4) In teaching and learning mathematics using learning model TS, students with low mathematics logical intelligence have better achievement in affective domain than using QSH and DI.

Mathematical modelling techniques

CERN Document Server

Aris, Rutherford

1995-01-01

""Engaging, elegantly written."" - Applied Mathematical ModellingMathematical modelling is a highly useful methodology designed to enable mathematicians, physicists and other scientists to formulate equations from a given nonmathematical situation. In this elegantly written volume, a distinguished theoretical chemist and engineer sets down helpful rules not only for setting up models but also for solving the mathematical problems they pose and for evaluating models.The author begins with a discussion of the term ""model,"" followed by clearly presented examples of the different types of mode

Using Mathematics, Mathematical Applications, Mathematical Modelling, and Mathematical Literacy: A Theoretical Study

Science.gov (United States)

Mumcu, Hayal Yavuz

2016-01-01

The purpose of this theoretical study is to explore the relationships between the concepts of using mathematics in the daily life, mathematical applications, mathematical modelling, and mathematical literacy. As these concepts are generally taken as independent concepts in the related literature, they are confused with each other and it becomes…

Mathematical Biology Modules Based on Modern Molecular Biology and Modern Discrete Mathematics

Science.gov (United States)

Davies, Robin; Hodge, Terrell; Enyedi, Alexander

2010-01-01

We describe an ongoing collaborative curriculum materials development project between Sweet Briar College and Western Michigan University, with support from the National Science Foundation. We present a collection of modules under development that can be used in existing mathematics and biology courses, and we address a critical national need to introduce students to mathematical methods beyond the interface of biology with calculus. Based on ongoing research, and designed to use the project-based-learning approach, the modules highlight applications of modern discrete mathematics and algebraic statistics to pressing problems in molecular biology. For the majority of projects, calculus is not a required prerequisite and, due to the modest amount of mathematical background needed for some of the modules, the materials can be used for an early introduction to mathematical modeling. At the same time, most modules are connected with topics in linear and abstract algebra, algebraic geometry, and probability, and they can be used as meaningful applied introductions into the relevant advanced-level mathematics courses. Open-source software is used to facilitate the relevant computations. As a detailed example, we outline a module that focuses on Boolean models of the lac operon network. PMID:20810955

Mathematical biology modules based on modern molecular biology and modern discrete mathematics.

Science.gov (United States)

Robeva, Raina; Davies, Robin; Hodge, Terrell; Enyedi, Alexander

2010-01-01

We describe an ongoing collaborative curriculum materials development project between Sweet Briar College and Western Michigan University, with support from the National Science Foundation. We present a collection of modules under development that can be used in existing mathematics and biology courses, and we address a critical national need to introduce students to mathematical methods beyond the interface of biology with calculus. Based on ongoing research, and designed to use the project-based-learning approach, the modules highlight applications of modern discrete mathematics and algebraic statistics to pressing problems in molecular biology. For the majority of projects, calculus is not a required prerequisite and, due to the modest amount of mathematical background needed for some of the modules, the materials can be used for an early introduction to mathematical modeling. At the same time, most modules are connected with topics in linear and abstract algebra, algebraic geometry, and probability, and they can be used as meaningful applied introductions into the relevant advanced-level mathematics courses. Open-source software is used to facilitate the relevant computations. As a detailed example, we outline a module that focuses on Boolean models of the lac operon network.

Cellular automata in photonic cavity arrays.

Science.gov (United States)

Li, Jing; Liew, T C H

2016-10-31

We propose theoretically a photonic Turing machine based on cellular automata in arrays of nonlinear cavities coupled with artificial gauge fields. The state of the system is recorded making use of the bistability of driven cavities, in which losses are fully compensated by an external continuous drive. The sequential update of the automaton layers is achieved automatically, by the local switching of bistable states, without requiring any additional synchronization or temporal control.

The human body metabolism process mathematical simulation based on Lotka-Volterra model

Science.gov (United States)

Oliynyk, Andriy; Oliynyk, Eugene; Pyptiuk, Olexandr; DzierŻak, RóŻa; Szatkowska, Małgorzata; Uvaysova, Svetlana; Kozbekova, Ainur

2017-08-01

The mathematical model of metabolism process in human organism based on Lotka-Volterra model has beeng proposed, considering healing regime, nutrition system, features of insulin and sugar fragmentation process in the organism. The numerical algorithm of the model using IV-order Runge-Kutta method has been realized. After the result of calculations the conclusions have been made, recommendations about using the modeling results have been showed, the vectors of the following researches are defined.

Complexity-Based Modeling of Scientific Capital: An Outline of Mathematical Theory

Directory of Open Access Journals (Sweden)

Yurij L. Katchanov

2014-01-01

measuring and assessing the accumulated recognition and the specific scientific power. The concept of scientific capital developed by Bourdieu is used in international social science research to explain a set of scholarly properties and practices. Mathematical modeling is applied as a lens through which the scientific capital is addressed. The principal contribution of this paper is an axiomatic characterization of scientific capital in terms of natural axioms. The application of the axiomatic method to scientific capital reveals novel insights into problem still not covered by mathematical modeling. Proposed model embraces the interrelations between separate sociological variables, providing a unified sociological view of science. Suggested microvariational principle is based upon postulate, which affirms that (under suitable conditions the observed state of the agent in scientific field maximizes scientific capital. Its value can be roughly imagined as a volume of social differences. According to the considered macrovariational principle, the actual state of scientific field makes so-called energy functional (which is associated with the distribution of scientific capital minimal.

Modelling and Optimizing Mathematics Learning in Children

Science.gov (United States)

Käser, Tanja; Busetto, Alberto Giovanni; Solenthaler, Barbara; Baschera, Gian-Marco; Kohn, Juliane; Kucian, Karin; von Aster, Michael; Gross, Markus

2013-01-01

This study introduces a student model and control algorithm, optimizing mathematics learning in children. The adaptive system is integrated into a computer-based training system for enhancing numerical cognition aimed at children with developmental dyscalculia or difficulties in learning mathematics. The student model consists of a dynamic…

Linear System Control Using Stochastic Learning Automata

Science.gov (United States)

Ziyad, Nigel; Cox, E. Lucien; Chouikha, Mohamed F.

1998-01-01

This paper explains the use of a Stochastic Learning Automata (SLA) to control switching between three systems to produce the desired output response. The SLA learns the optimal choice of the damping ratio for each system to achieve a desired result. We show that the SLA can learn these states for the control of an unknown system with the proper choice of the error criteria. The results of using a single automaton are compared to using multiple automata.

Modeling Students' Problem Solving Performance in the Computer-Based Mathematics Learning Environment

Science.gov (United States)

Lee, Young-Jin

2017-01-01

Purpose: The purpose of this paper is to develop a quantitative model of problem solving performance of students in the computer-based mathematics learning environment. Design/methodology/approach: Regularized logistic regression was used to create a quantitative model of problem solving performance of students that predicts whether students can…

Mathematical Modeling in Mathematics Education: Basic Concepts and Approaches

Science.gov (United States)

Erbas, Ayhan Kürsat; Kertil, Mahmut; Çetinkaya, Bülent; Çakiroglu, Erdinç; Alacaci, Cengiz; Bas, Sinem

2014-01-01

Mathematical modeling and its role in mathematics education have been receiving increasing attention in Turkey, as in many other countries. The growing body of literature on this topic reveals a variety of approaches to mathematical modeling and related concepts, along with differing perspectives on the use of mathematical modeling in teaching and…

Automata for the People: Machine Noise and Attention

Directory of Open Access Journals (Sweden)

David Ellison

2012-11-01

Full Text Available This article examines the production and reception of incidental machine noise, specifically the variably registered sounds emanating from automata in the eighteenth and nineteenth centuries. The argument proposed here is that the audience for automata performances demonstrated a capacity to screen out mechanical noise that may have otherwise interfered with the narrative theatricality of their display. In this regard the audience may be said to resemble auditors at musical performances who learned to suppress the various noises associated with the physical mechanics of performance, and the faculty of attention itself. For William James among others, attention demands selection among competing stimuli. As the incidental noise associated with automata disappears from sensibility over time, its capacity to signify in other contexts emerges. In the examples traced here, such noise is a means of distinguishing a specifically etherealised human-machine interaction. This is in sharp distinction from other more degrading forms of relationship such as the sound of bodies labouring at machines. In this regard, the barely detected sound of the automata in operation may be seen as a precursor to the white noise associated with modern, corporate productivity.

Simulation of changes in heavy metal contamination in farmland soils of a typical manufacturing center through logistic-based cellular automata modeling.

Science.gov (United States)

Qiu, Menglong; Wang, Qi; Li, Fangbai; Chen, Junjian; Yang, Guoyi; Liu, Liming

2016-01-01

A customized logistic-based cellular automata (CA) model was developed to simulate changes in heavy metal contamination (HMC) in farmland soils of Dongguan, a manufacturing center in Southern China, and to discover the relationship between HMC and related explanatory variables (continuous and categorical). The model was calibrated through the simulation and validation of HMC in 2012. Thereafter, the model was implemented for the scenario simulation of development alternatives for HMC in 2022. The HMC in 2002 and 2012 was determined through soil tests and cokriging. Continuous variables were divided into two groups by odds ratios. Positive variables (odds ratios >1) included the Nemerow synthetic pollution index in 2002, linear drainage density, distance from the city center, distance from the railway, slope, and secondary industrial output per unit of land. Negative variables (odds ratios <1) included elevation, distance from the road, distance from the key polluting enterprises, distance from the town center, soil pH, and distance from bodies of water. Categorical variables, including soil type, parent material type, organic content grade, and land use type, also significantly influenced HMC according to Wald statistics. The relative operating characteristic and kappa coefficients were 0.91 and 0.64, respectively, which proved the validity and accuracy of the model. The scenario simulation shows that the government should not only implement stricter environmental regulation but also strengthen the remediation of the current polluted area to effectively mitigate HMC.

Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions.

Science.gov (United States)

Nehaniv, Chrystopher L; Rhodes, John; Egri-Nagy, Attila; Dini, Paolo; Morris, Eric Rothstein; Horváth, Gábor; Karimi, Fariba; Schreckling, Daniel; Schilstra, Maria J

2015-07-28

Interaction computing is inspired by the observation that cell metabolic/regulatory systems construct order dynamically, through constrained interactions between their components and based on a wide range of possible inputs and environmental conditions. The goals of this work are to (i) identify and understand mathematically the natural subsystems and hierarchical relations in natural systems enabling this and (ii) use the resulting insights to define a new model of computation based on interactions that is useful for both biology and computation. The dynamical characteristics of the cellular pathways studied in systems biology relate, mathematically, to the computational characteristics of automata derived from them, and their internal symmetry structures to computational power. Finite discrete automata models of biological systems such as the lac operon, the Krebs cycle and p53-mdm2 genetic regulation constructed from systems biology models have canonically associated algebraic structures (their transformation semigroups). These contain permutation groups (local substructures exhibiting symmetry) that correspond to 'pools of reversibility'. These natural subsystems are related to one another in a hierarchical manner by the notion of 'weak control'. We present natural subsystems arising from several biological examples and their weak control hierarchies in detail. Finite simple non-Abelian groups are found in biological examples and can be harnessed to realize finitary universal computation. This allows ensembles of cells to achieve any desired finitary computational transformation, depending on external inputs, via suitably constrained interactions. Based on this, interaction machines that grow and change their structure recursively are introduced and applied, providing a natural model of computation driven by interactions.

Mathematical Modelling of a Hybrid Micro-Cogeneration Group Based on a Four Stroke Diesel Engine

Directory of Open Access Journals (Sweden)

Apostol Valentin

2014-06-01

Full Text Available The paper presents a part of the work conducted in the first stage of a Research Grant called ”Hybrid micro-cogeneration group of high efficiency equipped with an electronically assisted ORC” acronym GRUCOHYB. The hybrid micro-cogeneration group is equipped with a four stroke Diesel engine having a maximum power of 40 kW. A mathematical model of the internal combustion engine is presented. The mathematical model is developed based on the Laws of Thermodynamics and takes into account the real, irreversible processes. Based on the mathematical model a computation program was developed. The results obtained were compared with those provided by the Diesel engine manufacturer. Results show a very high correlation between the manufacturer’s data and the simulation results for an engine running at 100% load. Future developments could involve using an exergetic analysis to show the ability of the ORC to generate electricity from recovered heat

Nonlinear threshold Boolean automata networks and phase transitions

OpenAIRE

Demongeot, Jacques; Sené, Sylvain

2010-01-01

In this report, we present a formal approach that addresses the problem of emergence of phase transitions in stochastic and attractive nonlinear threshold Boolean automata networks. Nonlinear networks considered are informally defined on the basis of classical stochastic threshold Boolean automata networks in which specific interaction potentials of neighbourhood coalition are taken into account. More precisely, specific nonlinear terms compose local transition functions that define locally t...

Modelers' perception of mathematical modeling in epidemiology: a web-based survey.

Directory of Open Access Journals (Sweden)

Gilles Hejblum

Full Text Available BACKGROUND: Mathematical modeling in epidemiology (MME is being used increasingly. However, there are many uncertainties in terms of definitions, uses and quality features of MME. METHODOLOGY/PRINCIPAL FINDINGS: To delineate the current status of these models, a 10-item questionnaire on MME was devised. Proposed via an anonymous internet-based survey, the questionnaire was completed by 189 scientists who had published in the domain of MME. A small minority (18% of respondents claimed to have in mind a concise definition of MME. Some techniques were identified by the researchers as characterizing MME (e.g. Markov models, while others-at the same level of sophistication in terms of mathematics-were not (e.g. Cox regression. The researchers' opinions were also contrasted about the potential applications of MME, perceived as highly relevant for providing insight into complex mechanisms and less relevant for identifying causal factors. The quality criteria were those of good science and were not related to the size and the nature of the public health problems addressed. CONCLUSIONS/SIGNIFICANCE: This study shows that perceptions on the nature, uses and quality criteria of MME are contrasted, even among the very community of published authors in this domain. Nevertheless, MME is an emerging discipline in epidemiology and this study underlines that it is associated with specific areas of application and methods. The development of this discipline is likely to deserve a framework providing recommendations and guidance at various steps of the studies, from design to report.

Applications of automata and graphs: Labeling operators in Hilbert space. II

International Nuclear Information System (INIS)

Cho, Ilwoo; Jorgensen, Palle E. T.

2009-01-01

We introduced a family of infinite graphs directly associated with a class of von Neumann automaton model A G . These are finite state models used in symbolic dynamics: stimuli models and in control theory. In the context of groupoid von Neumann algebras, and an associated fractal group, we prove a classification theorem for representations of automata.

On using priced timed automata to achieve optimal scheduling

DEFF Research Database (Denmark)

Rasmussen, Jacob Illum; Larsen, Kim Guldstrand; Subramani, K.

2006-01-01

This contribution reports on the considerable effort made recently towards extending and applying well-established timed automata technology to optimal scheduling and planning problems. The effort of the authors in this direction has to a large extent been carried out as part of the European proj...... of so-called priced timed automata....

FEMME, a flexible environment for mathematically modelling the environment

NARCIS (Netherlands)

Soetaert, K.E.R.; DeClippele, V.; Herman, P.M.J.

2002-01-01

A new, FORTRAN-based, simulation environment called FEMME (Flexible Environment for Mathematically Modelling the Environment), designed for implementing, solving and analysing mathematical models in ecology is presented. Three separate phases in ecological modelling are distinguished: (1) the model

Autopoietic Automata: Complexity Issues in Offspring-Producing Evolving Processes

Czech Academy of Sciences Publication Activity Database

Wiedermann, Jiří

2007-01-01

Roč. 383, č. 2-3 (2007), s. 260-269 ISSN 0304-3975 R&D Projects: GA AV ČR 1ET100300517 Institutional research plan: CEZ:AV0Z10300504 Keywords : autopoietic automata * self-reproducing automata * interactive Turing machine * simulation * computational complexity Subject RIV: IN - Informatics, Computer Science Impact factor: 0.735, year: 2007

Universality of two-dimensional critical cellular automata

OpenAIRE

Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert; Smith, Paul

2014-01-01

We study the class of monotone, two-state, deterministic cellular automata, in which sites are activated (or `infected') by certain configurations of nearby infected sites. These models have close connections to statistical physics, and several specific examples have been extensively studied in recent years by both mathematicians and physicists. This general setting was first studied only recently, however, by Bollob\\'as, Smith and Uzzell, who showed that the family of all such `bootstrap per...

Using a satisfiability solver to identify deterministic finite state automata

NARCIS (Netherlands)

Heule, M.J.H.; Verwer, S.

2009-01-01

We present an exact algorithm for identification of deterministic finite automata (DFA) which is based on satisfiability (SAT) solvers. Despite the size of the low level SAT representation, our approach seems to be competitive with alternative techniques. Our contributions are threefold: First, we

Comprehensive bidding strategies with genetic programming/finite state automata

International Nuclear Information System (INIS)

Richter, C.W. Jr.; Sheble, G.B.; Ashlock, D.

1999-01-01

This research is an extension of the authors' previous work in double auctions aimed at developing bidding strategies for electric utilities which trade electricity competitively. The improvements detailed in this paper come from using data structures which combine genetic programming and finite state automata termed GP-Automata. The strategies developed by the method described here are adaptive--reacting to inputs--whereas the previously developed strategies were only suitable in the particular scenario for which they had been designed. The strategies encoded in the GP-Automata are tested in an auction simulator. The simulator pits them against other distribution companies (distcos) and generation companies (gencos), buying and selling power via double auctions implemented in regional commodity exchanges. The GP-Automata are evolved with a genetic algorithm so that they possess certain characteristics. In addition to designing successful bidding strategies (whose usage would result in higher profits) the resulting strategies can also be designed to imitate certain types of trading behaviors. The resulting strategies can be implemented directly in on-line trading, or can be used as realistic competitors in an off-line trading simulator

Developing mathematical modelling competence

DEFF Research Database (Denmark)

Blomhøj, Morten; Jensen, Tomas Højgaard

2003-01-01

In this paper we introduce the concept of mathematical modelling competence, by which we mean being able to carry through a whole mathematical modelling process in a certain context. Analysing the structure of this process, six sub-competences are identified. Mathematical modelling competence...... cannot be reduced to these six sub-competences, but they are necessary elements in the development of mathematical modelling competence. Experience from the development of a modelling course is used to illustrate how the different nature of the sub-competences can be used as a tool for finding...... the balance between different kinds of activities in a particular educational setting. Obstacles of social, cognitive and affective nature for the students' development of mathematical modelling competence are reported and discussed in relation to the sub-competences....

An effective approach of lesion segmentation within the breast ultrasound image based on the cellular automata principle.

Science.gov (United States)

Liu, Yan; Cheng, H D; Huang, Jianhua; Zhang, Yingtao; Tang, Xianglong

2012-10-01

In this paper, a novel lesion segmentation within breast ultrasound (BUS) image based on the cellular automata principle is proposed. Its energy transition function is formulated based on global image information difference and local image information difference using different energy transfer strategies. First, an energy decrease strategy is used for modeling the spatial relation information of pixels. For modeling global image information difference, a seed information comparison function is developed using an energy preserve strategy. Then, a texture information comparison function is proposed for considering local image difference in different regions, which is helpful for handling blurry boundaries. Moreover, two neighborhood systems (von Neumann and Moore neighborhood systems) are integrated as the evolution environment, and a similarity-based criterion is used for suppressing noise and reducing computation complexity. The proposed method was applied to 205 clinical BUS images for studying its characteristic and functionality, and several overlapping area error metrics and statistical evaluation methods are utilized for evaluating its performance. The experimental results demonstrate that the proposed method can handle BUS images with blurry boundaries and low contrast well and can segment breast lesions accurately and effectively.

On two integrable cellular automata

Energy Technology Data Exchange (ETDEWEB)

Bobenko, A [Technische Univ. Berlin (Germany). Fachbereich Mathematik; Bordemann, M [Freiburg Univ. (Germany). Fachbereich Physik; Gunn, C [Technische Univ. Berlin (Germany). Fachbereich Mathematik; Pinkall, U [Technische Univ. Berlin (Germany). Fachbereich Mathematik

1993-11-01

We describe two simple cellular automata (CA) models which exhibit the essential attributes of soliton systems. The first one is an invertible, 2-state, 1-dimensional CA or, in other words, a nonlinear Z[sub 2]-valued dynamical system with discrete space and time. Against a vacuum state of 0, the system exhibits light cone particles in both spatial directions, which interact in a soliton-like fashion. A complete solution of this system is obtained. We also consider another CA, which is described by the Hirota equation over a finite field, and present a Lax representation for it. (orig.)

A Deterministic Approach to the Synchronization of Cellular Automata

OpenAIRE

Garcia, J.; Garcia, P.

2011-01-01

In this work we introduce a deterministic scheme of synchronization of linear and nonlinear cellular automata (CA) with complex behavior, connected through a master-slave coupling. By using a definition of Boolean derivative, we use the linear approximation of the automata to determine a function of coupling that promotes synchronization without perturbing all the sites of the slave system.

Safety evaluation of driver cognitive failures and driving errors on right-turn filtering movement at signalized road intersections based on Fuzzy Cellular Automata (FCA) model.

Science.gov (United States)

Chai, Chen; Wong, Yiik Diew; Wang, Xuesong

2017-07-01

This paper proposes a simulation-based approach to estimate safety impact of driver cognitive failures and driving errors. Fuzzy Logic, which involves linguistic terms and uncertainty, is incorporated with Cellular Automata model to simulate decision-making process of right-turn filtering movement at signalized intersections. Simulation experiments are conducted to estimate the relationships between cognitive failures and driving errors with safety performance. Simulation results show Different types of cognitive failures are found to have varied relationship with driving errors and safety performance. For right-turn filtering movement, cognitive failures are more likely to result in driving errors with denser conflicting traffic stream. Moreover, different driving errors are found to have different safety impacts. The study serves to provide a novel approach to linguistically assess cognitions and replicate decision-making procedures of the individual driver. Compare to crash analysis, the proposed FCA model allows quantitative estimation of particular cognitive failures, and the impact of cognitions on driving errors and safety performance. Copyright © 2017 Elsevier Ltd. All rights reserved.

An Equivalent Electrical Circuit Model of Proton Exchange Membrane Fuel Cells Based on Mathematical Modelling

Directory of Open Access Journals (Sweden)

Dinh An Nguyen

2012-07-01

Full Text Available Many of the Proton Exchange Membrane Fuel Cell (PEMFC models proposed in the literature consist of mathematical equations. However, they are not adequately practical for simulating power systems. The proposed model takes into account phenomena such as activation polarization, ohmic polarization, double layer capacitance and mass transport effects present in a PEM fuel cell. Using electrical analogies and a mathematical modeling of PEMFC, the circuit model is established. To evaluate the effectiveness of the circuit model, its static and dynamic performances under load step changes are simulated and compared to the numerical results obtained by solving the mathematical model. Finally, the applicability of our model is demonstrated by simulating a practical system.

Solution of Dendritic Growth in Steel by the Novel Point Automata Method

International Nuclear Information System (INIS)

Lorbiecka, A Z; Šarler, B

2012-01-01

The aim of this paper is the simulation of dendritic growth in steel in two dimensions by a coupled deterministic continuum mechanics heat and species transfer model and a stochastic localized phase change kinetics model taking into account the undercooling, curvature, kinetic, and thermodynamic anisotropy. The stochastic model receives temperature and concentration information from the deterministic model and the deterministic heat, and species diffusion equations receive the solid fraction information from the stochastic model. The heat and species transfer models are solved on a regular grid by the standard explicit Finite Difference Method (FDM). The phase-change kinetics model is solved by a novel Point Automata (PA) approach. The PA method was developed [1] in order to circumvent the mesh anisotropy problem, associated with the classical Cellular Automata (CA) method. The PA approach is established on randomly distributed points and neighbourhood configuration, similar as appears in meshless methods. A comparison of the PA and CA methods is shown. It is demonstrated that the results with the new PA method are not sensitive to the crystallographic orientations of the dendrite.

On the use of spin glass concepts in random automata networks

Energy Technology Data Exchange (ETDEWEB)

Miranda, E N; Parga, N

1988-06-01

We apply concepts and techniques developed in the context of the mean-field theory of spin glasses to networks of random automata. This approach, proposed recently by Derrida and Flyvbjerg, may be useful in understanding the multivalley structure of the Kauffman model.

Bounded-oscillation Pushdown Automata

Directory of Open Access Journals (Sweden)

Pierre Ganty

2016-09-01

Full Text Available We present an underapproximation for context-free languages by filtering out runs of the underlying pushdown automaton depending on how the stack height evolves over time. In particular, we assign to each run a number quantifying the oscillating behavior of the stack along the run. We study languages accepted by pushdown automata restricted to k-oscillating runs. We relate oscillation on pushdown automata with a counterpart restriction on context-free grammars. We also provide a way to filter all but the k-oscillating runs from a given PDA by annotating stack symbols with information about the oscillation. Finally, we study closure properties of the defined class of languages and the complexity of the k-emptiness problem asking, given a pushdown automaton P and k >= 0, whether P has a k-oscillating run. We show that, when k is not part of the input, the k-emptiness problem is NLOGSPACE-complete.