Geometrical model of computation: fractals and complexity gaps

Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, throught a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components --called modules-- supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00870600
Author Senot, Maxime
Maintainer CCSD
Last Updated May 6, 2026, 19:43 (UTC)
Created May 6, 2026, 19:43 (UTC)
Identifier tel-00870600
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor GAMoC ; Laboratoire d'Informatique Fondamentale d'Orléans (LIFO) ; Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
creator Senot, Maxime
date 2013-06-27T00:00:00
harvest_object_id e9c4fddc-ab49-4295-a635-873ec02ce7d9
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-12T00:00:00
set_spec type:THESE