Algebraic and structural automata theory
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.
Borowik, Bohdan; Lahno, Valery; Petrov, Oleksandr
2013-01-01
This book serves a dual purpose: firstly to combine the treatment of circuits and digital electronics, and secondly, to establish a strong connection with the contemporary world of digital systems. The need for this approach arises from the observation that introducing digital electronics through a course in traditional circuit analysis is fast becoming obsolete. Our world has gone digital. Automata theory helps with the design of digital circuits such as parts of computers, telephone systems and control systems. A complete perspective is emphasized, because even the most elegant computer architecture will not function without adequate supporting circuits. The focus is on explaining the real-world implementation of complete digital systems. In doing so, the reader is prepared to immediately begin design and implementation work. This work serves as a bridge to take readers from the theoretical world to the everyday design world where solutions must be complete to be successful.
Automata theory and its applications
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 ...
Application of Fuzzy Algebra in Automata theory
Kharatti Lal
2016-06-01
Full Text Available In our first application we consider strings of fuzzy singletons as input to a fuzzy finite state machine. The notion of fuzzy automata was introduced in [58]. There has been considerable growth in the area [18]. In this section present a theory of free fuzzy monoids and apply the results to the area of fuzzy automata. In fuzzy automata, the set of strings of input symbols can be considered to be a free monoid. We introduced the motion of fuzzy strings of input symbols, where the fuzzy strings from free fuzzy submonoids of the free monoids of input strings. We show that fuzzy automata with fuzzy input are equivalent to fuzzy automata with crisp input. Hence the result of fuzzy automata theory can be immediately applied to those of fuzzy automata theory with fuzzy input. The result are taken from [7] and [34].
Learning automata theory and applications
Najim, K
1994-01-01
Learning systems have made a significant impact on all areas of engineering problems. They are attractive methods for solving many problems which are too complex, highly non-linear, uncertain, incomplete or non-stationary, and have subtle and interactive exchanges with the environment where they operate. The main aim of the book is to give a systematic treatment of learning automata and to produce a guide to a wide variety of ideas and methods that can be used in learning systems, including enough theoretical material to enable the user of the relevant techniques and concepts to understand why
Automata theory based on complete residuated lattice-valued logic
邱道文
2001-01-01
This paper establishes a fundamental framework of automata theory based on complete residuated lattice-valued logic. First it deals with how to extend the transition relation of states and particularly presents a characterization of residuated lattice by fuzzy automata (called valued automata).After that fuzzy subautomata (called valued subautomata), successor and source operators are proposed and their basic properties as well as the equivalent relation among them are discussed, from which it follows that the two fuzzy operators are exactly fuzzy closure operators. Finally an L bifuzzy topological characterization of valued automata is presented, so a more generalized fuzzy automata theory is built.
An Interface Theory for Input/Output Automata
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 separa...
Event-Clock Automata: From Theory to Practice
Geeraerts, Gilles; Sznajder, Nathalie
2011-01-01
Event clock automata (ECA) are a model for timed languages that has been introduced by Alur, Fix and Henzinger as an alternative to timed automata, with better theoretical properties (for instance, ECA are determinizable while timed automata are not). In this paper, we revisit and extend the theory of ECA. We first prove that no finite time abstract language equivalence exists for ECA, thereby disproving a claim in the original work on ECA. This means in particular that regions do not form a time abstract bisimulation. Nevertheless, we show that regions can still be used to build a finite automaton recognizing the untimed language of an ECA. Then, we extend the classical notions of zones and DBMs to let them handle event clocks instead of plain clocks (as in timed automata) by introducing event zones and Event DBMs (EDBMs). We discuss algorithms to handle event zones represented as EDBMs, as well as (semi-) algorithms based on EDBMs to decide language emptiness of ECA.
Theory of automata, formal languages and computation
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.
Classification of networks of automata by dynamical mean field theory
Dynamical mean field theory is used to classify the 224=65,536 different networks of binary automata on a square lattice with nearest neighbour interactions. Application of mean field theory gives 700 different mean field classes, which fall in seven classes of different asymptotic dynamics characterized by fixed points and two-cycles. (orig.)
A half-century of automata theory celebration and inspiration
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
Inclusion Matching Implementation of Automata Modulo Theory (AMT)
Massacci, Fabio; Siahaan, Ida
2009-01-01
The traditional realm of formal methods is the off-line veriﬁcation of formal properties of hardware and software. In this technical report we describe a different approach that uses formal methods (namely the integration of automata modulo theory with decision procedures) on-the-ﬂy, at the time an application is downloaded on a mobile application such as PDA or a smart phone. We also describe its integration with decision solver based on MathSAT and NuSMV, and the results of our experiments ...
Automata network theories in immunology: their utility and their underdetermination.
Atlan, H
1989-01-01
Small networks of threshold automata are used to model complex interactions between populations of regulatory cells (helpers and suppressors, antigen specific and anti-idiotypic) which participate in the immune response. The models, being discrete and semiquantitative, are well adapted to the situation of incomplete information often encountered in vivo. However, the dynamics of many different network structures usually end up in the same attractor set. Thus, many different theories are equivalent in their explicative power for the same facts. This property, known as underdetermination of the theories by the facts, is given a quantitative estimate. It appears that such an underdetermination, as a kind of irreducible complexity, can be expected in many in vivo biological processes, even when the number of interacting and functionally coupled elements is relatively small. PMID:2924021
Computer Models and Automata Theory in Biology and Medicine
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...
Priced Timed Automata: Theory and Tools
Larsen, Kim Guldstrand
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.......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....
L-FLAT: Logtalk Toolkit for Formal Languages and Automata Theory
Moura, Paulo; Dias, Artur Miguel
2011-01-01
We describe L-FLAT, a Logtalk Toolkit for teaching Formal Languages and Automata Theory. L-FLAT supports the definition of \\textsl{alphabets}, the definition of \\textsl{orders} over alphabet symbols, the partial definition of \\textsl{languages} using unit tests, and the definition of \\textsl{mechanisms}, which implement language generators or language recognizers. Supported mechanisms include \\textsl{predicates}, \\textsl{regular expressions}, \\textsl{finite automata}, \\textsl{context-free gra...
Cellular automata approach to three-phase traffic theory
The cellular automata (CA) approach to traffic modelling is extended to allow for spatially homogeneous steady state solutions that cover a two-dimensional region in the flow-density plane. Hence these models fulfil a basic postulate of a three-phase traffic theory proposed by Kerner. This is achieved by a synchronization distance, within which a vehicle always tries to adjust its speed to that of the vehicle in front. In the CA models presented, the modelling of the free and safe speeds, the slow-to-start rules as well as some contributions to noise are based on the ideas of the Nagel-Schreckenberg-type modelling. It is shown that the proposed CA models can be very transparent and still reproduce the two main types of congested patterns (the general pattern and the synchronized flow pattern) as well as their dependence on the flows near an on-ramp, in qualitative agreement with the recently developed continuum version of the three-phase traffic theory (Kerner B S and Klenov S L 2002 J. Phys. A: Math. Gen. 35 L31 ). These features are qualitatively different from those in previously considered CA traffic models. The probability of the breakdown phenomenon (i.e. of the phase transition from free flow to synchronized flow) as function of the flow rate to the on-ramp and of the flow rate on the road upstream of the on-ramp is investigated. The capacity drops at the on-ramp which occur due to the formation of different congested patterns are calculated
Notes on automata theory based on quantum logic
QIU DaoWen
2007-01-01
The main results are as follows: (1) it deals with a number of basic operations (concatenation, Kleene closure, homomorphism, complement); (2) due to a condition imposed on the implication operator for discussing some basic issues in orthomodular lattice-valued automata, this condition is investigated in detail, and it is discovered that all the relatively reasonable five implication operators in quantum logic do not satisfy this condition, and that one of the five implications satisfies such a condition iff the truth-value lattice is indeed a Boolean algebra; (3) it deals further with orthomodular lattice-valued successor and source operators; (4) an example is provided, implying that some negative results obtained in the literature may still hold in some typical orthomodular lattice-valued automata.
NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra
Rosenberg, Ivo; Goldstein, Martin
2005-01-01
Several of the contributions to this volume bring forward many mutually beneficial interactions and connections between the three domains of the title. Developing them was the main purpose of the NATO ASI summerschool held in Montreal in 2003. Although some connections, for example between semigroups and automata, were known for a long time, developing them and surveying them in one volume is novel and hopefully stimulating for the future. Another aspect is the emphasis on the structural theory of automata that studies ways to contstruct big automata from small ones. The volume also has contributions on top current research or surveys in the three domains. One contribution even links clones of universal algebra with the computational complexity of computer science. Three contributions introduce the reader to research in the former East block.
Finite automata, their algebras and grammars towards a theory of formal expressions
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...
Learning automata an introduction
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.
Deepak D’Souza; P S Thiagarajan
2002-04-01
We identify a subclass of timed automata called product interval automata and develop its theory. These automata consist of a network of timed agents with the key restriction being that there is just one clock for each agent and the way the clocks are read and reset is determined by the distribution of shared actions across the agents. We show that the resulting automata admit a clean theory in both logical and language theoretic terms. We also show that product interval automata are expressive enough to model the timed behaviour of asynchronous digital circuits.
Automation of Algorithmic Tasks for Virtual Laboratories Based on Automata Theory
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.
Automation of Algorithmic Tasks for Virtual Laboratories Based on Automata Theory
Evgeniy A. Efimchik
2016-04-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.
Efficient Identification of Timed Automata: Theory and practice
Verwer, S.E.
2010-01-01
This thesis contains a study in a subfield of artificial intelligence, learning theory, machine learning, and statistics, known as system (or language) identification. System identification is concerned with constructing (mathematical) models from observations. Such a model is an intuitive descripti
Active XML Document Rewriting Based on Tree Automata Theory
MA Haitao; HAO Zhongxiao; ZHU Yan
2006-01-01
The problem of document rewriting is a fundamental problem in active XML(AXML) data exchange and usually has a higher complexity.Prior work was focused on string automaton theory.This paper tries to solve it by using tree automaton.More precisely, the paper firstly defines a new tree automaton, active XML tree automaton (AXTA),which can efficiently represent the set of AXML documents produced by an AXML document or AXML document schema.And then, an algorithm for constructing AXTA automaton is also proposed.Finally, a polynomial time(PTIME) determining algorithm for AXML document rewriting is presented based on AXTA automaton.
Special Relativity Derived from Cellular Automata Theory The Origin of the Universal Speed Limit
Ostoma, T
1998-01-01
A new formulation of Special Relativity is described. It is based on Cellular Automata theory and on a new theory of inertia called Quantum Inertia. The universe consists of a huge 3D array of cells given by C(x,y,z), whose numeric states are updated by every new CA clock period. The numeric state of the cells depends on the contents of the imediate neigbours and on the mathematical rules of the cell, with each cell containing the same set of rules. Photon motion on the CA is represented by information patterns 'shifting' from cell to adjacent cell at every clock cycle, and this represents the universal speed limit. The Lorentz Transformations follow directly from this model of light motion. The concept of mass and inertia is revised to be compatible with the CA model.
Bagnoli, Franco
1998-01-01
An introduction to cellular automata (both deterministic and probabilistic) with examples. Definition of deterministic automata, dynamical properties, damage spreading and Lyapunov exponents; probabilistic automata and Markov processes, nonequilibrium phase transitions, directed percolation, diffusion; simulation techniques, mean field. Investigation themes: life, epidemics, forest fires, percolation, modeling of ecosystems and speciation. They represent my notes for the school "Dynamical Mod...
Adamatzky, Andrew
2015-01-01
The book gives a comprehensive overview of the state-of-the-art research and engineering in theory and application of Lattice Automata in design and control of autonomous Robots. Automata and robots share the same notional meaning. Automata (originated from the latinization of the Greek word “αυτόματον”) as self-operating autonomous machines invented from ancient years can be easily considered the first steps of robotic-like efforts. Automata are mathematical models of Robots and also they are integral parts of robotic control systems. A Lattice Automaton is a regular array or a collective of finite state machines, or automata. The Automata update their states by the same rules depending on states of their immediate neighbours. In the context of this book, Lattice Automata are used in developing modular reconfigurable robotic systems, path planning and map exploration for robots, as robot controllers, synchronisation of robot collectives, robot vision, parallel robotic actuators. All chapters are...
Varieties of Learning automata: An Overview
Thathachar, MLA; Sastry, PS
2002-01-01
Automata models of learning systems introduced in the 1960s were popularized as learning automata (LA) in a survey paper 1974 [1]. Since then, there have been many fundamental advances in the theory as well as applications of these learning models. In the past few years, the structure of LA, has been modified in several directions to suit different applications. Concepts such as parameterized learning automata (PLA), generalized learning,automata (GLA), and continuous action-set learning auto...
On the Minimization of XML-Schemas and Tree Automata for Unranked Trees
Martens, Wim; Niehren, Joachim
2007-01-01
Automata for unranked trees form a foundation for XML schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. First, we study unranked tree automata that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal automata in that class are not unique and that minimization is np complete. Second, we study more recent automata classes that do al...
On path hypercompositions in graphs and automata
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.
Codd, E F
1968-01-01
Cellular Automata presents the fundamental principles of homogeneous cellular systems. This book discusses the possibility of biochemical computers with self-reproducing capability.Organized into eight chapters, this book begins with an overview of some theorems dealing with conditions under which universal computation and construction can be exhibited in cellular spaces. This text then presents a design for a machine embedded in a cellular space or a machine that can compute all computable functions and construct a replica of itself in any accessible and sufficiently large region of t
An overview of quantum computation models: quantum automata
2008-01-01
Quantum automata,as theoretical models of quantum computers,include quantum finite automata (QFA),quantum sequential machines (QSM),quantum pushdown automata (QPDA),quantum Turing machines (QTM),quantum cellular automata (QCA),and the others,for example,automata theory based on quantum logic (orthomodular lattice-valued automata).In this paper,we try to outline a basic progress in the research on these models,focusing on QFA,QSM,QPDA,QTM,and orthomodular lattice-valued automata.Also,other models closely relative to them are mentioned.In particular,based on the existing results in the literature,we finally address a number of problems to be studied in future.
Continuity Controlled Hybrid Automata
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 hybrid automata as timed transition systems. We also relate the synchronized product operator on hybrid automata to the parallel composition operator of the process algebra. It turns out that the f...
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 r...
Massacci, Fabio; Siahaan, Ida
2009-01-01
With the advent of the next generation java servlet on the smartcard, the Future Internet will be composed by web servers and clients silently yet busily running on high end smart cards in our phones and our wallets. In this new world model we can no longer accept the current security model where programs can be downloaded on our machines just because they are vaguely "trusted". We want to know what they do in more precise details. We claim that the Future Internet needs the notion of securit...
Quantum features of natural cellular automata
Elze, Hans-Thomas
2016-03-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.
Quantum features of natural cellular automata
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 Schroedinger 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\\rightarrow 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...
Interface Input/Output Automata
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...... from guarantees not yet seen in other behavioral interface theories. Moreover we derive the composition operator systematically and formally, guaranteeing that the resulting compositions are always the weakest in the sense of assumptions, and the strongest in the sense of guarantees. 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....
Probabilistic weighted automata
Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A.
2009-01-01
Nondeterministic weighted automata are finite automata with numerical weights on transitions. They define quantitative languages $L$ that assign to each word $w$ a real number $L(w)$. The value of an infinite word $w$ is computed as the maximal value of all runs over $w$, and the value of a run as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted automata, in which the transitions are chosen in a randomized (rather ...
Continuity Controlled Hybrid Automata
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
Bergstra, J.A.; Middelburg, C.A.
2008-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
Membrane Automata with Priorities
Luděk Cienciala; Lucie Ciencialová
2004-01-01
In this paper the one-way P automata with priorities are introduced. Such automata are P systemshere the membranes are only allowed to consume objects from parent membranes, under the given conditions. The result of computation of these systems is the set of multiset sequences consumed by skin membrane intc the system. The rules associated in some order with each membrane cannot modify any objects, they can only move them through membrane. We show that P automata with priorities and two membranes can accept every recursively enumerated language.
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.
Automata and Quantum Computing
Ambainis, Andris; Yakaryilmaz, Abuzer
2015-01-01
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers.
Katja, Verbeeck; Ann, Nowe; Peter, Vrancx; Maarten, Peeters
2008-01-01
In this chapter we have demonstrated that Learning Automata are interesting building blocks for multi-agent Reinforcement learning algorithms. LA can be viewed as policy iterators, that update their action probabilities based on private information only. Even in multi-automaton settings, each LA is updated using only the environment response, and not on the basis of any knowledge regarding the other automata, i.e. nor their strategies, nor their feedback. As such LA based agent algorithms are...
Translating partitioned cellular automata into classical type cellular automata
Poupet, Victor
2008-01-01
Partitioned cellular automata are a variant of cellular automata that was defined in order to make it very simple to create complex automata having strong properties such as number conservation and reversibility (which are often difficult to obtain on cellular automata). In this article we show how a partitioned cellular automaton can be translated into a regular cellular automaton in such a way that these properties are conserved.
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 proj...... 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....
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.
Automata, universality, computation tribute to Maurice Margenstern
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.
A Parallel Encryption Algorithm for Block Ciphers Based on Reversible Programmable Cellular Automata
Das, Debasis
2010-01-01
A Cellular Automata (CA) is a computing model of complex System using simple rule. In CA the problem space into number of cell and each cell can be one or several final state. Cells are affected by neighbours' to the simple rule. Cellular Automata are highly parallel and discrete dynamical systems, whose behaviour is completely specified in terms of a local relation. This paper deals with the Cellular Automata (CA) in cryptography for a class of Block Ciphers through a new block encryption algorithm based on Reversible Programmable Cellular Automata Theory. The proposed algorithm belongs to the class of symmetric key systems.
Quantum Genetics, Quantum Automata and Quantum Computation
Baianu, Professor I. C.
2004-01-01
The concepts of quantum automata and quantum computation are studied in the context of quantum genetics and genetic networks with nonlinear dynamics. In a previous publication (Baianu,1971a) the formal concept of quantum automaton was introduced and its possible implications for genetic and metabolic activities in living cells and organisms were considered. This was followed by a report on quantum and abstract, symbolic computation based on the theory of categories, functors and natural trans...
Compositions of (max, +) automata
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.333, year: 2014 http://link.springer.com/article/10.1007/s10626-014-0186-6
Bisimulations for fuzzy automata
Ćirić, Miroslav; Ignjatović, Jelena; Damljanović, Nada; Bašić, Milan
2011-01-01
Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy a...
Stochastic properties of disturbed Elementary Cellular Automata
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)
Designing beauty the art of cellular automata
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 compact topology for sand automata
Dennunzio, Alberto; Masson, Benoît
2008-01-01
In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of the cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with the nilpotency. We show that the classical definition is not meaningful for sand automata. Then, we introduce a suitable new notion of nilpotency for sand automata. Finally, we prove that this simple dynamical behavior is undecidable.
Kumar, Shailesh
2010-01-01
A cellular automata (CA) configuration is constructed that exhibits emergent failover. The configuration is based on standard Game of Life rules. Gliders and glider-guns form the core messaging structure in the configuration. The blinker is represented as the basic computational unit, and it is shown how it can be recreated in case of a failure. Stateless failover using primary-backup mechanism is demonstrated. The details of the CA components used in the configuration and its working are described, and a simulation of the complete configuration is also presented.
Weighted Watson-Crick automata
Tamrin, Mohd Izzuddin Mohd; Turaev, Sherzod; Sembok, Tengku Mohd Tengku
2014-07-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.
Weighted Watson-Crick automata
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.
Height-Deterministic Pushdown Automata
Nowotka, Dirk; Srba, Jiri
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...
Energy Games in Multiweighted Automata
Fahrenberg, U.; Juhl, L.; Larsen, Kim Guldstrand; Srba, J.
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....
Learning communicating and nondeterministic automata
Kern, Carsten
2009-01-01
The results of this dissertation are two-fold. On the one hand, inductive learning techniques are extended and two new inference algorithms for inferring nondeterministic, and universal, respectively, finite-state automata are presented. On the other hand, certain learning techniques are employed and enhanced to semi-automatically infer communicating automata (also called design models in the software development cycle). For both topics, theoretical results on the feasibility of the approache...
Faulkner, Nicholas
2012-01-01
We study some dynamical properties of a family of two-dimensional cellular automata: those that arise from an underlying one dimensional sand automaton whose local rule is obtained using a latin square. We identify a simple sand automaton G whose local rule is algebraic, and classify this automaton as having equicontinuity points, but not being equicontinuous. We also show it is not surjective. We generalise some of these results to a wider class of sand automata.
Modelling Social-Technical Attacks with Timed Automata
David, Nicolas; David, Alexandre; Hansen, Rene Rydhof;
2015-01-01
Attacks on a system often exploit vulnerabilities that arise from human behaviour or other human activity. Attacks of this type, so-called socio-technical attacks, cover everything from social engineering to insider attacks, and they can have a devastating impact on an unprepared organisation. 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....
Single spin measurement using cellular automata techniques
Perez-Delgado, C A; Cory, D G; Mosca, M; Cappellaro, Paola; Cory, David G.; Mosca, Michele; Perez-Delgado, Carlos A.
2006-01-01
We propose an approach for single spin measurement. Our method uses techniques from the theory of quantum cellular automata to correlate a large amount of ancillary spins to the one to be measured. It has the distinct advantage of being efficient, and to a certain extent fault-tolerant. Under ideal conditions, it requires the application of only order of cube root of N steps (each requiring a constant number of rf pulses) to create a system of N correlated spins. It is also fairly robust against pulse errors, imperfect initial polarization of the ancilla spin system, and does not rely on entanglement. We study the scalability of our scheme through numerical simulation.
Single spin measurement using cellular automata techniques
Perez-Delgado, Carlos A.; Mosca, Michele; Cappellaro, Paola; Cory, David G.
2006-01-01
We propose an approach for single spin measurement. Our method uses techniques from the theory of quantum cellular automata to correlate a large amount of ancillary spins to the one to be measured. It has the distinct advantage of being efficient, and to a certain extent fault-tolerant. Under ideal conditions, it requires the application of only order of cube root of N steps (each requiring a constant number of rf pulses) to create a system of N correlated spins. It is also fairly robust agai...
Porod, Wolfgang; Lent, Craig S.; Bernstein, Gary H.
1994-06-01
The Notre Dame group has developed a new paradigm for ultra-dense and ultra-fast information processing in nanoelectronic systems. These Quantum Cellular Automata (QCA's) are the first concrete proposal for a technology based on arrays of coupled quantum dots. The basic building block of these cellular arrays is the Notre Dame Logic Cell, as it has been called in the literature. The phenomenon of Coulomb exclusion, which is a synergistic interplay of quantum confinement and Coulomb interaction, leads to a bistable behavior of each cell which makes possible their use in large-scale cellular arrays. The physical interaction between neighboring cells has been exploited to implement logic functions. New functionality may be achieved in this fashion, and the Notre Dame group invented a versatile majority logic gate. In a series of papers, the feasibility of QCA wires, wire crossing, inverters, and Boolean logic gates was demonstrated. A major finding is that all logic functions may be integrated in a hierarchial fashion which allows the design of complicated QCA structures. The most complicated system which was simulated to date is a one-bit full adder consisting of some 200 cells. In addition to exploring these new concepts, efforts are under way to physically realize such structures both in semiconductor and metal systems. Extensive modeling work of semiconductor quantum dot structures has helped identify optimum design parameters for QCA experimental implementations.
Adaptive stochastic cellular automata: Applications
Qian, S.; Lee, Y. C.; Jones, R. D.; Barnes, C. W.; Flake, G. W.; O'Rourke, M. K.; Lee, K.; Chen, H. H.; Sun, G. Z.; Zhang, Y. Q.; Chen, D.; Giles, C. L.
1990-09-01
The stochastic learning cellular automata model has been applied to the problem of controlling unstable systems. Two example unstable systems studied are controlled by an adaptive stochastic cellular automata algorithm with an adaptive critic. The reinforcement learning algorithm and the architecture of the stochastic CA controller are presented. Learning to balance a single pole is discussed in detail. Balancing an inverted double pendulum highlights the power of the stochastic CA approach. The stochastic CA model is compared to conventional adaptive control and artificial neural network approaches.
Action principle for cellular automata and the linearity of quantum mechanics
Elze, Hans-Thomas
2014-01-01
We introduce an action principle for a class of integer valued cellular automata and obtain Hamiltonian equations of motion. Employing sampling theory, these discrete deterministic equations are invertibly mapped on continuum equations for a set of bandwidth limited harmonic oscillators, which encode the Schr\\"odinger equation. Thus, the linearity of quantum mechanics is related to the action principle of such cellular automata and its conservation laws to discrete ones.
Profinite Techniques for Probabilistic Automata and the Optimality of the Markov Monoid Algorithm
Fijalkow, Nathanaël
2015-01-01
We consider the value 1 problem for probabilistic automata over finite words. This problem is known to be undecidable. However, different algorithms have been proposed to partially solve it. The aim of this paper is to prove that one such algorithm, called the Markov Monoid algorithm, is optimal. To this end, we develop a profinite theory for probabilistic automata. This new framework gives a topological account by constructing the free prostochastic monoid. We use it in two ways. First, to c...
Is there a sharp phase transition for deterministic cellular automata?
Previous work has suggested that there is a kind of phase transition between deterministic automata exhibiting periodic behavior and those exhibiting chaotic behavior. However, unlike the usual phase transitions of physics, this transition takes place over a range of values of the parameter rather than at a specific value. The present paper asks whether the transition can be made sharp, either by taking the limit of an infinitely large rule table, or by changing the parameter in terms of which the space of automata is explored. We find strong evidence that, for the class of automata we consider, the transition does become sharp in the limit of an infinite number of symbols, the size of the neighborhood being held fixed. Our work also suggests an alternative parameter in terms of which it is likely that the transition will become fairly sharp even if one does not increase the number of symbols. In the course of our analysis, we find that mean field theory, which is our main tool, gives surprisingly good predictions of the statistical properties of the class of automata we consider. 18 refs., 6 figs
On the Accepting Power of 2-Tape Büchi Automata
Finkel, Olivier
2007-01-01
We show that, from a topological point of view, 2-tape B\\"uchi automata have the same accepting power than Turing machines equipped with a B\\"uchi acceptance condition. In particular, we show that for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete infinitary rational relations accepted by 2-tape B\\"uchi automata. This very surprising result gives answers to questions of W. Thomas [Automata and Quantifier Hierarchies, in: Formal Properties of Finite automata and Applications, Ramatuelle, 1988, LNCS 386, Springer, 1989, p.104-119], of P. Simonnet [Automates et Th\\'eorie Descriptive, Ph. D. Thesis, Universit\\'e Paris 7, March 1992], and of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In: "A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621].
Control of (max,+) Automata: a single step approach
Komenda, Jan; Lahaye, S.; Boimond, J.-L.
Budapest: European Union Control Association, 2009 - (Kevicky, L.; Bokor, J.), s. 1985-1990 ISBN 978-963-311-369-1. [European Control Conference 2009. Budapest (HU), 23.08.2009-26.08.2009] Grant ostatní: EU Projekt(XE) EU. ICT .DISC 224498 Institutional research plan: CEZ:AV0Z10190503 Keywords : (max,+) automata * supervisory control * Hadamard product * residuation theory Subject RIV: BA - General Mathematics
Constraint LTL Satisfiability Checking without Automata
Bersani, Marcello M; Morzenti, Angelo; Pradella, Matteo; Rossi, Matteo; Pietro, Pierluigi San
2012-01-01
This paper introduces a novel technique to decide the satisfiability of formulae written in the language of Linear Temporal Logic with Both future and past operators and atomic formulae belonging to constraint system D (CLTLB(D) for short). The technique is based on the concept of bounded satisfiability, and hinges on an encoding of CLTLB(D) formulae into QF-EUD, the theory of quantifier-free equality and uninterpreted functions combined with D. Similarly to standard LTL, where bounded model-checking and SAT-solvers can be used as an alternative to automata-theoretic approaches to model-checking, our approach allows users to solve the satisfiability problem for CLTLB(D) formulae through SMT-solving techniques, rather than by checking the emptiness of the language of a suitable automaton A{\\phi}. The technique is effective, and it has been implemented in our Zot formal verification tool.
Cellular automata in image processing and geometry
Adamatzky, Andrew; Sun, Xianfang
2014-01-01
The book presents findings, views and ideas on what exact problems of image processing, pattern recognition and generation can be efficiently solved by cellular automata architectures. This volume provides a convenient collection in this area, in which publications are otherwise widely scattered throughout the literature. The topics covered include image compression and resizing; skeletonization, erosion and dilation; convex hull computation, edge detection and segmentation; forgery detection and content based retrieval; and pattern generation. The book advances the theory of image processing, pattern recognition and generation as well as the design of efficient algorithms and hardware for parallel image processing and analysis. It is aimed at computer scientists, software programmers, electronic engineers, mathematicians and physicists, and at everyone who studies or develops cellular automaton algorithms and tools for image processing and analysis, or develops novel architectures and implementations of mass...
Active automata learning for real life applications
Merten, Maik
2013-01-01
Automata learning is a concept discussed in the literature for decades. Accordingly, the theoretical framework for learning automata from observations has been in place already for a considerable time. Despite the ever-increasing theoretical maturity of the field, real-life applications are few and far between. In part this can certainly be attributed to the lack of ready-made infrastructure, e.g., frameworks that support automata learning with the goal of learning realistic systems....
Xtoys cellular automata on xwindows
Creutz, M
1995-01-01
Xtoys is a collection of xwindow programs for demonstrating simulations of various statistical models. Included are xising, for the two dimensional Ising model, xpotts, for the q-state Potts model, xautomalab, for a fairly general class of totalistic cellular automata, xsand, for the Bak-Tang-Wiesenfield model of self organized criticality, and xfires, a simple forest fire simulation. The programs should compile on any machine supporting xwindows.
Parallel adaptive finite state automata
Rocha, Ricardo L.; Garanhani, César E.C.
2006-01-01
The interest on parallelism has grown in many areas of technology. Hardware development has evolved greatly in the last years, leaving to software developers the goal of building better tools and compilers for parallel computation. Also, symbolic computation must take advantage of parallel computation. The proposal contained in this paper is to use functional languages as a tool to implement adaptive automata using the concepts of symbolic computation
Dominant Strategies of Quantum Games on Quantum Periodic Automata
Konstantinos Giannakis
2015-11-01
Full Text Available Game theory and its quantum extension apply in numerous fields that affect people’s social, political, and economical life. Physical limits imposed by the current technology used in computing architectures (e.g., circuit size give rise to the need for novel mechanisms, such as quantum inspired computation. Elements from quantum computation and mechanics combined with game-theoretic aspects of computing could open new pathways towards the future technological era. This paper associates dominant strategies of repeated quantum games with quantum automata that recognize infinite periodic inputs. As a reference, we used the PQ-PENNY quantum game where the quantum strategy outplays the choice of pure or mixed strategy with probability 1 and therefore the associated quantum automaton accepts with probability 1. We also propose a novel game played on the evolution of an automaton, where players’ actions and strategies are also associated with periodic quantum automata.
Parrondo games as lattice gas automata
Meyer, David A.; Blumer, Heather
2001-01-01
Parrondo games are coin flipping games with the surprising property that alternating plays of two losing games can produce a winning game. We show that this phenomenon can be modelled by probabilistic lattice gas automata. Furthermore, motivated by the recent introduction of quantum coin flipping games, we show that quantum lattice gas automata provide an interesting definition for quantum Parrondo games.
L.A.U.D.E: Learning Automata for Urban Development Exploration. The Case Study of Rome Urban System
Rabino, Giovanni A.; Papini, Lorenzo; Silvana T. Lombardo; Colonna, Antonio; Stefano, Vittorio Di
1998-01-01
This paper deals with urban cellular automata. It is organized in two parts. The first one is concerning theory, methodology and operational aspects of the application of cellular automata to the simulation of dynamics of urban systems. Starting with a review of the literature on this research field (Batty, Cecchini, Couclelis, White et al.) we present: ? as to theoretical foundation of the approach, a clarification on the distinction between global and local description (the traditional mode...
Edit Distance for Pushdown Automata
Chatterjee, Krishnendu; Henzinger, Thomas A.; Ibsen-Jensen, Rasmus; Otop, Jan
2015-01-01
The edit distance between two words $w_1, w_2$ is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform $w_1$ to $w_2$. The edit distance generalizes to languages ${\\cal L}_1, {\\cal L}_2$, where the edit distance is the minimal number $k$ such that for every word from ${\\cal L}_1$ there exists a word in ${\\cal L}_2$ with edit distance at most $k$. We study the edit distance computation problem between pushdown automata and their subclas...
Cellular automata a parallel model
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.
Mathematical Physics of Cellular Automata
Garcia-Morales, Vladimir
2012-01-01
A universal map is derived for all deterministic 1D cellular automata (CA) containing no freely adjustable parameters. The map can be extended to an arbitrary number of dimensions and topologies and its invariances allow to classify all CA rules into equivalence classes. Complexity in 1D systems is then shown to emerge from the weak symmetry breaking of the addition modulo an integer number p. The latter symmetry is possessed by certain rules that produce Pascal simplices in their time evolution. These results elucidate Wolfram's classification of CA dynamics.
Compositions of (max+)-automata
Lahaye, S.; Komenda, Jan; Boimond, J.-L.
Guadalajara : IFAC, 2012 - (Ramírez-Treviño, A.; López-Mellado, E.; Lesage, J.), s. 61-66 ISBN 978-3-902823-28-1. [11th International Workshop on Discrete Event Systems (WODES 2012). Guadalajara (MX), 03.10.2012-05.10.2012] R&D Projects: GA ČR(CZ) GAP103/11/0517 Institutional support: RVO:67985840 Keywords : (max,+) automata * synchronous composition * asynchronous composition Subject RIV: BA - General Mathematics http://www.ifac-papersonline.net/Detailed/58159.html
Universal map for cellular automata
García-Morales, V., E-mail: vmorales@ph.tum.de [Institute for Advanced Study – Technische Universität München, Lichtenbergstr. 2a, D-85748 Garching (Germany)
2012-08-20
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.
Chaotic behavior in the disorder cellular automata
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
Towards a voxel-based geographic automata for the simulation of geospatial processes
Jjumba, Anthony; Dragićević, Suzana
2016-07-01
Many geographic processes evolve in a three dimensional space and time continuum. However, when they are represented with the aid of geographic information systems (GIS) or geosimulation models they are modelled in a framework of two-dimensional space with an added temporal component. The objective of this study is to propose the design and implementation of voxel-based automata as a methodological approach for representing spatial processes evolving in the four-dimensional (4D) space-time domain. Similar to geographic automata models which are developed to capture and forecast geospatial processes that change in a two-dimensional spatial framework using cells (raster geospatial data), voxel automata rely on the automata theory and use three-dimensional volumetric units (voxels). Transition rules have been developed to represent various spatial processes which range from the movement of an object in 3D to the diffusion of airborne particles and landslide simulation. In addition, the proposed 4D models demonstrate that complex processes can be readily reproduced from simple transition functions without complex methodological approaches. The voxel-based automata approach provides a unique basis to model geospatial processes in 4D for the purpose of improving representation, analysis and understanding their spatiotemporal dynamics. This study contributes to the advancement of the concepts and framework of 4D GIS.
Vectorized multisite coding for hydrodynamic cellular automata
Simulating eight lattices for Pomeau's cellular automata simultaneously through bit-per-bit operations, a vectorized Fortran program reached 30 million updates per second and per Cray YMP processor. They authors give the full innermost loops
Reaction-Diffusion Automata Phenomenology, Localisations, Computation
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...
Tree automata-based refinement with application to Horn clause verification
Kafle, Bishoksan; Gallagher, John Patrick
rather than just transition systems; secondly, we show how algorithms manipulating tree automata interact with abstract interpretations, establishing progress in refinement and generating refined clauses that eliminate causes of imprecision. We show how to derive a refined set of Horn clauses in which...... given infeasible traces have been eliminated, using a recent optimised algorithm for tree automata determinisation. We also show how we can introduce disjunctive abstractions selectively by splitting states in the tree automaton. The approach is independent of the abstract domain and constraint theory...
Combinatorics of Boolean automata circuits dynamics
Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain
2012-01-01
International audience In line with fields of theoretical computer science and biology that study Boolean automata networks to model regulation networks, we present some results concerning the dynamics of networks whose underlying structures are oriented cycles, that is, Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work fo...
Line Complexity Asymptotics of Polynomial Cellular Automata
Stone, Bertrand
2016-01-01
Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols in the automaton are integers modulo some prime $p$. We are principally concerned with the asymptotic behavior of the line complexity sequence $a_T(k)$, which counts, for each $k$, the number of coefficient strings of length...
Efficient Induction of Finite State Automata
Collins, Matthew S.; Oliver, Jonathan
2013-01-01
This paper introduces a new algorithm for the induction if complex finite state automata from samples of behavior. The algorithm is based on information theoretic principles. The algorithm reduces the search space by many orders of magnitude over what was previously thought possible. We compare the algorithm with some existing induction techniques for finite state automata and show that the algorithm is much superior in both run time and quality of inductions.
Directed Percolation arising in Stochastic Cellular Automata
Regnault, Damien
2008-01-01
Cellular automata are both seen as a model of computation and as tools to model real life systems. Historically they were studied under synchronous dynamics where all the cells of the system are updated at each time step. Meanwhile the question of probabilistic dynamics emerges: on the one hand, to develop cellular automata which are capable of reliable computation even when some random errors occur; on the other hand, because synchronous dynamics is not a reasonable assumption to simulate re...
On the Behavior Characteristics of Cellular Automata
CHEN Jin-cai; ZHANG Jiang-ling; FENG Dan
2005-01-01
In this paper, the inherent relationships between the running regulations and behavior characteristics of cellular automata are presented; an imprecise taxonomy of such systems is put forward; the three extreme cases of stable systems are discussed; and the illogicalness of evolutional strategies of cellular automata is analyzed. The result is suitable for the emulation and prediction of behavior of discrete dynamics systems; especially it can be taken as an important analysis means of dynamic performance of complex networks.
Oestrus Detection in Dairy Cows using Automata Modelling and Diagnosis Techniques
Jónsson, Ragnar Ingi; Caponetti, Fabio; Blanke, Mogens;
2009-01-01
This paper addresses detection of oestrus in dairy cows using automata-based modelling and diagnosis. Measuring lying/standing behaviour of the cows by a sensor attached to the cows hindleg, lying/standing behaviour is modelled as a stochastic automaton. The paper introduces a cow's lying......-balance as a biologically inspired quantity describing how much the cow has been resting for a preceding period. A dynamic lying-balance model is identified from real data and the lying balance is used as input, together with lying/standing sensor measurements. Using different automata models for oestrus and...... non-oestrus conditions, with state transition probability densities identified from observations, diagnosis theory for stochastic automata is employed to obtain diagnoses of oestrus. The oestrus cases are detected using consistency based diagnosis on real data....
Discrete geodesics and cellular automata
Arrighi, Pablo
2015-01-01
This paper proposes a dynamical notion of discrete geodesics, understood as straightest trajectories in discretized curved spacetime. The notion is generic, as it is formulated in terms of a general deviation function, but readily specializes to metric spaces such as discretized pseudo-riemannian manifolds. It is effective: an algorithm for computing these geodesics naturally follows, which allows numerical validation---as shown by computing the perihelion shift of a Mercury-like planet. It is consistent, in the continuum limit, with the standard notion of timelike geodesics in a pseudo-riemannian manifold. Whether the algorithm fits within the framework of cellular automata is discussed at length. KEYWORDS: Discrete connection, parallel transport, general relativity, Regge calculus.
The Consensus Problem, Cellular Automata, and Self- replicating Structures
Griffin, David
2016-01-01
Over The course of the last four years I have researched the consensus problem. I have done so by studying how cellular automata following the 2DGKL rule are able to reach consensus in a verity of ways. There are only certain structures that can form within a network, and these structures can be described and examined directly from the rules that make them up. I have also explored a variety of methods to study the rule including, graph theory and liner algebra representations of the cellular ...
Formal languages, automata and numeration systems, v.2
Rigo, Michel
2014-01-01
The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi) or between combinatorics on words and number theory has paved the way to recent dramatic developments, for example, the transcendence results for the real numbers having a "simple" binary expansion, by B. Adamczewski and Y. Bugeaud. This book is at the heart of this interplay through a unified exposition. Objects are considered with a perspective that comes both from t
Cox, Brian N.; Snead, Malcolm L.
2016-02-01
We argue in favor of representing living cells as automata and review demonstrations that autonomous cells can form patterns by responding to local variations in the strain fields that arise from their individual or collective motions. An autonomous cell's response to strain stimuli is assumed to be effected by internally-generated, internally-powered forces, which generally move the cell in directions other than those implied by external energy gradients. Evidence of cells acting as strain-cued automata have been inferred from patterns observed in nature and from experiments conducted in vitro. Simulations that mimic particular cases of pattern forming share the idealization that cells are assumed to pass information among themselves solely via mechanical boundary conditions, i.e., the tractions and displacements present at their membranes. This assumption opens three mechanisms for pattern formation in large cell populations: wavelike behavior, kinematic feedback in cell motility that can lead to sliding and rotational patterns, and directed migration during invasions. Wavelike behavior among ameloblast cells during amelogenesis (the formation of dental enamel) has been inferred from enamel microstructure, while strain waves in populations of epithelial cells have been observed in vitro. One hypothesized kinematic feedback mechanism, "enhanced shear motility", accounts successfully for the spontaneous formation of layered patterns during amelogenesis in the mouse incisor. Directed migration is exemplified by a theory of invader cells that sense and respond to the strains they themselves create in the host population as they invade it: analysis shows that the strain fields contain positional information that could aid the formation of cell network structures, stabilizing the slender geometry of branches and helping govern the frequency of branch bifurcation and branch coalescence (the formation of closed networks). In simulations of pattern formation in
About the embedding of one dimensional cellular automata into hyperbolic cellular automata
Margenstern, Maurice
2010-01-01
In this paper, we look at two ways to implement determinisitic one dimensional cellular automata into hyperbolic cellular automata in three contexts: the pentagrid, the heptagrid and the dodecagrid, these tilings being classically denoted by $\\{5,4\\}$, $\\{7,3\\}$ and $\\{5,3,4\\}$ respectively.
Formal languages, automata and numeration systems introduction to combinatorics on words
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
Non deterministic finite automata for power systems fault diagnostics
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.
Infinite Runs in Weighted Timed Automata with Energy Constraints
Bouyer, Patricia; Fahrenberg, Uli; Larsen, Kim Guldstrand; Markey, Nicolas; Srba, Jiri
We study the problems of existence and construction of infinite schedules for finite weighted automata and one-clock weighted timed automata, subject to boundary constraints on the accumulated weight. More specifically, we consider automata equipped with positive and negative weights on transitions...... consider a game version of the above, where certain transitions may be uncontrollable....
Cellular automata with majority rule on evolving network
Makowiec, Danuta
2004-01-01
The cellular automata discrete dynamical system is considered as the two-stage process: the majority rule for the change in the automata state and the rule for the change in topological relations between automata. The influence of changing topology to the cooperative phenomena, namely zero-temperature ferromagnetic phase transition, is observed.
Infrared image enhancement using Cellular Automata
Qi, Wei; Han, Jing; Zhang, Yi; Bai, Lian-fa
2016-05-01
Image enhancement is a crucial technique for infrared images. The clear image details are important for improving the quality of infrared images in computer vision. In this paper, we propose a new enhancement method based on two priors via Cellular Automata. First, we directly learn the gradient distribution prior from the images via Cellular Automata. Second, considering the importance of image details, we propose a new gradient distribution error to encode the structure information via Cellular Automata. Finally, an iterative method is applied to remap the original image based on two priors, further improving the quality of enhanced image. Our method is simple in implementation, easy to understand, extensible to accommodate other vision tasks, and produces more accurate results. Experiments show that the proposed method performs better than other methods using qualitative and quantitative measures.
Minimization of Deterministic Fuzzy Tree Automata
S. Moghari
2014-03-01
Full Text Available Until now, some methods for minimizing deterministic fuzzy finite tree automata (DFFTA and weighted tree automata have been established by researchers. Those methods are language preserving, but the behavior of original automata and minimized one may be different. This paper, considers both language preserving and behavior preserving in minimization process. We drive Myhill-Nerode kind theorems corresponding to each proposed method and introduce PTIME algorithms for behaviorally and linguistically minimization. The proposed minimization algorithms are based on two main steps. The first step includes finding dependency between equivalency of states, according to the set of transition rules of DFFTA, and making merging dependency graph (MDG. The second step is refinement of MDG and making minimization equivalency set (MES. Additionally, behavior preserving minimization of DFFTA requires a pre-processing for modifying fuzzy membership grade of rules and final states, which is called normalization.
From equilibrium spin models to probabilistic cellular automata
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
Study of phase separation using liquid-gas model of lattice-gas cellular automata
This report describes the study of phase separation by the liquid gas model of lattice gas cellular automata. The lattice gas cellular automaton is one model for simulating fluid phenomena which was proposed by Frisch, Hasslacher and Pomeau in 1986. In 1990, Appert and Zaleski added a new long-range interaction to lattice gas cellular automata to construct a model, the liquid-gas model, which could simulate phase separation using lattice-gas cellular automata. Gerits et al formulated the liquid-gas model mathematically using the theory of statistical dynamics in 1993 and explained the mechanism of phase separation in the liquid-gas model using the equation of state. At first this report explains the FHP model of lattice gas cellular automata and derives fluid dynamics equations such as the equation of continuity and the Navier-Stokes equation. Then the equation of state for the liquid-gas model which was derived by Gerits et al is modified by adding the interactions which were proposed by Appert but not considered by Gerits et al. The modified equation of state is verified by the computer simulation using the liquid gas model. The relation between phase separation and the equation of state is discussed. (author)
Cellular automata and self-organized criticality
Creutz, Michael
1996-01-01
Cellular automata provide a fascinating class of dynamical systems capable of diverse complex behavior. These include simplified models for many phenomena seen in nature. Among other things, they provide insight into self-organized criticality, wherein dissipative systems naturally drive themselves to a critical state with important phenomena occurring over a wide range of length and time scales.
Automata Learning through Counterexample Guided Abstraction Refinement
Aarts, Fides; Heidarian, Faranak; Kuppens, Harco;
2012-01-01
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 even...
Bisimulations meet PCTL equivalences for probabilistic automata
Song, Lei; Zhang, Lijun; Godskesen, Jens Chr.; Nielson, Flemming
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...
Position Automata for Kleene Algebra with Tests
A. Silva
2012-01-01
Full Text Available Kleene algebra with tests (KAT is an equational system that combines Kleene and Boolean algebras. One can model basic programming constructs and assertions in KAT, which allowed for its application in compiler optimization, program transformation and dataflow analysis. To provide semantics for KAT expressions, Kozen first introduced emph{automata on guarded strings}, showing that the regular sets of guarded strings plays the same role in KAT as regular languages play in Kleene algebra. Recently, Kozen described an elegant algorithm, based on ``derivatives'', to construct a deterministic automaton that accepts the guarded strings denoted by a KAT expression. This algorithm generalizes Brzozowski's algorithm for regular expressions and inherits its inefficiency arising from the explicit computation of derivatives. In the context of classical regular expressions, many efficient algorithms to compile expressions to automata have been proposed. One of those algorithms was devised by Berry and Sethi in the 80's (we shall refer to it as Berry-Sethi construction/algorithm, but in the literature it is also referred to as position or Glushkov automata algorithm. In this paper, we show how the Berry-Sethi algorithm can be used to compile a $KAT$ expression to an automaton on guarded strings. Moreover, we propose a new automata model for KAT expressions and adapt the construction of Berry and Sethi to this new model.
Linear Parametric Model Checking of Timed Automata
Hune, Tohmas Seidelin; Romijn, Judi; Stoelinga, Mariëlle; Vaandrager, Frits W.
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...
Minimization of Fuzzy Finite Generalized Automata
无
2006-01-01
Some concepts in Fuzzy Generalized Automata (FGA) are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts: the first is called E-reduction which contracts equivalent states, and the second is called RE-reduction which removes retrievable states. Finally an example is given to illuminate the algorithm of minimization.
Two Phase Flow Simulation Using Cellular Automata
The classical mathematical treatment of two-phase flows is based on the average of the conservation equations for each phase.In this work, a complementary approach to the modeling of these systems based on statistical population balances of aut omata sets is presented.Automata are entities defined by mathematical states that change following iterative rules representing interactions with the neighborhood.A model of automata for two-phase flow simulation is presented.This model consists of fie lds of virtual spheres that change their volumes and move around a certain environment.The model is more general than the classical cellular automata in two respects: the grid of cellular automata is dismissed in favor of a trajectory generator, and the rules of interaction involve parameters representing the actual physical interactions between phases.Automata simulation was used to study unsolved two-phase flow problems involving high heat flux rates. One system described in this work consists of a vertical channel with saturated water at normal pressure heated from the lower surface.The heater causes water to boil and starts the bubble production.We used cellular automata to describe two-phase flows and the interaction with the heater.General rule s for such cellular automata representing bubbles moving in stagnant liquid were used, with special attention to correct modeling of different mechanisms of heat transfer.The results of the model were compared to previous experiments and correlations finding good agreement.One of the most important findings is the confirmation of Kutateladze's idea about a close relation between the start of critical heat flux and a change in the flow's topology.This was analyzed using a control volume located in the upper surface of the heater.A strong decrease in the interfacial surface just before the CHF start was encountered.The automata describe quite well some characteristic parameters such as the shape of the local void fraction in the
Solving multiconstraint assignment problems using learning automata.
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
Proceedings of Second International Symposium on Games, Automata, Logics and Formal Verification
D'Agostino, Giovanna; 10.4204/EPTCS.54
2011-01-01
This volume contains the Proceedings of the Second International Symposium on Games, Automata, Languages, and Formal Verification (GandALF 2011). The conference was held in Minori (Amalfi Coast, Italy), from the 15th to the 17th of June 2011. The aim of the GandALF Symposium is to provide a forum for researchers from different areas and with different background, that share a common interest in game theory, mathematical logic, automata theory, and their applications to the specification, design, and verification of complex systems. This proceedings contain the abstracts of three invited talks and nineteen regular papers that have been selected through a rigorous reviewing process according to originality, quality, and relevance to the topics of the symposium.
Neighborhood Selection and Rules Identification for Cellular Automata: A Rough Sets Approach
Placzek, Bartlomiej
2014-01-01
In this paper a method is proposed which uses data mining techniques based on rough sets theory to select neighborhood and determine update rule for cellular automata (CA). According to the proposed approach, neighborhood is detected by reducts calculations and a rule-learning algorithm is applied to induce a set of decision rules that define the evolution of CA. Experiments were performed with use of synthetic as well as real-world data sets. The results show that the introduced method allow...
Simultaneous Finite Automata: An Efficient Data-Parallel Model for Regular Expression Matching
Sin'ya, Ryoma; Matsuzaki, Kiminori; Sassa, Masataka
2014-01-01
Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automat...
Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 2
陶仁骥; 陈世华
2002-01-01
Semi-input-memory finite automata, a kind of finite automata introduced bythe author of this paper for studying error propagation, are a generalization of input-memoryfinite automata by appending an autonomous finite automaton component. This paper gives acharacterization on the structure of weakly invertible semi-input-memory finite automata withdelay 2 in which input alphabets and output alphabets have two elements and autonomousfinite automata are cyclic. For the structure of feedforward inverse finite automata with delay2, Zhu first gave a characterization; from a result on mutual invertibility of finite automata, theresult mentioned above also leads to a different characterization on the structure of feedforwardinverse finite automata with delay 2.
Deterministic recognizability of picture languages with Wang automata
V. Lonati; M. Pradella
2010-01-01
special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications International audience We present a model of automaton for picture language recognition, called Wang automaton, which is based on labeled Wang tiles. Wang automata combine features of both online tessellation acceptors and 4-way automata: as in online tessellation acceptors, computation assigns states to each picture position; as in 4-way automata, the input head visits the pictur...
Evolutionary Information Theory
Mark Burgin
2013-04-01
Full Text Available Evolutionary information theory is a constructive approach that studies information in the context of evolutionary processes, which are ubiquitous in nature and society. In this paper, we develop foundations of evolutionary information theory, building several measures of evolutionary information and obtaining their properties. These measures are based on mathematical models of evolutionary computations, machines and automata. To measure evolutionary information in an invariant form, we construct and study universal evolutionary machines and automata, which form the base for evolutionary information theory. The first class of measures introduced and studied in this paper is evolutionary information size of symbolic objects relative to classes of automata or machines. In particular, it is proved that there is an invariant and optimal evolutionary information size relative to different classes of evolutionary machines. As a rule, different classes of algorithms or automata determine different information size for the same object. The more powerful classes of algorithms or automata decrease the information size of an object in comparison with the information size of an object relative to weaker4 classes of algorithms or machines. The second class of measures for evolutionary information in symbolic objects is studied by introduction of the quantity of evolutionary information about symbolic objects relative to a class of automata or machines. To give an example of applications, we briefly describe a possibility of modeling physical evolution with evolutionary machines to demonstrate applicability of evolutionary information theory to all material processes. At the end of the paper, directions for future research are suggested.
Simulation of earthquakes with cellular automata
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.
Cellular Automata Studies of Vertical Silicon Devices
M. Saraniti; G. Zandler; G. Formicone; S. Goodnick
1998-01-01
We present systematic theoretical Cellular Automata (CA) studies of a novel nanometer scale Si device, namely vertically grown Metal Oxide Field Effect Transistors (MOSFET) with channel lengths between 65 and 120 nm. The CA simulations predict drain characteristics and output conductance as a function of gate length. The excellent agreement with available experimental data indicates a high quality oxide/semiconductor interface. Impact ionization is shown to be of minor importance. For inhomog...
Finite Automata with Generalized Acceptance Criteria
Timo Peichl; Heribert Vollmer
2001-01-01
We examine the power of nondeterministic finite automata with acceptance of an input word defined by a leaf language, i.e., a condition on the sequence of leaves in the automaton's computation tree. We study leaf languages either taken from one of the classes of the Chomsky hierarchy, or taken from a time- or space-bounded complexity class. We contrast the obtained results with those known for leaf languages for Turing machines and Boolean circuits.
Uncoupled Automata and Pure Nash Equilibria
Yakov Babichenko
2007-01-01
AbstractWe study the problem of reaching a pure Nash equilibrium in multi-person games that are repeatedly played under the assumption of uncoupledness: every player knows only his own payoff function. We consider strategies that can be implemented by finite-state automata, and characterize the minimal number of states needed in order to guarantee that a pure Nash equilibrium is reached in every game where such an equilibrium exists.
Decidable and undecidable problems about quantum automata
Blondel, V D; Koiran, P; Portier, N; Blondel, Vincent D.; Jeandel, Emmanuel; Koiran, Pascal; Portier, Natacha
2003-01-01
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
Modelling Cow Behaviour Using Stochastic Automata
Jónsson, Ragnar Ingi
2010-01-01
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 coinci...
The linearity of quantum mechanics from the perspective of Hamiltonian cellular automata
Elze, Hans-Thomas
2014-01-01
We discuss the action principle and resulting Hamiltonian equations of motion for a class of integer-valued cellular automata introduced recently [1]. Employing sampling theory, these deterministic finite-difference equations are mapped reversibly on continuum equations describing a set of bandwidth limited harmonic oscillators. They represent the Schroedinger equation. However, modifications reflecting the bandwidth limit are incorporated, i.e., the presence of a time (or length) scale. When this discreteness scale is taken to zero, the usual results are obtained. Thus, the linearity of quantum mechanics can be traced to the postulated action principle of such cellular automata and its conservation laws to discrete ones. The cellular automaton conservation laws are in one-to-one correspondence with those of the related quantum mechanical model, while admissible symmetries are not.
The linearity of quantum mechanics from the perspective of Hamiltonian cellular automata
We discuss the action principle and resulting Hamiltonian equations of motion for a class of integer-valued cellular automata introduced recently [1]. Employing sampling theory, these deterministic finite-difference equations are mapped reversibly on continuum equations describing a set of bandwidth limited harmonic oscillators. They represent the Schrödinger equation. However, modifications reflecting the bandwidth limit are incorporated, i.e., the presence of a time (or length) scale. When this discreteness scale is taken to zero, the usual results are obtained. Thus, the linearity of quantum mechanics can be traced to the postulated action principle of such cellular automata and its conservation laws to discrete ones. The cellular automaton conservation laws are in one-to-one correspondence with those of the related quantum mechanical model, while admissible symmetries are not.
Reversible Multi-Head Finite Automata Characterize Reversible Logarithmic Space
Axelsen, Holger Bock
2012-01-01
Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs ...
Input-Trees of Finite Automata and Application to Cryptanalysis
陶仁骥; 陈世华
2000-01-01
In this paper, weights of output set and of input set for finite automata are discussed. For a weakly invertible finite automaton, we prove that for states with minimal output weight, the distribution of input sets is uniform. Then for a kind of compound finite automata, we give weights of output set and of input set explicitly, and a characterization of their input-trees. For finite automaton public key cryptosystems, of which automata in public keys belong to such a kind of compound finite automata, we evaluate search amounts of exhaust search algorithms in average case and in worse case for both encryption and signature, and successful probabilities of stochastic search algorithms for both encryption and signature. In addition, a result on mutual invertibility of finite automata is also given.
陈永; 王晓明; 党建武
2012-01-01
交通运输能源消耗已经成为决策管理者高度关注的信息.采用元胞自动机(CA)理论研究了快速公交系统能耗问题,以元胞自动机NaSch交通流模型为基础,通过结合动能定理,建立了快速公交系统的元胞自动机能耗动力学仿真模型.并以目前建设的兰州市快速公交系统为例,仿真研究了周期性边界条件下,不同行车密度、不同停靠站时间以及驾驶员行为差异下随机慢化对快速公交车系统能耗的影响,得到了相应的定量分析结论.仿真结果表明,快速公交车辆停靠站时间越长,拥堵的范围越大,路面交通流能耗损失越小,对应的流量、速度也越小,系统越早进入堵塞相.%Transportation energy consumption has aroused high attention of the decision-makers. In this case, an energy consumption of Bus Rapid Transit (BRT) Cellular Automata (CA) model was designed, which was based on NaSch traffic model and Kinetic energy theorem. Taking Lanzhou city bus rapid transit traffic system as an example, the effects of BRT vehicle random slowness in the different traffic density, different road condition and drivers' behavior under periodic boundary conditions was studied. And corresponding quantitative analysis conclusion was get. The simulation results show that the rapid transit vehicle stops longer, the greater the range of congestion and the smaller the energy loss of the road traffic flow. Besides, the corresponding flow rate is also smaller, thus the system is plugged into congestion phase earlier.
Edit Distance for Timed Automata
Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Majumdar, Rupak
2013-01-01
The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define ...
Synchronous composition of interval weighted automata
Komenda, Jan; Lahaye, S.; Boimond, J.-L.
Berlin: The International Federation of Automatic Control, 2010 - (Raisch, J.; Giua, A.; Lafortune, S.; Moor, T.), s. 328-333 ISBN 978-3-902661-79-1. [10th International Workshop on Discrete Event Systems. Berlin (DE), 29.08.2010-01.09.2010] Grant ostatní: EU Projekt(XE) EU. ICT .DISC 224498 Institutional research plan: CEZ:AV0Z10190503 Keywords : timed discrete-event systems * product interval automata * T-time Petri nets * synchronous composition Subject RIV: BA - General Mathematics http://www.ifac-papersonline.net/Detailed/42947.html
Cellular automata modelling of hantarvirus infection
Hantaviruses are a group of viruses which have been identified as being responsible for the outbreak of diseases such as the hantavirus pulmonary syndrome. In an effort to understand the characteristics and dynamics of hantavirus infection, mathematical models based on differential equations have been developed and widely studied. However, such models neglect the local characteristics of the spreading process and do not include variable susceptibility of individuals. In this paper, we develop an alternative approach based on cellular automata to analyze and study the spatiotemporal patterns of hantavirus infection.
Cellular automata modelling of hantarvirus infection
Abdul Karim, Mohamad Faisal [School of Distance Education, Universiti Sains Malaysia, Minden 11800, Penang (Malaysia)], E-mail: faisal@usm.my; Md Ismail, Ahmad Izani [School of Mathematical Sciences, Universiti Sains Malaysia, Minden 11800, Penang (Malaysia)], E-mail: izani@cs.usm.my; Ching, Hoe Bee [School of Mathematical Sciences, Universiti Sains Malaysia, Minden 11800, Penang (Malaysia)], E-mail: Bee_Ching_Janice_Hoe@dell.com
2009-09-15
Hantaviruses are a group of viruses which have been identified as being responsible for the outbreak of diseases such as the hantavirus pulmonary syndrome. In an effort to understand the characteristics and dynamics of hantavirus infection, mathematical models based on differential equations have been developed and widely studied. However, such models neglect the local characteristics of the spreading process and do not include variable susceptibility of individuals. In this paper, we develop an alternative approach based on cellular automata to analyze and study the spatiotemporal patterns of hantavirus infection.
Quantumness of discrete Hamiltonian cellular automata
Elze Hans-Thomas
2014-01-01
Full Text Available We summarize a recent study of discrete (integer-valued Hamiltonian cellular automata (CA showing that their dynamics can only be consistently defined, if it is linear in the same sense as unitary evolution described by the Schrödinger equation. This allows to construct an invertible map between such CA and continuous quantum mechanical models, which incorporate a fundamental scale. Presently, we emphasize general aspects of these findings, the construction of admissible CA observables, and the existence of solutions of the modified dispersion relation for stationary states.
Learn with SAT to Minimize Büchi Automata
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.
Recursive definition of global cellular-automata mappings
Feldberg, Rasmus; Knudsen, Carsten; Rasmussen, Steen
1994-01-01
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 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...
Operational State Complexity of Deterministic Unranked Tree Automata
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.
A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata
Borello, Alex
2010-01-01
In this paper, we present the simulation of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head one-way finite automata and is characterized by having its heads moving only forward, on a trajectory that only depends on the length of the input. While the original finite automaton works in linear time, its corresponding cellular automaton performs the same task in real time, that is, exactly the length of the input. Although not truly a speed-up, the simulation may be interesting and reminds us of the open question about the equivalence of linear and real times on cellular automata.
Relation between coined quantum walks and quantum cellular automata
Hamada, M; Segawa, E; Hamada, Masatoshi; Konno, Norio; Segawa, Etsuo
2004-01-01
Motivated by the recent work of Patel et al., this letter clarifies a connection between coined quantum walks and quantum cellular automata in a general setting. As a consequence, their result is naturally derived from the connection.
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
Holzer, Markus; 10.4204/EPTCS.1.9
2009-01-01
Multi-head finite automata were introduced in (Rabin, 1964) and (Rosenberg, 1966). Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature.
On the number of attractors of Boolean automata circuits
Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain
2009-01-01
In line with fields of theoretical computer science and biology that study Boolean automata networks often seen as models of regulation networks, we present some results concerning the dynamics of networks whose underlying interaction graphs are circuits, that is Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work focuses on th...
Performance analysis of probabilistic timed automata using digital clocks
M. Kwiatkowska; G Norman; Parker, D.; Sproston, J.
2006-01-01
Probabilistic timed automata, a variant of timed automata extended with discrete probability distributions, is a modelling formalism suitable for describing formally both nondeterministic and probabilistic aspects of real-time systems, and is amenable to model checking against probabilistic timed temporal logic properties. However, the previously developed verification algorithms either suffer from high complexity, give only approximate results, or are restricted to a limited class of propert...
Achieving of Fuzzy Automata for Processing Fuzzy Logic
SHU Lan; WU Qing-e
2005-01-01
At present, there has been an increasing interest in neuron-fuzzy systems, the combinations of artificial neural networks with fuzzy logic. In this paper, a definition of fuzzy finite state automata (FFA) is introduced and fuzzy knowledge equivalence representations between neural networks, fuzzy systems and models of automata are discussed. Once the network has been trained, we develop a method to extract a representation of the FFA encoded in the recurrent neural network that recognizes the training rules.
Simulation of Two-Way Pushdown Automata Revisited
Robert Glück
2013-01-01
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 arg...
Resource-Optimal Scheduling Using Priced Timed Automata
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 progr......-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....
Modelling Cow Behaviour Using Stochastic Automata
Jónsson, Ragnar Ingi
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......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...... hour suplying with information on which hour of the day it is and lastly modelling the general activity level. Diagnosis algorithms for the three approaches are implemented and tested using the real data measurements and show that the diagnosis algorithm can distinguish between data belonging to...
Traffic jam dynamics in stochastic cellular automata
Nagel, K. [Los Alamos National Lab., NM (United States)]|[Santa Fe Inst., NM (United States); Schreckenberg, M. [Univ. Duisburg (Germany)
1995-09-01
Simple models for particles hopping on a grid (cellular automata) are used to simulate (single lane) traffic flow. Despite their simplicity, these models are astonishingly realistic in reproducing start-stop-waves and realistic fundamental diagrams. One can use these models to investigate traffic phenomena near maximum flow. A so-called phase transition at average maximum flow is visible in the life-times of jams. The resulting dynamic picture is consistent with recent fluid-dynamical results by Kuehne/Kerner/Konhaeuser, and with Treiterer`s hysteresis description. This places CA models between car-following models and fluid-dynamical models for traffic flow. CA models are tested in projects in Los Alamos (USA) and in NRW (Germany) for large scale microsimulations of network traffic.
On Tree Pattern Matching by Pushdown Automata
T. Flouri
2009-01-01
Full Text Available Tree pattern matching is an important operation in Computer Science on which a number of tasks such as mechanical theorem proving, term-rewriting, symbolic computation and non-procedural programming languages are based on. Work has begun on a systematic approach to the construction of tree pattern matchers by deterministic pushdown automata which read subject trees in prefix notation. The method is analogous to the construction of string pattern matchers: for given patterns, a non-deterministic pushdown automaton is created and then it is determinised. In this first paper, we present the proposed non-deterministic pushdown automaton which will serve as a basis for the determinisation process, and prove its correctness.
Computing by Temporal Order: Asynchronous Cellular Automata
Michael Vielhaber
2012-08-01
Full Text Available Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case, under all possible update rules (asynchronicity. Over the torus Z/nZ (n<= 11,we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule. We furthermore show that all even (element of the alternating group bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.
Simulating Complex Systems by Cellular Automata
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...
Particles and Patterns in Cellular Automata
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
A cellular automata model for ant trails
Sibel Gokce; Ozhan Kayacan
2013-05-01
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 (i) ant colony consists of two kinds of ants, goodand poor-smelling ants, (ii) ants might make U-turn for some special reasons. For some values of densities of good- and poor-smelling ants, the flux and mean velocity of the colony were studied as a function of density and evaporation rate of pheromone.
Knowledge discovery for geographical cellular automata
LI; Xia; Anthony; Gar-On; Yeh
2005-01-01
This paper proposes a new method for geographical simulation by applying data mining techniques to cellular automata. CA has strong capabilities in simulating complex systems. The core of CA is how to define transition rules. There are no good methods for defining these transition rules. They are usually defined by using heuristic methods and thus subject to uncertainties. Mathematical equations are used to represent transition rules implicitly and have limitations in capturing complex relationships. This paper demonstrates that the explicit transition rules of CA can be automatically reconstructed through the rule induction procedure of data mining. The proposed method can reduce the influences of individual knowledge and preferences in defining transition rules and generate more reliable simulation results. It can efficiently discover knowledge from a vast volume of spatial data.
SELF-ORGANIZED CRITICALITY AND CELLULAR AUTOMATA
CREUTZ,M.
2007-01-01
Cellular automata provide a fascinating class of dynamical systems based on very simple rules of evolution yet capable of displaying highly complex behavior. These include simplified models for many phenomena seen in nature. Among other things, they provide insight into self-organized criticality, wherein dissipative systems naturally drive themselves to a critical state with important phenomena occurring over a wide range of length and the scales. This article begins with an overview of self-organized criticality. This is followed by a discussion of a few examples of simple cellular automaton systems, some of which may exhibit critical behavior. Finally, some of the fascinating exact mathematical properties of the Bak-Tang-Wiesenfeld sand-pile model [1] are discussed.
Integral Imaging Based 3-D Image Encryption Algorithm Combined with Cellular Automata
Li, X. W.; Kim, D. H.; Cho, S. J.; Kim, S. T.
2013-01-01
A novel optical encryption method is proposed in this paper to achieve 3-D image encryption. This proposed encryption algorithm combines the use of computational integral imaging (CII) and linear-complemented maximum- length cellular automata (LC-MLCA) to encrypt a 3D image. In the encryption process, the 2-D elemental image array (EIA) recorded by light rays of the 3-D image are mapped inversely through the lenslet array according the ray tracing theory. Next, the 2-D EIA is encrypted by LC-...
Blazquez, J.S.; Millan, M.; Conde, C.F.; Conde, A. [Departamento de Fisica de la Materia Condensada, Universidad de Sevilla-ICMSE, P.O. Box 1065, 41080 Sevilla (Spain)
2010-05-15
Nanocrystallization kinetics is analyzed in the frame of instantaneous growth approximation, which implies that the time required for a crystallite to reach its final size is negligible with respect to the time required for the nanocrystallization process. This approach strongly simplifies the kinetic analysis and allows us to obtain the nucleation rate from both isothermal and non-isothermal nanocrystallization processes. Moreover, as no constraining mechanism is considered but the absence of growth, the results could be discussed in the frame of Johnson-Mehl-Avrami-Kolmogorov theory with a growth index equal to zero. Cellular automata simulations are in agreement with the observed kinetics and microstructure. (Abstract Copyright [2010], Wiley Periodicals, Inc.)
A Simulation of Oblivious Multi-head One-way Finite Automata by Real-time Cellular Automata
Borello, Alex
2010-01-01
In this paper, we present the simulation of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head one-way finite automata and is characterized by having its heads moving only forward, on a trajectory that only depends on the length of the input. While the original finite automaton works in linear time, its corresponding cellular automaton performs the same task in real time, that is, exactly the length of the input. Alt...
Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata
Abdelaziz Fellah; Zachary Friggstad; Soufiane Noureddine
2007-01-01
Timed Alternating Finite Automata (TAFA), a natural generalization of Timed Finite Automata (TFA), are synchronous and powerful models for real-time computations. They become an effective and expressive model for developing embedded systems with real-time constraint computations which are required in many applications. We introduce Deterministic Timed Alternating Finite Automata (DTAFA), a new class of timed alternating finite automata, extended with a finite set of restricted and mutually ex...
Automata over a binary alphabet generating free groups of even rank
Steinberg, Benjamin; Vorobets, Mariya; Vorobets, Yaroslav
2006-01-01
We construct automata over a binary alphabet with $2n$ states, $n\\geq 2$, whose states freely generate a free group of rank $2n$. Combined with previous work, this shows that a free group of every finite rank can be generated by finite automata over a binary alphabet. We also construct free products of cyclic groups of order two via such automata.
Two-tape finite automata with quantum and classical states
Zheng, Shenggen; Qiu, Daowen
2011-01-01
{\\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and {\\it two-way two-tape deterministic finite automata} (2TFA) were introduced by Rabin and Scott. In this paper we study 2TFA and propose a new computing model called {\\it two-way two-tape finite automata with quantum and classical states} (2TQCFA). First, we give efficient 2TFA algorithms for recognizing languages which can be recognized by 2QCFA. Second, we give efficient 2TQCFA algorithms to recognize several languages whose status vis-a-vis 2QCFA have been posed as open questions, such as $L_{square}=\\{a^{n}b^{n^{2}}\\mid n\\in \\mathbf{N}\\}$. Third, we show that $\\{a^{n}b^{n^{k}}\\mid n\\in \\mathbf{N}\\}$ can be recognized by {\\it $(k+1)$-tape deterministic finite automata} ($(k+1)$TFA). Finally, we introduce {\\it $k$-tape automata with quantum and classical states} ($k$TQCFA) and prove that $\\{a^{n}b^{n^{k}}\\mid n\\in \\mathbf{N}\\}$ can be recognized by $k$TQCFA.
Cellular automata modelling of biomolecular networks dynamics.
Bonchev, D; Thomas, S; Apte, A; Kier, L B
2010-01-01
The modelling of biological systems dynamics is traditionally performed by ordinary differential equations (ODEs). When dealing with intracellular networks of genes, proteins and metabolites, however, this approach is hindered by network complexity and the lack of experimental kinetic parameters. This opened the field for other modelling techniques, such as cellular automata (CA) and agent-based modelling (ABM). This article reviews this emerging field of studies on network dynamics in molecular biology. The basics of the CA technique are discussed along with an extensive list of related software and websites. The application of CA to networks of biochemical reactions is exemplified in detail by the case studies of the mitogen-activated protein kinase (MAPK) signalling pathway, the FAS-ligand (FASL)-induced and Bcl-2-related apoptosis. The potential of the CA method to model basic pathways patterns, to identify ways to control pathway dynamics and to help in generating strategies to fight with cancer is demonstrated. The different line of CA applications presented includes the search for the best-performing network motifs, an analysis of importance for effective intracellular signalling and pathway cross-talk. PMID:20373215
Cellular automata modeling of cooperative eutectic growth
E. Olejnik
2010-01-01
Full Text Available The model and results of the 2D simulation of the cooperative growth of two phases in the lamellar eutectic are presented. The pro-posed model takes into account heat transfer, components diffusion and nonstationary concentration distribution in the liquid and solid phases, non-equlibrium nature of the phase transformation and kinetics of the growth, influence of the surface energy and interface curva-ture on the conditions of the thermodynamic equilibrium. For the determination of the phase interface shape the Cellular Automata tech-nique (CA was used. For the calculation of temperature and concentration distribution the numerical solution of the Fourier equation was used. The partial differential equations were solved by Finite Differences Method (FDM. The spatial position and cell sizes of CA lattice and FDM mesh are equal.Proposed model can predict the steady state growth with a constant interlamellar spacing in the regular plate eutectic, as well as some transient processes that bring to the changes of that parameters. Obtained simulation data show the solid-liquid interface changes result in the termination of lamella and enlargement of interlamellar spacing. Another simulation results illustrate a pocket formation in the center of one phase that forestalls nucleation (or intergrowth of the new lamellae of another phase. The data of the solidification study of the transparent material (CBr4 – 8,4% C2Cl6 obtained in the thin layer demonstrate the qualita-tive agreement of the simulation.
Minimum-Cost Reachability for Priced Timed Automata
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....
Simulation of Two-Way Pushdown Automata Revisited
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.
The brittleness model of complex system based on cellular automata
LIN De-ming; JIN Hong-zhang; LI Qi; WU Hong-mei
2004-01-01
Now the research on the complex system is a hot spot. Brittleness is one of the basic characteristics of a complex system. In a complex system, after one of subsystems is struck to be collapsed, the whole system will collapse. Meanwhile, cellular automata is a discrete dynamic system. When the rule is given, the cellular automata could be defined. Then it can imitate the complex action. Cellular automata is used to simulate the brittleness action in this study. Entropy was used to analyze the action and get the rule. Then,three normal brittleness models were given. The result shows that the brittleness of complex system is existent and in addition some important behavior mode of complex system brittleness has been achieved.
Design of the Sequential System Automata using Temporal Equivalence Classes
A. Ursu
1997-10-01
Full Text Available A design method of sequential system automata using temporal logic specifications is proposed in this paper. The method is based on well-known Z.Manna and P.Wolper temporal logic satisfiability analysis procedure [1] and is extended to include past time temporal operators. A new specification method which uses temporal equivalence classes is proposed to specify the behaviour of large digital circuits. The impact of the composition and decomposition operations of the temporal equivalence classes on the final automata has been studied. A case study is carried out which deals with the design of the synchronous bus arbiter circuit element. The SMV tool has been used to verify the temporal properties of the obtained automata.
Timed-Arc Petri Nets vs. Networks of Timed Automata
Srba, Jiri
We establish mutual translations between the classes of 1-safe timed-arc Petri nets (and its extension with testing arcs) and networks of timed automata (and its subclass where every clock used in the guard has to be reset). The presented translations are very tight (up to isomorphism of labelled...... transition systems with time). This provides a convenient characterization from the theoretical point of view but is not always satisfactory from the practical point of view because of the possible non-polynomial blow up in the size (in the direction from automata to nets). Hence we relax the isomorphism...... corollary of the presented reductions is a new PSPACE-completeness result for reachability in 1-safe timed-arc Petri nets, reusing the region/zone techniques already developed for timed automata....
Optimal Conditional Reachability for Multi-Priced Timed Automata
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...... cost of reaching a given target state, with respect to some primary cost variable, while respecting upper bound constraints on the remaining (secondary) cost variables. Decidability is proven by constructing a zone-based algorithm that always terminates while synthesizing the optimal cost with a single...
Turing degrees of limit sets of cellular automata
Borello, Alex; Cervelle, Julien; Vanier, Pascal
2014-01-01
Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of preimages. It is well known that these always contain a computable point and that any non-trivial property on them is undecidable. We go one step further in this article by giving a full characterization of the sets of Turing degrees of cellular automata: they are the same as the sets of Turing degrees of effectively c...
Lattice gas cellular automata and lattice Boltzmann models an introduction
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.
Path-equivalent developments in acyclic weighted automata
Giraud, Mathieu; Veber, Philippe; Lavenier, Dominique
2007-01-01
Weighted ﬁnite automata (WFA) are used with FPGA accelerating hardware to scan large genomic banks. Hardwiring such automata raises surface area and clock frequency constraints, requiring eﬃcient ε-transitions-removal techniques. In this paper, we present bounds on the number of new transitions for the development of acyclic WFA, which is a special case of the ε-transitions-removal problem. We introduce a new problem, a partial removal of ε-transitions while accepting short chains of ε-transi...
Implementation of Automata Theory to Improve the Learning Disability
Ali, Syed Asif; Soomro, Safeeullah; Memon, Abdul Ghafoor; Baqi, Abdul
2013-01-01
There are various types of disability egress in world like blindness, deafness, and Physical disabilities. It is quite difficult to deal with people with disability. Learning disability (LD) is types of disability totally different from general disability. To deal children with learning disability is difficult for both parents and teacher. As parent deal with only single child so it bit easy. But teacher deals with different students at a time so its more difficult to deal with group of stude...
Supervisory control of (max,+) automata: extensions towards applications
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.654, year: 2014 http://www.tandfonline.com/doi/full/10.1080/00207179.2015.1048295
Team Automata for Security Analysis of Multicast/Broadcast Communication
Beek, ter Maurice; Lenzini, Gabriele; Petrocchi, Marinella; Busi, N.; Gorrieri, R.; Martinelli, F.
2003-01-01
We show that team automata (TA) are well suited to model secure multicast/broadcast communication with possible packet loss. This is a consequence of the natural way in which one-to-many (one-to-all) transmissions typical of multicast (broadcast) sessions can be modelled as communications between th
Modelling and simulating in-stent restenosis with complex automata
A.G. Hoekstra; P. Lawford; R. Hose
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 s
Cellular automata simulation of nanometre-scale MOSFETs
Saraniti, M.; Zandler, G.; Formicone, G.; Wigger, S.; Goodnick, S.
1998-08-01
We present systematic theoretical cellular automata studies of vertically grown, nanometre-scale, MOSFETs. The predicted drain characteristics and output conductance are in excellent agreement with experimental data from fabricated devices. The inclusion of an inhomogeneous p-doping profiles along the channel is investigated, which is shown to improve current saturation and therefore allows the reduction of the device dimensions.
Supervisory Control of (max,+) automata: a behavioral approach
Komenda, Jan; Lahaye, S.; Boimond, J.-L.
2009-01-01
Roč. 19, č. 4 (2009), s. 525-549. ISSN 0924-6703 Grant ostatní: 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
Modeling diffusion of innovations with probabilistic cellular automata
Boccara, Nino; Fuks, Henryk
1997-01-01
We present a family of one-dimensional cellular automata modeling the diffusion of an innovation in a population. Starting from simple deterministic rules, we construct models parameterized by the interaction range and exhibiting a second-order phase transition. We show that the number of individuals who eventually keep adopting the innovation strongly depends on connectivity between individuals.
Using a satisfiability solver to identify deterministic finite state automata
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 p
Computer generation of initial spatial distribution for cell automata
GuangHua Liu; WenJun Zhang
2011-01-01
The algorithm to generate spatial distribution patterns was developed and presented in this study. Three typical spatial distribution patterns, i.e., Poisson distribution, binomial distribution, and negative binomial distribution were included in the algorithm. The Java program was also provided. The algorithm can be used to generate initial distribution in cell automata modeling.
On reversibility of cellular automata with periodic boundary conditions
Nobe, Atsushi [Graduate School of Engineering Science, Osaka University, Machikaneyama-cho 1-3, Toyonaka, Osaka 560-8531 (Japan); Yura, Fumitaka [Imai Quantum Computing and Information Project, ERATO, JST, Daini Hongo White Bldg 201, 5-28-3 Hongo, Bunkyo, Tokyo 113-0033 (Japan)
2004-06-04
Reversibility of one-dimensional cellular automata with periodic boundary conditions is discussed. It is shown that there exist exactly 16 reversible elementary cellular automaton rules for infinitely many cell sizes by means of a correspondence between elementary cellular automaton and the de Bruijn graph. In addition, a sufficient condition for reversibility of three-valued and two-neighbour cellular automaton is given.
Automata in SageMath---Combinatorics meet Theoretical Computer Science
Heuberger, Clemens; Krenn, Daniel; Kropf, Sara
2014-01-01
The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the asymptotic Hamming weight of a non-adjacent-form-like digit expansion, which was not known before.
Reachability analysis for timed automata using max-plus algebra
Lu, Qi; Madsen, Michael; Milata, Martin; Ravn, Søren; Fahrenberg, Uli; Larsen, Kim Guldstrand
2012-01-01
We show that max-plus polyhedra are usable as a data structure in reachability analysis of timed automata. Drawing inspiration from the extensive work that has been done on difference bound matrices, as well as previous work on max-plus polyhedra in other areas, we develop the algorithms needed t...
Boolean linear differential operators on elementary cellular automata
Martín Del Rey, Ángel
2014-12-01
In this paper, the notion of boolean linear differential operator (BLDO) on elementary cellular automata (ECA) is introduced and some of their more important properties are studied. Special attention is paid to those differential operators whose coefficients are the ECA with rule numbers 90 and 150.
Comprehensive bidding strategies with genetic programming/finite state automata
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
Return of the Quantum Cellular Automata: Episode VI
Carr, Lincoln D.; Hillberry, Logan E.; Rall, Patrick; Halpern, Nicole Yunger; Bao, Ning; Montangero, Simone
2016-05-01
There are now over 150 quantum simulators or analog quantum computers worldwide. Although exploring quantum phase transitions, many-body localization, and the generalized Gibbs ensemble are exciting and worthwhile endeavors, there are totally untapped directions we have not yet pursued. One of these is quantum cellular automata. In the past a principal goal of quantum cellular automata was to reproduce continuum single particle quantum physics such as the Schrodinger or Dirac equation from simple rule sets. Now that we begin to really understand entanglement and many-body quantum physics at a deeper level, quantum cellular automata present new possibilities. We explore several time evolution schemes on simple spin chains leading to high degrees of quantum complexity and nontrivial quantum dynamics. We explain how the 256 known classical elementary cellular automata reduce to just a few exciting quantum cases. Our analysis tools include mutual information based complex networks as well as more familiar quantifiers like sound speed and diffusion rate. Funded by NSF and AFOSR.
Cellular automata-based artificial life system of horizontal gene transfer
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.
A federation of simulations based on cellular automata in cyber-physical systems
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.
Definition and evolution of quantum cellular automata with two qubits per cell
Karafyllidis, Ioannis G.
2008-01-01
Studies of quantum computer implementations suggest cellular quantum computer architectures. These architectures can simulate the evolution of quantum cellular automata, which can possibly simulate both quantum and classical physical systems and processes. It is however known that except for the trivial case, unitary evolution of one-dimensional homogeneous quantum cellular automata with one qubit per cell is not possible. Quantum cellular automata that comprise two qubits per cell are define...
Automata for the verification of monadic second-order graph properties
Courcelle, Bruno; Durand, Irène
2012-01-01
The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. These automata recognize the terms over fixed finite signatures that define graphs satisfying the given sentences. However, this construction produces automata of hyper-exponential sizes, and is thus impossible to use in practice in many cases. To overcome this difficulty, we prop...
Using Learning Automata in Coordination Among Heterogeneous Agents in a Complex Multi-Agent Domain
Mohammadreza Khojasteh; Aida Kazimi
2012-01-01
This paper describes our use of Learning Automata as a reinforcement learning method in coordination among three heterogeneous teams of agents acting in RoboCup Rescue Simulation environment. We provide a brief introduction to Learning Automata and Cellular Learning Automata, the reinforcement machine learning methods that we have used in lots of parts of our agents’ development. Then we will describe the major challenges each team of agents should be concerned about in such a complex domain ...
A note on limited pushdown alphabets in stateless deterministic pushdown automata
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
Evolutionary Information Theory
Mark Burgin
2013-01-01
Evolutionary information theory is a constructive approach that studies information in the context of evolutionary processes, which are ubiquitous in nature and society. In this paper, we develop foundations of evolutionary information theory, building several measures of evolutionary information and obtaining their properties. These measures are based on mathematical models of evolutionary computations, machines and automata. To measure evolutionary information in an invariant form, we const...
Construction of living cellular automata using the Physarum plasmodium
Shirakawa, Tomohiro; Sato, Hiroshi; Ishiguro, Shinji
2015-04-01
The plasmodium of Physarum polycephalum is a unicellular and multinuclear giant amoeba that has an amorphous cell body. To clearly observe how the plasmodium makes decisions in its motile and exploratory behaviours, we developed a new experimental system to pseudo-discretize the motility of the organism. In our experimental space that has agar surfaces arranged in a two-dimensional lattice, the continuous and omnidirectional movement of the plasmodium was limited to the stepwise one, and the direction of the locomotion was also limited to four neighbours. In such an experimental system, a cellular automata-like system was constructed using the living cell. We further analysed the exploratory behaviours of the plasmodium by duplicating the experimental results in the simulation models of cellular automata. As a result, it was revealed that the behaviours of the plasmodium are not reproduced by only local state transition rules; and for the reproduction, a kind of historical rule setting is needed.
On the secure obfuscation of deterministic finite automata.
Anderson, William Erik
2008-06-01
In this paper, we show how to construct secure obfuscation for Deterministic Finite Automata, assuming non-uniformly strong one-way functions exist. We revisit the software protection approaches originally proposed by [5, 10, 12, 17] and revise them to the current obfuscation setting of Barak et al. [2]. Under this model, we introduce an efficient oracle that retains some 'small' secret about the original program. Using this secret, we can construct an obfuscator and two-party protocol that securely obfuscates Deterministic Finite Automata against malicious adversaries. The security of this model retains the strong 'virtual black box' property originally proposed in [2] while incorporating the stronger condition of dependent auxiliary inputs in [15]. Additionally, we show that our techniques remain secure under concurrent self-composition with adaptive inputs and that Turing machines are obfuscatable under this model.
Generalized Cayley Graphs and Cellular Automata over them
Arrighi, Pablo; Nesme, Vincent
2012-01-01
Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their equality; to name all vertices relative to a point; the fact that they have a well-defined notion of translation, and that they can be endowed with a compact metric. We propose a notion of graph associated to a language, which conserves or generalizes these features. Whereas Cayley graphs are regular; associated graphs are arbitrary, although of a bounded degree. Moreover, it is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions for a distance on the set of configurations that makes it a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Similarly, we extend their definition to these arbitrary, bounded degree, time-varying graphs. KEYWORDS: Causal Graph Dynamics, Curtis-Hedlund-Lynden, Dynamical networks, Boolean networks, Generative networks automata, Graph Autom...
Station Model for Rail Transit System Using Cellular Automata
XUN Jing; NING Bin; LI Ke-Ping
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.
Quantum dot spin cellular automata for realizing a quantum processor
We show how single quantum dots, each hosting a singlet–triplet qubit, can be placed in arrays to build a spin quantum cellular automaton. A fast (∼10 ns) deterministic coherent singlet–triplet filtering, as opposed to current incoherent tunneling/slow-adiabatic based quantum gates (operation time ∼300 ns), can be employed to produce a two-qubit gate through capacitive (electrostatic) couplings that can operate over significant distances. This is the coherent version of the widely discussed charge and nano-magnet cellular automata, and would increase speed, reduce dissipation, and perform quantum computation while interfacing smoothly with its classical counterpart. This combines the best of two worlds—the coherence of spin pairs known from quantum technologies, and the strength and range of electrostatic couplings from the charge-based classical cellular automata. Significantly our system has zero electric dipole moment during the whole operation process, thereby increasing its charge dephasing time. (paper)
From Boolean logic to switching circuits and automata. Towards modern information technology
Stankovic, Radomir S. [Nis Univ. (RS). Dept. of Computer Science; Astola, Jaakko [Tampere Univ. of Technology (Finland). Dept. of Signal Processing
2011-07-01
Logic networks and automata are facets of digital systems. The change of the design of logic networks from skills and art into a scientific discipline was possible by the development of the underlying mathematical theory called the Switching Theory. The fundamentals of this theory come from the attempts towards an algebraic description of laws of thoughts presented in the works by George J. Boole and the works on logic by Augustus De Morgan. As often the case in engineering, when the importance of a problem and the need for solving it reach certain limits, the solutions are searched by many scholars in different parts of the word, simultaneously or at about the same time, however, quite independently and often unaware of the work by other scholars. The formulation and rise of Switching Theory is such an example. This book presents a brief account of the developments of Switching Theory and highlights some less known facts in the history of it. The readers will find the book a fresh look into the development of the field revealing how difficult it has been to arrive at many of the concepts that we now consider obvious. Researchers in the history or philosophy of computing will find this book a valuable source of information that complements the standard presentations of the topic. (orig.)
Transductions Computed by One-Dimensional Cellular Automata
Martin Kutrib; Andreas Malcher
2012-01-01
Cellular automata are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and to compute the output. Since there is a particular interest in fast transductions, we mainly focus on the time complexities real time and linear time. We first investigate the computational capabilities of cellular automaton transducers by comparing them to it...
Feedback Shift Registers as Cellular Automata Boundary Conditions
Salman, K.
2013-01-01
We present a new design for random number generatio n. The outputs of linear feedback shift registers (LFSRs) act as continuous inputs to the t wo boundaries of a one-dimensional (1-D) Elementary Cellular Automata (ECA). The results sho w superior randomness features and the output string has passed the Diehard statistical ba ttery of tests. The design is good candidate for parallel random number generation, ...
Recursive Schemes, Krivine Machines, and Collapsible Pushdown Automata
Salvati, Sylvain; Walukiewicz, Igor
2012-01-01
Higher-order recursive schemes offer an interesting method of approximating program semantics. The semantics of a scheme is an infinite tree labeled with built-in constants. This tree represents the meaning of the program up to the meaning of built-in constants. It is much easier to reason about properties of such trees than properties of interpreted programs. Moreover some interesting properties of programs are already expressible on the level of these trees. Collapsible pushdown automata (C...
A hierarchy of compositional models of I/O-Automata
Jonsson, Bengt
1991-01-01
A semantic model of computer systems is compositional if it adequately represents the behavior of the modeled systems in a context of other systems. A compositional model is thus a good basis for specifying and reasoning about systems in a modular fashion. I/O-automata is a class of communicating system which can represent several types of asyncronously communicating systems, such as message-passing distributed systems, systems with broadcast communication, and systems with shared variables. ...
Dynamical phase transitions in spin models and automata
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
Nanosensor Data Processor in Quantum-Dot Cellular Automata
Fenghui Yao; Mohamed Saleh Zein-Sabatto; Guifeng Shao; Mohammad Bodruzzaman; Mohan Malkani
2014-01-01
Quantum-dot cellular automata (QCA) is an attractive nanotechnology with the potential alterative to CMOS technology. QCA provides an interesting paradigm for faster speed, smaller size, and lower power consumption in comparison to transistor-based technology, in both communication and computation. This paper describes the design of a 4-bit multifunction nanosensor data processor (NSDP). The functions of NSDP contain (i) sending the preprocessed raw data to high-level processor, (ii) counting...
Analysis for Embedded Systems: Experiments with Priced Timed Automata
Ovatman, Tolga; Brekling, Aske Wiid; Hansen, Michael Reichhardt
2010-01-01
Analysis of resource consumption of embedded systems is a major challenge in the industry since the number of components that can be included in a single chip keeps getting bigger. In this paper, we consider simple models of embedded systems and the automated analysis about timing and memory access...... priced timed automata and Uppaal Cora as a model checking tool in reasoning about resource consumption of embedded systems....
Parametrized automata simulation and application to service composition
Belkhir, Walid; Chevalier, Yannick; Rusinowitch, Michael
2015-01-01
The service composition problem asks whether, given a client and a community of available services, there exists an agent (called the mediator) that suitably delegates the actions requested by the client to the available community of services. We address this problem in a general setting where the agents communication actions are parametrized by data from an infinite domain and possibly subject to constraints. For this purpose, we define parametrized automata (PAs), where transitions are guar...
Lattice Gas Cellular Automata for Computational Fluid Animation
Giraldi, Gilson A.; Xavier, Adilson V.; Apolinario Jr, Antonio L.; Rodrigues, Paulo S.
2005-01-01
The past two decades showed a rapid growing of physically-based modeling of fluids for computer graphics applications. In this area, a common top down approach is to model the fluid dynamics by Navier-Stokes equations and apply a numerical techniques such as Finite Differences or Finite Elements for the simulation. In this paper we focus on fluid modeling through Lattice Gas Cellular Automata (LGCA) for computer graphics applications. LGCA are discrete models based on point particles that mov...
Evolution of Cellular Automata using Lindenmayer Systems and Fourier Transforms
Berg, Sivert
2013-01-01
Cellular automata (CAs) are a class of highly parallel computing systems consisting of many simple computing elements called cells. The cells can only communicate with neighboring cells, meaning there is no global communication in the system. Programming such a system to solve complex problems can be a daunting task, and indirect methods are often applied to make it easier. In this thesis we use evolutionary algorithms (EAs) to evolve CAs. We also look at the possibility of employing L-system...
Improving Quality of Clustering using Cellular Automata for Information retrieval
P. K. Sree
2008-01-01
Full Text Available Clustering has been widely applied to Information Retrieval (IR on the grounds of its potential improved effectiveness over inverted file search. Clustering is a mostly unsupervised procedure and the majority of the clustering algorithms depend on certain assumptions in order to define the subgroups present in a data set .A clustering quality measure is a function that, given a data set and its partition into clusters, returns a non-negative real number representing the quality of that clustering. Moreover, they may behave in a different way depending on the features of the data set and their input parameters values. Therefore, in most applications the resulting clustering scheme requires some sort of evaluation as regards its validity. The quality of clustering can be enhanced by using a Cellular Automata Classifier for information retrieval. In this study we take the view that if cellular automata with clustering is applied to search results (query-specific clustering, then it has the potential to increase the retrieval effectiveness compared both to that of static clustering and of conventional inverted file search. We conducted a number of experiments using ten document collections and eight hierarchic clustering methods. Our results show that the effectiveness of query-specific clustering with cellular automata is indeed higher and suggest that there is scope for its application to IR.
GCA-w: Global Cellular Automata with Write-Access
The novel GCA-w model (Global Cellular Automata with Write access) is presented which is based on the GCA (Global Cellular Automata) model. The GCA model is a massively parallel model like the cellular automata model. In the CA model, the cells have static links to their local neighbors whereas in the GCA model, the links are dynamic according to a special local rule. In both models, the access is '' read-only ''. Thereby no write conflict can occur and all cells can update their states independently in parallel. The GCA model is useful for many parallel problems that can be described by a non-local and changing neighborhood. A shortcoming of the GCA model is the missing write access to neighboring cells. Although a write access can be emulated in O(log n) time this slowdown may not be acceptable in some practical applications. Therefore, the GCA-w model was developed. The GCA-w model allows to change the states of the neighboring cells as well as the state of the own cell. Thereby certain parallel algorithms can be described more appropriately and the number of active cells can be controlled by the cells themselves in a decentralized way. Activity control also enables dynamic resource sharing and the reduction of power consumption. The usefulness of the GCA-w model is demonstrated by some fine-grain parallel applications: one-to-all communication, synchronization and moving particles. (author)
A cellular automata evacuation model considering friction and repulsion
SONG Weiguo; YU Yanfei; FAN Weicheng; Zhang Heping
2005-01-01
There exist interactions among pedestrians and between pedestrian and environment in evacuation. These interactions include attraction, repulsion and friction that play key roles in human evacuation behaviors, speed and efficiency. Most former evacuation models focus on the attraction force, while repulsion and friction are not well modeled. As a kind of multi-particle self-driven model, the social force model introduced in recent years can represent those three forces but with low simulation efficiency because it is a continuous model with complex rules. Discrete models such as the cellular automata model and the lattice gas model have simple rules and high simulation efficiency, but are not quite suitable for interactions' simulation. In this paper, a new cellular automata model based on traditional models is introduced in which repulsion and friction are modeled quantitatively. It is indicated that the model can simulate some basic behaviors, e.g.arching and the "faster-is-slower" phenomenon, in evacuation as multi-particle self-driven models, but with high efficiency as the normal cellular automata model and the lattice gas model.
A comparison of Monte Carlo and cellular automata approaches for semiconductor device simulation
Zandler, G.; Di Carlo, A.; Kometer, K.; Lugli, P.; Vogl, P.; Gornik, E. (Technische Univ. Muenchen (Germany))
1993-02-01
The authors present a detailed comparison of Monte Carlo and cellular automata approaches as applied to the study of nonequilibrium transport and semiconductor device simulation. They show that the novel cellular automata (CA) technique enjoys all benefits of the more traditional Monte Carlo (MC) method, while at the same time allowing considerably higher performances.
Modeling chemical systems using cellular automata a textbook and laboratory manual
Kier, Lemont B; Cheng, Chao-Kun
2006-01-01
Provides a practical introduction to an exciting modeling paradigm for complex systems. This book discusses the nature of scientific inquiry using models and simulations, and describes the nature of cellular automata models. It gives descriptions of how cellular automata models can be used in the study of a variety of phenomena.
Bus Automata For Intelligent Robots And Computer Vision
Rothstein, Jerome
1988-02-01
Bus automata (BA's) are arrays of automata, each controlling a module of a global interconnection network, an automaton and its module constituting a cell. Connecting modules permits cells to become effectively nearest neighbors even when widely separated. This facilitates parallelism in computation far in excess of that allowed by the "bucket-brigade" communication bottleneck of traditional cellular automata (CA's). Distributed information storage via local automaton states permits complex parallel data processing for rapid pattern recognition, language parsing and other distributed computation at systolic array rates. Global BA architecture can be entirely changed in the time to make one cell state transition. The BA is thus a neural model (cells correspond to neurons) with network plasticity attractive for brain models. Planar (chip) BA's admitting optical input (phototransistors) become powerful retinal models. The distributed input pattern is optically fed directly to distributed local memory, ready for distributed processing, both "retinally" and cooperatively with other BA chips ("brain"). This composite BA can compute control signals for output organs, and sensory inputs other than visual can be utilized similarly. In the BA retina is essentially brain, as in mammals (retina and brain are embryologically the same). The BA can also model opto-motor response (frogs, insects) or sonar response (dolphins, bats), and is proposed as the model of choice for the brains of future intelligent robots and for computer eyes with local parallel image processing capability. Multidimensional formal languages are introduced, corresponding to BA's and patterns the way generative grammars correspond to sequential machines, and applied to fractals and their recognition by BA's.
Concretization and animation of Finite Automata with c-cards
Valente, Andrea
2004-01-01
to classes of 10 to 12 years old, and in general to students with a limited mathematical background. Our approach builds on {\\em computational cards} (or c-cards), a project aiming at scaling-down the learning complexity of computer science core contents, by presenting symbol manipulation via...... a tangible, physical metaphor. C-cards are still at a very early stage of development as an educational tool, yet we believe they represent a nice, intuitive mind-tool, that can be consistently applied to a variety of (theoretical) computer science concepts. Here an algorithm for mapping finite automata on c-cards...
Two Novel Quantum-Dot Cellular Automata Full Adders
Mahdie Qanbari
2013-01-01
Full Text Available Quantum-dot cellular automata (QCA is an efficient technology to create computing devices. QCA is a suitable candidate for the next generation of digital systems. Full adders are the main member of computational systems because other operations can be implemented by adders. In this paper, two QCA full adders are introduced. The first one is implemented in one layer, and the second one is implemented in three layers. Five-input majority gate is used in both of them. These full adders are better than pervious designs in terms of area, delay, and complexity.
Control of (max,+) automata: logical and timing aspects
Komenda, Jan; Lahaye, S.; Boimond, J.-L.
Göteborg: Ihe Institute of Electrical and Electronics Engineering, 2008 - (Lenartson, B.; Fabian, M.; Akesson, K.; Giua, A.; Kumar, R.), s. 55-60 ISBN 978-1-4244-2592-1. [International Workshop on Discrete Event Systems. Göteborg (SE), 28.05.2008-30.05.2008] R&D Projects: GA AV ČR(CZ) KJB100190609; GA MŠk MEB020729 Institutional research plan: CEZ:AV0Z10190503 Keywords : (max,+) automata * control * Hadamard product Subject RIV: BA - General Mathematics
Motion Planning in Multi-robot Systems using Timed Automata
Andersen, Michael. S.; Jensen, Rune S.; Bak, Thomas;
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......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...
Cellular automata model of magnetospheric-ionospheric coupling
Kozelov, B. V.; Kozelova, T. V.
2003-01-01
We propose a cellular automata model (CAM) to describe the substorm activity of the magnetospheric-ionospheric system. The state of each cell in the model is described by two numbers that correspond to the energy content in a region of the current sheet in the magnetospheric tail and to the conductivity of the ionospheric domain that is magnetically connected with this region. The driving force of the system is supposed to be provided by the solar wind that is convected along the two b...
Directed Percolation Phenomena in Asynchronous Elementary Cellular Automata
Fatès, Nazim,
2006-01-01
Cellular automata are discrete dynamical systems that are widely used to model natural systems. Classically they are run with perfect synchrony ; i.e., the local rule is applied to each cell at each time step. A possible modification of the updating scheme consists in applying the rule with a fixed probability, call the synchrony rate. It has been shown in a previous work that varying the synchrony rate continuously could produce a discontinuity in the behaviour of the CA. This works aims at ...
An intelligent floor field cellular automata model for pedestrian dynamics
Kirik, Ekaterina; Krouglov, Dmitriy
2009-01-01
A stochastic cellular automata (CA) model for pedestrian dynamics is presented. Our goal is to simulate different types of pedestrian movement, from regular to panic. But here we emphasize regular situations which imply that pedestrians analyze environment and choose their route more carefully. And transition probabilities have to depict such effect. The potentials of floor fields and environment analysis are combined in the model obtained. People patience is included in the model. This makes simulation of pedestrians movement more realistic. Some simulation results are presented and comparison with basic FF-model is made.
Nanosensor Data Processor in Quantum-Dot Cellular Automata
Fenghui Yao
2014-01-01
Full Text Available Quantum-dot cellular automata (QCA is an attractive nanotechnology with the potential alterative to CMOS technology. QCA provides an interesting paradigm for faster speed, smaller size, and lower power consumption in comparison to transistor-based technology, in both communication and computation. This paper describes the design of a 4-bit multifunction nanosensor data processor (NSDP. The functions of NSDP contain (i sending the preprocessed raw data to high-level processor, (ii counting the number of the active majority gates, and (iii generating the approximate sigmoid function. The whole system is designed and simulated with several different input data.
Decentralized control of product (max+)-automata using coinduction
Komenda, Jan; Lahaye, S.; Boimond, J.-L.
Guadalajara : IFAC, 2012 - (Ramírez-Treviño, A.; López-Mellado, E.; Lesage, J.), s. 122-127 ISBN 978-3-902823-28-1. [11th International Workshop on Discrete Event Systems (WODES 2012). Guadalajara (MX), 03.10.2012-05.10.2012] R&D Projects: GA ČR(CZ) GAP103/11/0517 Institutional support: RVO:67985840 Keywords : (max,+) automata * decentralized control * coalgebra Subject RIV: BA - General Mathematics http://www.ifac-papersonline.net/Detailed/58179.html
Timed Automata Semantics for Visual e-Contracts
Enrique Martínez
2011-09-01
Full Text Available C-O Diagrams have been introduced as a means to have a more visual representation of electronic contracts, where it is possible to represent the obligations, permissions and prohibitions of the different signatories, as well as what are the penalties in case of not fulfillment of their obligations and prohibitions. In such diagrams we are also able to represent absolute and relative timing constraints. In this paper we present a formal semantics for C-O Diagrams based on timed automata extended with an ordering of states and edges in order to represent different deontic modalities.
Modelling discrete longitudinal data using acyclic probabilistic finite automata
Anantharama Ankinakatte, Smitha; Edwards, David
2015-01-01
Acyclic probabilistic finite automata (APFA) constitute a rich family of models for discrete longitudinal data. An APFA may be represented as a directed multigraph, and embodies a set of context-specific conditional independence relations that may be read off the graph. A model selection algorith...... assessed using cross-validation. The comparisons are based on three data sets, two from molecular genetics and one from social science. The proposed algorithm performs at least as well as the algorithm in Beagle in both respects...
Do integrable cellular automata have the confinement property?
Grammaticos, B. [IMNC, Universite Paris VII-Paris XI, CNRS, UMR 8165, Bat. 104, 91406 Orsay (France); Ramani, A. [Centre de Physique Theorique, Ecole Polytechnique, CNRS, 91128 Palaiseau (France); Tamizhmani, K.M. [Departement of Mathematics, Pondicherry University, Kalapet, 605014 Puducherry (India); Tamizhmani, T. [Department of Mathematics, Kanchi Mamunivar Centre for Postgraduate Studies, Puducherry (India); Carstea, A.S. [Department of Theoretical Physics, Institute of Physics and Nuclear Engineering, 407 Atomistilor, Magurele, 077125 Bucharest (Romania)
2007-07-27
We analyse a criterion, introduced by Joshi and Lafortune, for the integrability of cellular automata obtained from discrete systems through the ultradiscretization procedure. We show that while this criterion can be used in order to single out integrable ultradiscrete systems, there do exist cases where the system is nonintegrable and still the criterion is satisfied. Conversely we show that for ultradiscrete systems that are derived from linearizable mappings the criterion is not satisfied. We investigate this phenomenon further in the case of a mapping which includes a linearizable subcase and show how the violation of the criterion comes to be. Finally, we comment on the growth properties of ultradiscrete systems. (fast track communication)
Do integrable cellular automata have the confinement property?
We analyse a criterion, introduced by Joshi and Lafortune, for the integrability of cellular automata obtained from discrete systems through the ultradiscretization procedure. We show that while this criterion can be used in order to single out integrable ultradiscrete systems, there do exist cases where the system is nonintegrable and still the criterion is satisfied. Conversely we show that for ultradiscrete systems that are derived from linearizable mappings the criterion is not satisfied. We investigate this phenomenon further in the case of a mapping which includes a linearizable subcase and show how the violation of the criterion comes to be. Finally, we comment on the growth properties of ultradiscrete systems. (fast track communication)
Cellular automata for traffic flow simulation with safety embedded notions
Larraga, M. E.; Alvarez-Icaza, L.
2007-01-01
In this paper a cellular automata model for one-lane traffic flow is presented. A new set of rules is proposed to better capture driver reactions to traffic that are intended to preserve safety on the highway. As a result, drivers behavior is derived from an analysis that determines the most appropriate action for a vehicle based on the distance from the vehicle ahead of it and the velocities of the two neighbor vehicles. The model preserves simplicity of CA rules and at the same time makes t...
Reversible cellular automata are invertible discrete dynamical systems which have been widely studied both for analysing interesting theoretical questions and for obtaining relevant practical applications, for instance, simulating invertible natural systems or implementing data coding devices. An important problem in the theory of reversible automata is to know how the local behaviour which is not invertible is able to yield a reversible global one. In this sense, symbolic dynamics plays an important role for obtaining an adequate representation of a reversible cellular automaton. In this paper we prove the equivalence between a reversible automaton where the ancestors only differ at one side (technically with one of the two Welch indices equal to 1) and a full shift. We represent any reversible automaton by a de Bruijn diagram, and we characterize the way in which the diagram produces an evolution formed by undefined repetitions of two states. By means of amalgamations, we prove that there is always a way of transforming a de Bruijn diagram into the full shift. Finally, we provide an example illustrating the previous results
Development of a Bacteria Computer: From in silico Finite Automata to in vitro and in vivo
Sakakibara, Yasubumi
We overview a series of our research on implementing finite automata in vitro and in vivo in the framework of DNA-based computing [1,2]. First, we employ the length-encoding technique proposed and presented in [3,4] to implement finite automata in test tube. In the length-encoding method, the states and state transition functions of a target finite automaton are effectively encoded into DNA sequences, a computation (accepting) process of finite automata is accomplished by self-assembly of encoded complementary DNA strands, and the acceptance of an input string is determined by the detection of a completely hybridized double-strand DNA. Second, we report our intensive in vitro experiments in which we have implemented and executed several finite-state automata in test tube. We have designed and developed practical laboratory protocols which combine several in vitro operations such as annealing, ligation, PCR, and streptavidin-biotin bonding to execute in vitro finite automata based on the length-encoding technique. We have carried laboratory experiments on various finite automata with 2 up to 6 states for several input strings. Third, we present a novel framework to develop a programmable and autonomous in vivo computer using Escherichia coli (E. coli), and implement in vivo finite-state automata based on the framework by employing the protein-synthesis mechanism of E. coli. We show some successful experiments to run an in vivo finite-state automaton on E. coli.
Exploring Quantum Dot Cellular Automata Based Reversible Circuit
Saroj Kumar Chandra
2012-03-01
Full Text Available Quantum-dot Cellular Automata (QCA is a new technology for development of logic circuits based on nanotechnology, and it is an one of the alternative for designing high performance computing over existing CMOS technology. The basic logic in QCA does not use voltage level for logic representation rather it represent binary state by polarization of electrons on the Quantum Cell which is basic building block of QCA. Extensive work is going on QCA for circuit design due to low power consumption and regularity in the circuit.. Clocking is used in QCA circuit to synchronize and control the information flow and to provide the power to run the circuit. Reversible logic design is a well-known paradigm in digital computation, and if circuit developed is reversible then it consumes very low power . Here, in this paper we are presenting a Reversible Universal Gate (RUG based on Quantum-dot Cellular Automata (QCA. The RUG implemented by QCA Designer tool and also its behavior is simulated by it.
Simulation of root forms using cellular automata model
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
Quantifying a cellular automata simulation of electric vehicles
Hill, Graeme; Bell, Margaret; Blythe, Phil
2014-12-01
Within this work the Nagel-Schreckenberg (NS) cellular automata is used to simulate a basic cyclic road network. Results from SwitchEV, a real world Electric Vehicle trial which has collected more than two years of detailed electric vehicle data, are used to quantify the results of the NS automata, demonstrating similar power consumption behavior to that observed in the experimental results. In particular the efficiency of the electric vehicles reduces as the vehicle density increases, due in part to the reduced efficiency of EVs at low speeds, but also due to the energy consumption inherent in changing speeds. Further work shows the results from introducing spatially restricted speed restriction. In general it can be seen that induced congestion from spatially transient events propagates back through the road network and alters the energy and efficiency profile of the simulated vehicles, both before and after the speed restriction. Vehicles upstream from the restriction show a reduced energy usage and an increased efficiency, and vehicles downstream show an initial large increase in energy usage as they accelerate away from the speed restriction.
Simulation of root forms using cellular automata model
Winarno, Nanang; Prima, Eka Cahya; Afifah, Ratih Mega Ayu
2016-02-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.
Modeling evolution and immune system by cellular automata
Bezzi, M. [Scuola Internazionale Superiore di Studi Avanzati, Trieste (Italy); Istituto Nazionale di Fisica della Materia, Florence (Italy)
2001-07-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.
Modeling evolution and immune system by cellular automata
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
Modeling self-organizing traffic lights with elementary cellular automata
Gershenson, Carlos
2009-01-01
There have been several highway traffic models proposed based on cellular automata. The simplest one is elementary cellular automaton rule 184. We extend this model to city traffic with cellular automata coupled at intersections using only rules 184, 252, and 136. The simplicity of the model offers a clear understanding of the main properties of city traffic and its phase transitions. We use the proposed model to compare two methods for coordinating traffic lights: a green-wave method that tries to optimize phases according to expected flows and a self-organizing method that adapts to the current traffic conditions. The self-organizing method delivers considerable improvements over the green-wave method. For low densities, the self-organizing method promotes the formation and coordination of platoons that flow freely in four directions, i.e. with a maximum velocity and no stops. For medium densities, the method allows a constant usage of the intersections, exploiting their maximum flux capacity. For high dens...
Simulation of root forms using cellular automata model
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.
Do you really mean what you actually enforced? Edit Automata revisited
Bielova, Nataliia; Massacci, Fabio
2008-01-01
In the landmark paper on the theoretical side of Polymer, Ligatti and his co-authors have identied a new class of enforcement mechanisms based on the notion of edit automata, that can transform sequences and enforce more than simple safety properties. We show that there is a gap between the edit automata that one can possibly write (e.g. by Ligatti et al in their running example) and the edit automata that are actually constructed according the theorems from Ligatti's IJIS paper and IC follow...
A Parallel Encryption Algorithm for Block Ciphers Based on Reversible Programmable Cellular Automata
Das, Debasis; Ray, Abhishek
2010-01-01
A Cellular Automata (CA) is a computing model of complex System using simple rule. In CA the problem space into number of cell and each cell can be one or several final state. Cells are affected by neighbours' to the simple rule. Cellular Automata are highly parallel and discrete dynamical systems, whose behaviour is completely specified in terms of a local relation. This paper deals with the Cellular Automata (CA) in cryptography for a class of Block Ciphers through a new block encryption al...
Decomposing a Kind of Weakly Invertible Finite Automata with Delay 2
YAO Gang(姚刚)
2003-01-01
Some properties of a finite automaton composed of two weakly invertible finiteautomata with delay 1 are given, where each of those two automata has the output set of eachstate with the same size. And for a weakly invertible finite automaton M with delay 2 satisfyingthe properties mentioned in this paper, two weakly invertible finite automata with delay i areconstructed such that M is equivalent to a sub-finite-automaton of the composition of those two.So a method to decompose this a kind of weakly invertible finite automata with delay 2 is presented.