Author name cluster

Pablo Arrighi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

MFCS Conference 2021 Conference Paper

Universal Gauge-Invariant Cellular Automata

Pablo Arrighi
Marin Costes
Nathanaël Eon

Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs "matter", and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a. k. a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a. k. a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.

Details

I&C Journal 2017 Journal Article

The vectorial λ-calculus

Pablo Arrighi
Alejandro Díaz-Caro
Benoît Valiron

We describe a type system for the linear-algebraic λ-calculus. The type system accounts for the linear-algebraic aspects of this extension of λ-calculus: it is able to statically describe the linear combinations of terms that will be obtained when reducing the programs. This gives rise to an original type theory where types, in the same way as terms, can be superposed into linear combinations. We prove that the resulting typed λ-calculus is strongly normalising and features weak subject reduction. Finally, we show how to naturally encode matrices and vectors in this typed calculus.

Details DOI

I&C Journal 2013 Journal Article

Causal graph dynamics

Pablo Arrighi
Gilles Dowek

We extend the theory of cellular automata to arbitrary, time-varying graphs. In other words we formalise, and prove theorems about, the intuitive idea of a labelled graph which evolves in time — but under the natural constraint that information can only ever be transmitted at a bounded speed, with respect to the distance given by the graph. The notion of translation-invariance is also generalised. The definition we provide for these ‘causal graph dynamics’ is simple and axiomatic. The theorems we provide also show that it is robust. For instance, causal graph dynamics are stable under composition and under restriction to radius one. In the finite case some fundamental facts of cellular automata theory carry through: causal graph dynamics admit a characterisation as continuous functions, and they are stable under inversion. The provided examples suggest a wide range of applications of this mathematical object, from complex systems science to theoretical physics.

Details DOI

MFCS Conference 2006 Conference Paper

Algebraic Characterizations of Unitary Linear Quantum Cellular Automata

Pablo Arrighi

Abstract We provide algebraic criteria for the unitarity of linear quantum cellular automata, i. e. one dimensional quantum cellular automata. We derive these both by direct combinatorial arguments, and by adding constraints into the model which do not change the quantum cellular automata’s computational power. The configurations we consider have finite but unbounded size.

Details