• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Trace Complexity of Chaotic Reversible Cellular Automata

Jarkko Kari, Ville Salo, Ilkka Törmä, Trace Complexity of Chaotic Reversible Cellular Automata. In: Shigeru Yamashita, Shin-ichi Minato (Eds.), Reversible Computation, Lecture Notes in Computer Science 8507, 54–66, Springer, 2014.

http://dx.doi.org/10.1007/978-3-319-08494-7_5

Abstract:

Delvenne, Kůrka and Blondel have defined new notions of computational complexity for arbitrary symbolic systems, and shown examples of effective systems that are computationally universal in this sense. The notion is defined in terms of the trace function of the system, and aims to capture its dynamics. We present a Devaney-chaotic reversible cellular automaton that is universal in their sense, answering a question that they explicitly left open. We also discuss some implications and limitations of the construction.

BibTeX entry:

@INPROCEEDINGS{inpKaSaTx14a,
  title = {Trace Complexity of Chaotic Reversible Cellular Automata},
  booktitle = {Reversible Computation},
  author = {Kari, Jarkko and Salo, Ville and Törmä, Ilkka},
  volume = {8507},
  series = {Lecture Notes in Computer Science},
  editor = {Yamashita, Shigeru and Minato, Shin-ichi},
  publisher = {Springer},
  pages = {54–66},
  year = {2014},
  keywords = {cellular automaton, reversible, chaos, computational complexity, trace, symbolic system},
  ISSN = {0302-9743},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication