Modèle géométrique de calcul : fractales et barrières de complexité

Autor: Senot, Maxime

Les modèles géométriques de calcul permettent d’effectuer des calculs à l’aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement d

Externí odkaz: http://www.theses.fr/2013ORLE2019/document

Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants

Autor: Duchier, Denys, Durand-Lose, Jérôme, Senot, Maxime

Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propos

Externí odkaz: http://arxiv.org/abs/1105.3454

Geometrical model of computation: fractals and complexity gaps

Autor: Senot, Maxime

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______166::33bb585ca0c59373053a00d6d4d69ede
https://theses.hal.science/tel-00870600v2

Solving Q-SAT in bounded space and time by geometrical computation

Autor: Duchier, Denys, Durand-Lose, Jérôme, Senot, Maxime

Publikováno v: CiE '11 (abstracts and handout booklet)
Models of computability in context, 7th Int. Conf. Computability in Europe
Models of computability in context, 7th Int. Conf. Computability in Europe, Jun 2011, Sofia, Bulgaria. pp.76-86

International audience; Abstract geometrical computation can solve PSPACE-com\-plete problems efficiently: any quantified boolean formula, instance of Q-SAT -- the problem of satisfiability of quantified boolean formula -- can be decided in bounded s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::ae5aeff3dce3df16d963178d1ab9f733
https://hal.archives-ouvertes.fr/hal-00605661/file/2011_CiE.pdf

Computing with signals: a generic and modular signal machine for satisfiability problems

Autor: Duchier, Denys, Durand-Lose, Jérôme, Senot, Maxime

Publikováno v: Workshop New Worlds of Computation (NWC '11)
Workshop New Worlds of Computation (NWC '11), May 2011, Orléans, France

International audience; Signal machines are an abstract and geometrical model of computation, where computations consist in colored segment lines and their intersections in the Euclidean plane. In this talk, we first introduce the model and give some

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::dc6dcbfb8a22d25a1f190d50561164c3
https://hal.archives-ouvertes.fr/hal-00749867