Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
Prochaine révision Les deux révisions suivantes
fr:research:ploopc [2016/04/13 17:21]
apeiron supprimée 		fr:research:ploopc [2018/02/16 01:25]
127.0.0.1 modification externe
Ligne 1: Ligne 1:
 FIXME **Cette page n'est pas encore traduite entièrement.** FIXME **Cette page n'est pas encore traduite entièrement.**
- 
-FIXME **This article is a work in progress.** 
  
 ====== Title ====== ====== Title ======
Ligne 9: Ligne 7:
 ====== Abstract ====== ====== Abstract ======
  
-Abstract State Machines of Y. Gurevich capture sequential algorithms, so we define the set of PTIME algorithms as the set of ASM programs computed in polynomial time (using timer-step principle). Then, we construct an imperative programming language PLoopC using bounded loop with break, and running with any data structure. Finally, we prove that PLoopC computes exactly PTIME algorithms in lock step (one step of the ASM is simulated by using a constant number of steps). ​+Abstract State Machines of Y. Gurevich capture sequential algorithms, so we define the set of PTIME algorithms as the set of ASM programs computed in polynomial time (using timer-step principle). Then, we construct an imperative programming language PLoopC using bounded loop with break, and running with any data structure. Finally, we prove that PLoopC computes exactly PTIME algorithms in lock step (one step of the ASM is simulated by using a constant number of steps).
  
 **Keywords**:​ ASM, computability,​ imperative language, implicit complexity, polynomial time, sequential algorithms, simulation. **Keywords**:​ ASM, computability,​ imperative language, implicit complexity, polynomial time, sequential algorithms, simulation.
Ligne 15: Ligne 13:
 ====== Links ====== ====== Links ======
  
-Here is {{:​en:​research:​ploopc1.pdf|the current ​version}}.+Here is the {{:​en:​research:​ploopc2.pdf|submitted ​version}}.