Paper Info
Title
Analysis of Synchronous and Asynchronous Cellular Automata Using Abstraction by Temporal Logic
Abstract
We have been studying abstractions of linked structures, in which cells are connected by pointers, using temporal logic. This paper presents some our results for these abstractions. The system to be verified is a transition system on a graph. The shape of the graph does not change as a result of the transition, but the label assigned to each cell (node) changes according to rewrite rules. The labels of cells are changed synchronously or asynchronously. We abstract such systems using abstract cells and abstract graphs. Abstract cells are characterized by a set of temporal formulas, and different abstractions can be tried by changing the set of formulas. Some examples of analysis are also described.
Year
DOI
Venue
2004
10.1007/978-3-540-24754-8_2
LECTURE NOTES IN COMPUTER SCIENCE
Keywords
Field
DocType
temporal logic,cellular automata
Transition system,Kripke structure,Pointer (computer programming),Cellular automaton,Asynchronous communication,Abstraction,Functional programming,Computer science,Algorithm,Theoretical computer science,Temporal logic
Conference
Volume
ISSN
Citations 
2998
0302-9743
3
PageRank 
References 
Authors
0.45
7
4
Name
Order
Citations
PageRank
Masami Hagiya1649102.85
Koichi Takahashi2386.30
Mitsuharu Yamamoto39111.09
Takahiro Sato430.45