Jacques Mazoyer

TCS Journal 2002 Journal Article

Reconnaissance parallèle des langages rationnels sur automates cellulaires plans

• Marianne Delorme
• Jacques Mazoyer

Peu de résultats sont connus sur la puissance de calcul des automates cellulaires 2D. Dans l'approche “reconnaissance de langages”, la difficulté provient de la multiplicité des plongements possibles d'un mot sur le plan discret. Une question très simple comme la reconnaisance des langages rationnels en temps réel devient vraiment délicate. Nous montrons ce résultat sur deux plongements particuliers (spirale d'Archimède et fil de Hilbert). Cette première investigation met en évidence que ce qui est difficile est moins l'algorithmique que la nature du plan discret.

MFCS Conference 2000 Conference Paper

The Infinite Versions of LOGSPACE! = P Are Consistent with the Axioms of Set Theory

• Grégory Lafitte
• Jacques Mazoyer

Abstract We consider the infinite versions of the usual computational complexity questions L og S pace ≟ P, NL og S pace ≟ P by studying the comparison of their descriptive logics on infinite partially ordered structures rather than restricting ourselves to finite structures. We show that the infinite versions of those famous class separation questions are consistent with the axioms of set theory and we give a sufficient condition on the complexity classes in order to get other such relative consistency results.

TCS Journal 1999 Journal Article

Avant Propos

• Jacques Mazoyer
• Renzo Pinzani
• Jean-Guy Penaud

SODA Conference 1999 Conference Paper

Compass Permits Leader Election

• Jacques Mazoyer
• Codrin M. Nichitiu
• Eric Rémila

TCS Journal 1999 Journal Article

Discrete parabolas and circles on 2D cellular automata

• Marianne Delorme
• Jacques Mazoyer
• Laure Tougne

TCS Journal 1999 Journal Article

Signals in one-dimensional cellular automata

• Jacques Mazoyer
• Véronique Terrier

In this paper, we are interested in signals, from the data can be transmitted in a cellular automaton. We study generation of some signals. In this aim, we investigate a notion of constructibility of increasing functions related to the production of words on the initial cell (in the sense of Fisher for the prime numbers). We establish some closure properties on this class of functions. We also exhibit some impossible moves of data.

MFCS Conference 1998 Conference Paper

Additive Cellular Automata over Z p and the Bottom of (CA, <=)

• Jacques Mazoyer
• Ivan Rapaport

Abstract In a previous work we began to study the question of “how to compare” cellular automata (CA). In that context it was introduced a preorder (CA, ≤) admitting a global minimum and it was shown that all the CA satisfying very simple dynamical properties as nilpotency or periodicity are located “on the bottom of (CA, ≤)”. Here we prove that also the (algebraically amenable) additive CA over ℤ p are located on the bottom of (CA, ≤). This result encourages our conjecture that says that the “distance” from the minimum could represent a measure of “complexity” on CA. We also prove that the additive CA over ℤ p with p prime are pairwise incomparable. This fact improves our understanding of (CA, ≤) because it means that the minimum, even in the canonical order compatible with ≤, has infinite outdegree.

MFCS Conference 1997 Conference Paper

A Shift-Invariant Metric on S zz Inducing a Non-trivial Tolology

• Gianpiero Cattaneo
• Enrico Formenti
• Luciano Margara
• Jacques Mazoyer

Abstract In this paper we discuss the meaning of sensitivity and its implications in CA behavior. A new shift-invariant metric is given. The metric topology induced by this metric is perfect but not compact. Moreover we prove that the new space is “suitable” for the study of the dynamical behavior of CA. In this context sensitivity assumes a stronger meaning than before (usually S ZZ is given the product topology). Now cellular automata are sensitive if they are not only capable of “transporting” the information but if they are also able to create new information. We also provide an experimental evidence of the fact that (in the new topology) sensitivity is linked to the fractal dimension of the space-time pattern generated by cellular automata evolutions.

TCS Journal 1996 Journal Article

On optimal solutions to the firing squad synchronization problem

• Jacques Mazoyer

TCS Journal 1987 Journal Article

A six-state minimal time solution to the firing squad synchronization problem

• Jacques Mazoyer

From Balzer's work (1967), we know that the firing squad synchronization problem has a minimal-time solution with eight states. We show that such a solution exists with only six states. Our method is somewhat different from all previous ones: the initial line is iteratively divided in two inequal parts so that each new right part can be treated as the homothetical image of a shorter initial line.