Revisão Bibliográfica: Autômatos Celulares
Bibliografy: Fonte: http://www.brunel.ac.uk/depts/AI/alife/
Download 445.54 Kb.
|
- Navigate this page:
- Title: Artificial Life
- 8) Inversibilidade
- Fonte: http://www.fapesp.br
- Title: Invertible Cellular Automata: A Review
- 9) Vínculo com outras áreas
Bibliografy:Fonte: http://www.brunel.ac.uk/depts/AI/alife/
Fonte: http://madeira.cc.hokudai.ac.jp/RD/takai/automa.html
Fonte: Citeseer: http://citeseer.nj.nec.com Referências Principais: Title: Artificial LifeAuthor: Packard, Bedau (2000) Abstract: Ver Introduction and History acima. O artigo explica com detalhes o que é vida artificial e suas relações com autômatos celulares. Artigos relacionados: • Agents, Games, and Evolution - Kimbrough (2001) • Convolution Generated Motion as a Link Between Cellular.. - Ruuth, Merriman, Osher (1998) • Towards a Multi-Agent Model for Visualizing Simulated User .. - Dijkstra, TIMMERMANS (1999) • Evolution of Cellular-automaton-based Associative Memories - Marcin Chady And • The Artificial Evolution of Adaptive Behaviour - Harvey (1995) • An Approach to Biological Computation: Unicellular Core-Memory.. - Suzuki (1999) • Core Memory Objects with Address Registers Representing.. - Hideaki Suzuki Atr - August 25, 2000 • Emergence and Levels of Abstraction - Damper Image Speech • Artificial Chemistries - Dittrich • A Developmental Model for the Evolution of Artificial Neural.. - Astor (1998) • Evolution of Genetic Organization in Digital Organisms - Charles Ofria (1999) • Evolution in time-dependent fitness landscapes - Claus Wil Ke (1998) • Evolution of Emergent Cooperative Behavior using Genetic Programming - Koza (1993) • Specialization of Perceptual Processes - Horswill (1994) • Schema Propagation in Selective Crossover - Kanta Vekaria And • Royal Road Encodings and Schema Propagation in Selective.. - Kanta Vekaria And • Challenging the Computational Metaphor: Implications for How We.. - Stein (1999) • A study of population uniformization in GAs - Preux (1994) • Artificial Biology - Maley The Artificial Voltar 8) Inversibilidade• Autômatos Reversíveis/Inversíveis Um autômato reversível é um sistema que não perde nenhuma informação ao longo do tempo. Assim em qualquer ponto na escala de tempo, o sistema é completamente reversível. Para introduzir um autômato reversível temos que estender a definição anterior de tempo dinâmico desenvolvida z(t+1) = f(z(t), Nz(t)) para
z(t+1) = f(z(t), Nz(t)) - z(t-1). A função z(t+1) é utilizada na reversão.A função (regra) f é arbitrária. Assim torna-se fácil a criação de autômatos celulares reversíveis fora de um conjunto de regras. Bibliografia: Fonte: http://www.fapesp.brTheoretical Computer ScienceVol: 246, Issue: 1-2, September 6, 2000 pp. 117-129 Title: Reversible space–time simulation of cellular automata Author: Durand-Lose, Jérôme O.a, 1 Affiliations: a. Laboratoire 13S, CNRS UPREES-A 6070, 930 Route des Colles, BP 145, 06903 SOPHIA ANTIPOLIS Cedex, France Keywords: (Partitioned) Cellular automata; Space–time simulation; Intrinsic universality and reversibility Abstract: The goal of this paper is to design a reversible d-dimensional cellular automaton which is capable of simulating the behavior of any given d-dimensional cellular automaton over any given configuration (even infinite) with respect to a well suited notion of simulation we introduce. We generalize a problem which was originally addressed in a paper by Toffoli in 1977. He asked whether a d-dimensional reversible cellular automaton could simulate d-dimensional cellular automata. In the same paper he proved that there exists a (d+1)-dimensional reversible cellular automaton which can simulate a given d-dimensional cellular automaton. To prove our result, we use as an intermediate model partition cellular automata defined by Morita et al. in 1989. Publisher: Elsevier Science Language of Publication: English Item Identifier: S0304-3975(99)00075-4 Publication Type: Article ISSN: 0304-3975 Fonte: Citeseer: http://citeseer.nj.nec.com Referências Principais: Title: Invertible Cellular Automata: A ReviewAuthor: Toffoli, Margolus (1994) Artigos relacionados: • A Survey of Continuous-Time Computation Theory - Orponen (1997) ...theoretical issues in analog computing, a similar situation exists, or can be foreseen, in e.g. cellular automata [17] and other "complex systems" models of computation (e.g. [36, 40]), molecular computing [1,... /...systems. (Technically, one needs to require here that the Turing machines to be simulated are invertible, but it is well known [4, 5] that any Turing machine can be converted into an invertible one.)... • Linear Cellular Automata With Boundary Conditions - Chin, Cortzen, Goldman (2000) ...CELLULAR AUTOMATA WITH BOUNDARY CONDITIONS William Chin 1 , Barbara Cortzen 1 , Jerry Goldman 2 I.... /...conditions. In other work, Jen [4], studied linear automata with periodic boundary conditions and invertible transition rules, utilizing the the theory of linear recurrences. In [2], periodic boundary... • Complexity of Two-Dimensional Patterns - Lindgren, Moore, Nordahl (2000) ... Cristopher Moore y Mats Nordahl z May 30, 2000 Abstract In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a language or set of symbol sequences produced... /...any drastic consequences to complexity theory. 3 Applications to Cellular Automata 3.1 Cellular automata Cellular automata or CA's are spatially extended dynamical systems de ned on a regular lattice where the... /... t (x) is in U j . This sequence then describes a coarse history or itinerary of x. If the map is invertible, a can also be extended backwards, producing a bi-in nite sequence. A logical question to ask,... • Dynamical constraints on group actions - Morris (1998) ... determined by Laurent polynomials on the full two dimensional two shift (two dimensional algebraic cellular automata). We go on to consider the more abstract setting of a mixing Z action by continuous group... /...subshifts. There are two appendices. The first is a short paper with Ward on mixing properties of invertible extensions that is not related to the material in the thesis. The second is a paper with Ward... • Crystalline Computation - Norman Margolus To ...discrete computer-logic. In particular, he discussed whether crystalline arrays of logic called Cellular Automata (CA) might 2 NORMAN H. MARGOLUS be able to simulate our known laws of physics in a direct... /...There has, however, been relatively little attention paid to exact lattice models which obey an invertible dynamics: from any state of the dynamical system you can infer the previous state. This kind of... • Corrigendum - Mike Boyle And ...subsequent decisive result of M. Nasu [N] that all expansive invertible onesided onedimensional cellular automata are shifts of nite type. Nevertheless, because Proposition 3.2 is of independent interest and... /...in [BM] is a special case of the subsequent decisive result of M. Nasu [N] that all expansive invertible onesided onedimensional cellular automata are shifts of nite type. Nevertheless, because... • Raissa M. D'Souza - Bell Laboratories Murray ...but here we apply it in the context of a lattice-gas with exact particle conservation. Earlier Cellular Automata (CA) models have used dimension splitting[19, 20], but not for simulating di#usion, and not as a... /...di#erence involves randomness: it is explicitly provided by concurrently simulating a di#erent invertible LGA as a source of stochasticity. This approach has also been used before in other parallel LGA... • Expansive Invertible Onesided Cellular Automata - Mike Boyle And (2000) ...INVERTIBLE ONESIDED CELLULAR AUTOMATA MIKE BOYLE AND ALEJANDRO MAASS Abstract. We study expansive invertible onesided cellular automata ... /...INVERTIBLE ONESIDED CELLULAR AUTOMATA MIKE BOYLE AND ALEJANDRO MAASS Abstract. We study expansive invertible ... • Scholar cursus - July-Septembre Programming Of ... July-Septembre 1997 Programming of a parallel application for the generalpurpose simulation of cellular automata in the project Paralin, in contact with Chile (work done at the University of Santiago, under... /...Good. June{July 1993 Internship under the direction of Bruno Durand, L.I.P., subject: Invertible Cellular Automata leading to a publication ([Dub95a, Dub93]). 1992-1993 First year of Magistre... • How to simulate Turing machines by invertible.. - Jean-Christophe.. ...to simulate Turing machines by invertible one-dimensional cellular automata Jean-Christophe Dubacq D'epartement de Math'ematiques et d'Informatique, ' Ecole Normale... /...or could be melted locally by the action of \Phi. The difference between partitionned cellular automata and cellular automata is that the local transition function is always defined as being the composition of GN... /...to simulate Turing machines by invertible one-dimensional cellular automata Jean-Christophe Dubacq D'epartement de Math'ematiques et... • The "game of everything" - Penrose Department Of ...that it is minimal at t 0. Key words: entropy, irreversibility, direction of time, reversible cellular automata, probability measures on infinite graphs, Gibbs states. 1 Introduction Ever since Boltzmann's... /...node are related to those in its immediate past by a `dynamical rule' which is deterministic and invertible. The assumed probability measure makes the nodes at time 0 independent, and correlations develop... • The Reachability problem for finite cellular automata - Andrea Clementi Centre ...Reachability problem for finite cellular automata Andrea Clementi Centre Universitaire d'Informatique University of Gen`eva Gen`eva (CH) Russell ... /...REachability Problem (CREP) for two classes of finite weakly predictable cellular automata: the invertible and the additive ones. In both cases we prove that CREP belongs tp the "Arthur-Merlin" class... • Rectangular structures from affine planes over fields - Tim Boykett ...Abstract A method for constructing rectangular structures, and thus reversible one-dimensional cellular automata from affine planes is presented. The construction of such examples from affine planes over finite ... /...=(R 1 R 2 ) R 1 \Theta R 2 . We say two rectangular structures are isomorphic if there is an invertible map between the base sets that preserves rectangles. Take two sets A B. Define S A \Theta B,... • Reversible Cellular Automaton Able to Simulate Any Other.. - Jrme Olivier ...'95, LNCS 911, pp. 230244 Abstract. Partitioning automata (PA) are dened. They are equivalent to cellular automata (CA). Reversible sub-classes are also equivalent. A simple, reversible and universal partitioning ... /...ioe its global function simulates the global function of the other. 3 Relations to Cellular Automata Cellular automata (CA) work on the same kind of lattice L (=ZZ 2 ). The points of L are called cells... /...composition of various elementary transitions. A PA is reversible ioe its global function is invertible and is the global function of some PA. It is equivalent to bijectivity of the elementary... • Almost All S-Integer Dynamical Systems Have Many Periodic Points - Ward (1997) ...corresponding to isometric extensions of the full p-shift or, more generally, linear algebraic cellular automata on the full p-shift) we show that the conjecture holds with the possible exception of at most... /... (k) be defined by V (S) ! \Gamma1 k (U! k (S)) : Then V is a 1=2 k preserving, invertible, ergodic transformation on \Omega (k), called the odometer. We shall often be dealing only... • Comments on "Theory and Applications of Cellular Automata in .. - Blackburn Murphy ...on "Theory and Applications of Cellular Automata in Cryptography" S.R. Blackburn , S. Murphy y and K.G. Paterson z Information Security... /... the stream ciphers in turn. 2.1 PCA with ROM Generator The PCA with ROM generator consists of l invertible L \Theta L binary matrices R 0 : : : R l\Gamma1 stored in ROM. Let V be an L dimensional... • "Structure and Complexity" - Organizers Eric ...Royer Complexity at Higher Types Miklos Santha A Decision Procedure for Unitary Linear Quantum Cellular Automata Rainer Schuler Is Testing More Complex Than Querying? Thomas Schwentick Algebraic and... /...sets complete for C under AC 0 reductions are all isomorphic under isomorphisms computable and invertible by AC 0 circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions: ... • Continuous Stochastic Cellular Automata That Have a.. - Poggio, Girosi (1994) ...WHITAKER COLLEGE A.I. Memo No.1168 April 1994 C.B.I.P. Paper No. 37 Continuous Stochastic Cellular Automata That Have a Stationary Distribution and No Detailed Balance Tomaso Poggio and Federico Girosi... /... d ff (x) 1 2 K fffi @ 2 @x fi @x ff U(x) 0 Provided that the diffusion matrix K is invertible we can effectuate the coordinate transformation x ff ! 1 2 K fiff x fi and defining the vector... • Some Results on Invertible Cellular Automata - Clementi, Mentrasti, PIERINI ...Results on Invertible Cellular Automata A. CLEMENTI . P. MENTRASTI y . P. PIERINI z Abstract We address certain questions... /...Results on Invertible Cellular Automata A. CLEMENTI . P. MENTRASTI y . P. PIERINI z Abstract We address certain ... • An Efficient Nonlinear Shift-Invariant Transformation - Joan Daemen ...sequences by means of automata with shift-invariant state-transition functions, called cellular automata. The transformation is closely related to one of the two nonlinear transformations that were... /...and the state-transition function of synchronous stream ciphers. Proposition1. If n is odd, is invertible. This proposition is proven by describing an algorithm that determines a unique preimage a for... • Periodicity and Transport from Round-Off Errors - Vivaldi ...to achieve invertibility in a delicate numerical experiment [Karney 1983], to represent maps as cellular automata [Kaneko 1988], and to construct numerically reversible symplectic integrators [Scovel 1991]. A... /... as a rule the floating-point dynamics is not a permutation, even when the map being represented is invertible. Yet every symplectic map is a permutation, and any discrete model that is to be consistent with... • Modelling Dynamical Geometry With Lattice Gas Automata - Brosl Hasslacher ... two research programs face complementary difficulties: Ilachinski's family of structurally dynamic cellular automata (CA) is so loosely constrained that the rule space is too large to explore usefully [13]. Hillman ... /...to implement: as we will discuss further in Section 3, making the scattering matrix invertible suffices. Nevertheless, the simultaneous requirements of particle number and momentum... Outros artigos relacionados: • Invertible Cellular Automata: A Review - Toffoli, Margolus (1990) • A common language for \programmable matter" (cellular.. - Tommaso To Oli • Occam, Turing, von Neumann, Jaynes: How much can you get for how.. - Toffoli (1994) • Some Results on Invertible Cellular Automata - Clementi, Mentrasti, PIERINI • Nonconstructible Blocks In 1d Cellular Automata: Minimal.. - Andrew Adamatzky • Cellular Automata and Artificial Life - Computation and Life in.. - Morita (1998) • Non-Conventional Computers - Toffoli (1998) • Action, or the fungibility of computation - Tommaso Toffoli • Parallel Quantum Computation - Norman Margolus Mit (1991) • Co-evolving Non-Uniform Cellular Automata to Perform Computations - Sipper (1996) • AFOSR Initiative Element: Lattice-Gas Automata and Lattice.. - Yepez (1993) • An introduction to Cellular Automata - Delorme (1998) • Cellular Automata and Lattice Boltzmann Techniques: An.. - Chopard, Luthi, Masselot (1998) • Reversible Cellular Automaton Able to Simulate Any Other - Jrme Olivier • Selection, and Combinatorial Drift - Up To This Programmable Matter Methods - Tommaso Toffoli
9) Vínculo com outras áreas9.1) Autômatos Celulares e Algoritmos GenéticosDirectory: pub -> docs -> vonzuben pub -> Asilomar Conference on Circuits, Systems & Computers, Pacific Grove, ca, November 1978, pp. 55 58 pub -> Forthcoming meetings and conferences pub -> Harmonised compatibility and sharing conditions for video pmse in the 7 9 ghz frequency band, taking into account radar use docs -> A dragon in the tube vonzuben -> Revisão Bibliográfica: Learning Vector Quantization 28/04/2003 vonzuben -> Revisão bibliográfica redes neurais recorrentes docs -> Updated March 2017 Registration Quick Reference Card for Employees/Associates Download 445.54 Kb. Share with your friends:
|