Mapping Computation with No Memory

Serge Burckel 1 Emeric Gioan 2 Emmanuel Thomé 3
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We investigate the computation of mappings from a set $S^n$ to itself with ''in situ programs'', that is using no extra variables than the input, and performing modifications of one component at a time. We consider several types of mappings and obtain effective computation and decomposition methods, together with upper bounds on the program length (number of assignments). Our technique is combinatorial and algebraic (graph coloration, partition ordering, modular arithmetics). For general mappings, we build a program with maximal length $5n-4$, or $2n-1$ for bijective mappings. The length is reducible to $4n-3$ when $|S|$ is a power of~$2$. This is the main combinatorial result of the paper, which can be stated equivalently in terms of multistage interconnection networks as: any mapping of $\{0,1\}^n$ can be performed by a routing in a double $n$-dimensional Benes network. Moreover, the maximal length is $2n-1$ for linear mappings when $S$ is any field, or a quotient of an Euclidean domain (e.g. $Z/sZ$). In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint. The ''in situ'' trait of the programs constructed here applies to optimization of program and chip design with respect to the number of variables, since no extra writing memory is used. In a non formal way, our approach is to perform an arbitrary transformation of objects by successive elementary local transformations inside these objects only with respect to their successive states.
Type de document :
Communication dans un congrès
UC'2009: 8th International Conference on Unconventional Computation, Sep 2009, Ponta Delgada, Portugal. Springer, 5715 (5715), pp.85-97, 2009, LNCS. 〈10.1007/978-3-642-03745-0_15〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395080
Contributeur : Emeric Gioan <>
Soumis le : dimanche 14 juin 2009 - 17:16:08
Dernière modification le : jeudi 15 février 2018 - 08:48:09

Identifiants

Citation

Serge Burckel, Emeric Gioan, Emmanuel Thomé. Mapping Computation with No Memory. UC'2009: 8th International Conference on Unconventional Computation, Sep 2009, Ponta Delgada, Portugal. Springer, 5715 (5715), pp.85-97, 2009, LNCS. 〈10.1007/978-3-642-03745-0_15〉. 〈lirmm-00395080〉

Partager

Métriques

Consultations de la notice

372