The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Flavio D'alessandro - One of the best experts on this subject based on the ideXlab platform.
-
Independent sets of words and the Synchronization Problem
Advances in Applied Mathematics, 2013Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for the class of locally strongly transitive automata introduced in Carpi and [email protected]?Alessandro (2009) [9]. Some extensions of this Problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.
-
Independent sets of words and the Synchronization Problem
arXiv: Formal Languages and Automata Theory, 2011Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for the class of locally strongly transitive automata introduced in a previous work of the authors. Some extensions of this Problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.
-
MFCS - The Synchronization Problem for Locally Strongly Transitive Automata
Mathematical Foundations of Computer Science 2009, 2009Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for a new class of deterministic automata called locally strongly transitive. An application to synchronizing colorings of aperiodic graphs with a cycle of prime length is also considered.
-
Developments in Language Theory - The Synchronization Problem for Strongly Transitive Automata
Developments in Language Theory, 1Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for a new class of deterministic automata called strongly transitive. An extension to unambiguous automata is also considered.
J Reisinger - One of the best experts on this subject based on the ideXlab platform.
-
the non blocking write protocol nbw a solution to a real time Synchronization Problem
Real-Time Systems Symposium, 1993Co-Authors: Hermann Kopetz, J ReisingerAbstract:The Synchronization Problem between a communication controller writing a data structure into a common memory and a set of concurrently executing real-time tasks reading this data structure is investigated. Two versions of an adaptable new non-blocking protocol are presented and a schedulability analysis for a task set using these protocols is given. >
-
RTSS - The non-blocking write protocol NBW: A solution to a real-time Synchronization Problem
1993 Proceedings Real-Time Systems Symposium, 1Co-Authors: Hermann Kopetz, J ReisingerAbstract:The Synchronization Problem between a communication controller writing a data structure into a common memory and a set of concurrently executing real-time tasks reading this data structure is investigated. Two versions of an adaptable new non-blocking protocol are presented and a schedulability analysis for a task set using these protocols is given. >
Arturo Carpi - One of the best experts on this subject based on the ideXlab platform.
-
Independent sets of words and the Synchronization Problem
Advances in Applied Mathematics, 2013Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for the class of locally strongly transitive automata introduced in Carpi and [email protected]?Alessandro (2009) [9]. Some extensions of this Problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.
-
Independent sets of words and the Synchronization Problem
arXiv: Formal Languages and Automata Theory, 2011Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for the class of locally strongly transitive automata introduced in a previous work of the authors. Some extensions of this Problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.
-
the Synchronization Problem for locally strongly transitive automata
Mathematical Foundations of Computer Science, 2009Co-Authors: Arturo Carpi, Flavio DalessandroAbstract:The Synchronization Problem is investigated for a new class of deterministic automata called locally strongly transitive. An application to synchronizing colorings of aperiodic graphs with a cycle of prime length is also considered.
-
MFCS - The Synchronization Problem for Locally Strongly Transitive Automata
Mathematical Foundations of Computer Science 2009, 2009Co-Authors: Arturo Carpi, Flavio D'alessandroAbstract:The Synchronization Problem is investigated for a new class of deterministic automata called locally strongly transitive. An application to synchronizing colorings of aperiodic graphs with a cycle of prime length is also considered.
-
the Synchronization Problem for strongly transitive automata
Developments in Language Theory, 2008Co-Authors: Arturo Carpi, Flavio DalessandroAbstract:The Synchronization Problem is investigated for a new class of deterministic automata called strongly transitive. An extension to unambiguous automata is also considered.
Jean-baptiste Yunès - One of the best experts on this subject based on the ideXlab platform.
-
A Note on Synchronization Steps in Firing Squad Synchronization Problem
2010 Third International Joint Conference on Computational Science and Optimization, 2010Co-Authors: Akira Nomura, Jean-baptiste Yunès, Hiroshi UmeoAbstract:The firing squad Synchronization Problem on cellular automata has been studied extensively for more than forty years, and a rich variety of Synchronization algorithms have been proposed. In this paper, we propose two Synchronization algorithms and their implementations, each having O(n^2) and O(2^n) Synchronization steps for n cells, respectively.
-
About 4-states Solutions to the Firing Squad Synchronization Problem
2008Co-Authors: Jean-baptiste Yunès, Naoki Kamikawa, Hiroshi UmeoAbstract:We present some elements of a new family of time-optimal solutions to a less restrictive firing squad Synchronization Problem. These solutions are all built on top of some elementary algebraic cellular automata. Thus, this gives a very new insight on the Problem and a more general way of computing on cellular automata.
-
simple new algorithms which solve the firing squad Synchronization Problem a 7 states 4n steps solution
Machines Computations and Universality, 2007Co-Authors: Jean-baptiste YunèsAbstract:We present a new family of solutions to the firing squad Synchronization Problem. All these solutions are built with a few finite number of signals, which lead to simple implementations with 7 or 8 internal states. Using one of these schemes we are able to built a 7-states 4n+O(log n)-steps solution to the firing squad Synchronization Problem. These solutions not only solves the unrestricted Problem (initiator at one of the two ends), but also the Problem with initiators at both ends and the Problem on a ring.
-
Seven-state solutions to the Firing Squad Synchronization Problem
Theoretical Computer Science, 1994Co-Authors: Jean-baptiste YunèsAbstract:Abstract We show that seven states are enough to implement Minsky-like solutions to the Firing Squad Synchronization Problem in a linear network of n finite state cellular automata with null transmission delay.
-
ACRI - About 4-States Solutions to the Firing Squad Synchronization Problem
Lecture Notes in Computer Science, 1Co-Authors: Hiroshi Umeo, Jean-baptiste Yunès, Naoki KamikawaAbstract:We present some elements of a new family of time-optimal solutions to a less restrictive firing squad Synchronization Problem. These solutions are all built on top of some elementary algebraic cellular automata. Thus, this gives a very new insight on the Problem and a more general way of computing on cellular automata.
Mimmo Parente - One of the best experts on this subject based on the ideXlab platform.
-
Computing with New Resources - Minimum and non-Minimum Time Solutions to the Firing Squad Synchronization Problem
Computing with New Resources, 2014Co-Authors: Margherita Napoli, Mimmo ParenteAbstract:In this paper we present a survey on the minimum and non minimum time solutions to the Firing Squad Synchronization Problem. Particular emphasis is on the contribution given by Jozef Gruska, in honor of which this article is dedicated.
-
THE FIRING SQUAD Synchronization Problem ON SQUARES, TORUSES AND RINGS
International Journal of Foundations of Computer Science, 2007Co-Authors: Jozef Gruska, S. La Torre, Mimmo ParenteAbstract:It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a Synchronization just by 1 time unit.
-
Different time solutions for the firing squad Synchronization Problem on basic grid networks
RAIRO - Theoretical Informatics and Applications, 2006Co-Authors: Jozef Gruska, S. La Torre, Margherita Napoli, Mimmo ParenteAbstract:We present several solutions to the Firing Squad Synchronization Problem on grid networks of different shapes. The nodes are finite state processors that work in unison with other processors and in synchronized discrete steps. The networks we deal with are: the line, the ring and the square. For all of these models we consider one- and two-way communication modes and we also constrain the quantity of information that adjacent processors can exchange at each step. We first present Synchronization algorithms that work in time $n^2$, $n \log n$, $n\sqrt n$, $2^n$, where n is a total number of processors. Synchronization methods are described through so called signals that are then used as building blocks to compose Synchronization solutions for the cases that Synchronization times are expressed by polynomials with nonnegative coefficients.
-
Various Solutions for the Firing Squad Synchronization Problem.
2005Co-Authors: Jozef Gruska, S. La Torre, Margherita Napoli, Mimmo ParenteAbstract:We present different classes of solutions to the Firing Squad Synchronization Problem on networks of different shapes. The nodes are finite state processors that work at unison discrete steps. The networks considered are the line, the ring and the square. For all of these models we have considered one and two-way communication modes and also constrained the quantity of information that adjacent processors can exchange each step. We are given a particular time expressed as a function of the number of nodes of the network, f(n) and present Synchronization algorithms in time n 2 , nlogn, n √ n, 2 n . The solutions are presented as signals that are used as building blocks to compose new solutions for all times expressed by polynomials with nonnegative coefficients.
-
MCU - Firing Squad Synchronization Problem on Bidimensional Cellular Automata with Communication Constraints
Lecture Notes in Computer Science, 2001Co-Authors: S. La Torre, Margherita Napoli, Mimmo ParenteAbstract:We are given a network of identical processors that work synchronously at discrete time steps, a Cellular Automaton. Processors are arranged as an array of m rows and n columns with the constraint that they can exchange only one bit of information with their neighbours. We study the Problem to synchronize the cellular automata, that is to let all the processors enter the same state for the first time at the very same instant. This Problem is also known as "The Firing Squad Synchronization Problem", introduced by Moore in 1964. We give algorithms to synchronize two dimensional Cellular Automata of (n×n) cells at some given times: n2, n⌈log n⌉, n⌈√n⌉ and 2n. Moreover we also give some general constructions to synchronize Cellular Automata of (m×n) cells. Our approach is a modular description of synchronizing algorithms in terms of "fragments" of cellular automata that are called signals.
