Three generators for minimal writing-space computations
Serge Burckel; Marianne Morillon
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 34, Issue: 2, page 131-138
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBurckel, Serge, and Morillon, Marianne. "Three generators for minimal writing-space computations." RAIRO - Theoretical Informatics and Applications 34.2 (2010): 131-138. <http://eudml.org/doc/222039>.
@article{Burckel2010,
abstract = { We
construct, for each integer n,
three functions from \{0,1\}n to \{0,1\} such that any boolean mapping from
\{0,1\}n to \{0,1\}n can be computed with a finite sequence of assignations
only using the n input variables and those three functions.
},
author = {Burckel, Serge, Morillon, Marianne},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Boolean functions; models of computations.; minimal writing-space computations},
language = {eng},
month = {3},
number = {2},
pages = {131-138},
publisher = {EDP Sciences},
title = {Three generators for minimal writing-space computations},
url = {http://eudml.org/doc/222039},
volume = {34},
year = {2010},
}
TY - JOUR
AU - Burckel, Serge
AU - Morillon, Marianne
TI - Three generators for minimal writing-space computations
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 2
SP - 131
EP - 138
AB - We
construct, for each integer n,
three functions from {0,1}n to {0,1} such that any boolean mapping from
{0,1}n to {0,1}n can be computed with a finite sequence of assignations
only using the n input variables and those three functions.
LA - eng
KW - Boolean functions; models of computations.; minimal writing-space computations
UR - http://eudml.org/doc/222039
ER -
References
top- N.G. de Bruijn, A combinatorial problem. Indag. Math.8 (1946) 461-467.
- S. Burckel, Closed Iterative Calculus. Theoret. Comput. Sci.158 (1996) 371-378.
- S. Burckel and M. Morillon, Computing Without Copying (submitted).
- S. Piccard, Sur les fonctions définies dans les ensembles finis quelconques. Fund. Math.24 (1935) 298-301.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.