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

Autor:	Duchier, Denys, Durand-Lose, Jérôme, Senot, Maxime
Přispěvatelé:	Durand-Lose, Jérôme, Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO)
Jazyk:	angličtina
Rok vydání:	2011
Předmět:	[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Zdroj:	Workshop New Worlds of Computation (NWC '11) Workshop New Worlds of Computation (NWC '11), May 2011, Orléans, France
Popis:	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 basic properties, and then we illustrate the power of signal machines by a geometrical construction solving Q-SAT in bounded space and time, by the use of space-time continuity. We will also discuss some new complexities measure, more adapted to signal machines
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::dc6dcbfb8a22d25a1f190d50561164c3 https://hal.archives-ouvertes.fr/hal-00749867 Zobrazit plný text záznamu