Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
en:research:ploopc [2016/03/22 17:17]
apeiron created
en:research:ploopc [2018/02/16 01:25] (current)
Line 1: Line 1:
-FIXME **This page is not fully translated, yet. Please help completing the translation.**\\ //(remove this paragraph once the translation is finished)//+====== Title ======
  
-En revue...+An Imperative Language Characterizing PTIME Algorithms 
 + 
 +====== Abstract ====== 
 + 
 +Abstract State Machines of YGurevich 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. 
 + 
 +====== Links ====== 
 + 
 +Here is the {{:​en:​research:​ploopc2.pdf|submitted version}}.