Skip to main content

Advanced Search

Projected result for your current search: 0

Search Operators:

You can use operators in your search query to narrow down your results even more. Click on the search operator to see an explanation of how it works.
Finds documents with exactly this word group, in exactly this word order and spelling (e.g. "employer branding").
Finds documents with both search terms (e.g. sales AND bonus).
Finds documents with one or the other search term (e.g. porsche OR volkswagen).
Finds documents with all search terms. Blank space is understood as AND (e.g. man robot production).
Finds documents with no appearance of the word behind NOT (e.g. ford NOT "harrison ford").
Finds documents where the search term is mentioned at least "n" times."n" may be any number (e.g. COUNT(gear)>8).
Finds documents with both search terms in any word order, permitting "n" words as a maximum distance between them. Best choose between 15 and 30 (e.g. NEAR(recruit, professionals, 20)).
Finds documents with the search term in word versions or composites. The asterisk * marks whether you wish them BEFORE, BEHIND, or BEFORE and BEHIND the search term (e.g. lightweight*, *lightweight, *lightweight*).
Finds documents with the search term in different spellings. "?" allows only one character (e.g. organi?ation).
Special characters are understood as AND (e.g. Miller Bros. & Sons).

Semantic Search

powered by (Link opens in a new window)
loading …
Log in
Top
Natural Computing

State-efficient realization of fault-tolerant FSSP algorithms

  • 17-10-2019
Published in:
Authors
Hiroshi Umeo
Naoki Kamikawa
Masashi Maeda
Gen Fujita
Published in
Natural Computing | Issue 4/2019

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of FSSP algorithms has been proposed. Here we study the classical FSSP on a model of fault-tolerant cellular automata that might have possibly some defective cells and present the first state-efficient implementations of fault-tolerant FSSP algorithms for one-dimensional (1D) and two-dimensional (2D) cellular arrays. It is shown that, under some constraints on the length and distribution of defective cells, any 1D cellular array of length n with p defective cell segments can be synchronized in \(2n-2+p\) steps and the algorithm is realized on a 1D cellular automaton of length \(n, 2 \le n \le 50\), having 164 states and 4792 transition rules. In addition, we give by far a smaller-state implementation of a 2D FSSP algorithm that can synchronize any 2D rectangular array of size \(m \times n\), possibly including at most O(mn) isolated defective zones, exactly in \(2(m+n)-4\) steps on a cellular automaton with only 6 states and 935 transition rules.

Please log in to get access to your license.

Log in Register for free

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Online-Abonnement

Springer Professional "Business + Economics & Engineering + Technology" gives you access to:

  • more than 102.000 books
  • more than 537 journals

from the following subject areas:

  • Automotive
  • Construction + Real Estate
  • Business IT + Informatics
  • Electrical Engineering + Electronics
  • Energy + Sustainability
  • Finance + Banking
  • Management + Leadership
  • Marketing + Sales
  • Mechanical Engineering + Materials
  • Insurance + Risk


Secure your knowledge advantage now!

inform now

Springer Professional "Engineering + Technology"

Online-Abonnement

Springer Professional "Engineering + Technology" gives you access to:

  • more than 67.000 books
  • more than 390 journals

from the following specialised fileds:

  • Automotive
  • Business IT + Informatics
  • Construction + Real Estate
  • Electrical Engineering + Electronics
  • Energy + Sustainability
  • Mechanical Engineering + Materials





 

Secure your knowledge advantage now!

inform now

Springer Professional "Business + Economics"

Online-Abonnement

Springer Professional "Business + Economics" gives you access to:

  • more than 67.000 books
  • more than 340 journals

from the following specialised fileds:

  • Construction + Real Estate
  • Business IT + Informatics
  • Finance + Banking
  • Management + Leadership
  • Marketing + Sales
  • Insurance + Risk



Secure your knowledge advantage now!

inform now
previous article Preface
next article Optimal and suboptimal regional control of probabilistic cellular automata
Title
State-efficient realization of fault-tolerant FSSP algorithms
Authors
Hiroshi Umeo
Naoki Kamikawa
Masashi Maeda
Gen Fujita
Publication date
17-10-2019
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 4/2019
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-019-09765-3
This content is only visible if you are logged in and have the appropriate permissions.
This content is only visible if you are logged in and have the appropriate permissions.

Other articles of this Issue 4/2019

A cellular automata based approach to track salient objects in videos

Solving dynamic economic emission dispatch problem considering wind power by multi-objective differential evolution with ensemble of selection method

A hybrid instance-intensive workflow scheduling method in private cloud environment

Optimal and suboptimal regional control of probabilistic cellular automata

Lattice-based versus lattice-free individual-based models: impact on coexistence in competitive communities

A decomposition based multiobjective genetic algorithm with adaptive multipopulation strategy for flowshop scheduling problem

Premium Partner

    Image Credits
    Neuer Inhalt/© ITandMEDIA, Nagarro GmbH/© Nagarro GmbH, AvePoint Deutschland GmbH/© AvePoint Deutschland GmbH, AFB Gemeinnützige GmbH/© AFB Gemeinnützige GmbH, USU GmbH/© USU GmbH, Ferrari electronic AG/© Ferrari electronic AG