In this paper, we consider asynchronous update scheme for a variant of graph rewriting systems called graph-rewriting automata, and show that synchronous update can be simulated by asynchronous update using a constructed rule set from the one for synchronous update. It is well known that such rule construction is possible on cellular automata or other automata networks whose structures are fixed, but graph rewriting automata induce structural changes and additional mechanism of communication and local synchronization is required. Some simple examples are given by simulation.
Описание
CiteULike: Asynchronous Graph-Rewriting Automata and Simulation of Synchronous Execution
%0 Book Section
%1 Tomita2007
%A Tomita, Kohji
%A Murata, Satoshi
%A Kurokawa, Haruhisa
%B Advances in Artificial Life
%C Berlin, Heidelberg
%D 2007
%E Almeida,
%E Rocha, Luis
%E Costa, Ernesto
%E Harvey, Inman
%E Coutinho, António
%I Springer Berlin / Heidelberg
%K adaptive-networks asynchrony graph-automata graph-grammar graph-rewriting graphs networks synchrony
%P 865--875
%R 10.1007/978-3-540-74913-4\_87
%T Asynchronous Graph-Rewriting Automata and Simulation of Synchronous Execution
%U http://dx.doi.org/10.1007/978-3-540-74913-4\_87
%V 4648
%X In this paper, we consider asynchronous update scheme for a variant of graph rewriting systems called graph-rewriting automata, and show that synchronous update can be simulated by asynchronous update using a constructed rule set from the one for synchronous update. It is well known that such rule construction is possible on cellular automata or other automata networks whose structures are fixed, but graph rewriting automata induce structural changes and additional mechanism of communication and local synchronization is required. Some simple examples are given by simulation.
%& 87
%@ 978-3-540-74912-7
@incollection{Tomita2007,
abstract = {In this paper, we consider asynchronous update scheme for a variant of graph rewriting systems called graph-rewriting automata, and show that synchronous update can be simulated by asynchronous update using a constructed rule set from the one for synchronous update. It is well known that such rule construction is possible on cellular automata or other automata networks whose structures are fixed, but graph rewriting automata induce structural changes and additional mechanism of communication and local synchronization is required. Some simple examples are given by simulation.},
added-at = {2011-06-14T15:53:25.000+0200},
address = {Berlin, Heidelberg},
author = {Tomita, Kohji and Murata, Satoshi and Kurokawa, Haruhisa},
biburl = {https://www.bibsonomy.org/bibtex/20b047d5b74765093d7c7b02183959553/rincedd},
booktitle = {Advances in Artificial Life},
chapter = 87,
citeulike-article-id = {9407125},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-74913-4\_87},
citeulike-linkout-1 = {http://www.springerlink.com/content/e2722441385532p0},
description = {CiteULike: Asynchronous Graph-Rewriting Automata and Simulation of Synchronous Execution},
doi = {10.1007/978-3-540-74913-4\_87},
editor = {Almeida and Rocha, Luis and Costa, Ernesto and Harvey, Inman and Coutinho, Ant\'{o}nio},
interhash = {3b98eb7cf2db242c7411275f2484a73c},
intrahash = {0b047d5b74765093d7c7b02183959553},
isbn = {978-3-540-74912-7},
keywords = {adaptive-networks asynchrony graph-automata graph-grammar graph-rewriting graphs networks synchrony},
pages = {865--875},
posted-at = {2011-06-14 14:52:43},
priority = {2},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
timestamp = {2011-06-14T15:53:26.000+0200},
title = {Asynchronous Graph-Rewriting Automata and Simulation of Synchronous Execution},
url = {http://dx.doi.org/10.1007/978-3-540-74913-4\_87},
volume = 4648,
year = 2007
}