La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays Les problèmes de synchronisation des pelotons d'exécution pour les modèles numériques sur un affichage à sept segments et des tableaux de segments

Kazuya YAMASHITA, Mitsuru SAKAI, Sadaki HIROSE, Yasuaki NISHITANI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le Problème de synchronisation des pelotons d'exécution (FSSP), l'un des problèmes les plus connus liés aux automates cellulaires, a été initialement proposé par Myhill en 1957 et est devenu célèbre grâce aux travaux de Moore [1]. La première solution à ce problème a été donnée par Minsky et McCarthy [2] et une solution en temps minimal a été donnée par Goto [3]. De nombreuses recherches ont également porté sur des variantes de ce problème. Dans cet article, d’un point de vue théorique, nous étendrons ce problème aux modèles numériques sur un affichage à sept segments. Certains de ces problèmes peuvent être généralisés comme FSSP pour certains arbres spéciaux appelés arbres de segments. Le FSSP pour les arbres de segments peut être réduit à un FSSP pour un tableau unidimensionnel divisé uniformément par des cellules jointes que nous appelons tableau de segments. Nous donnerons des algorithmes pour résoudre les FSSP pour ce tableau de segments et d'autres modèles numériques, respectivement. De plus, nous clarifierons le temps minimal nécessaire pour résoudre ces problèmes et montrerons qu’une telle solution n’existe pas.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.12 pp.3276-3283
Date de publication
2010/12/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E93.D.3276
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Mots-clés

Table des matières