Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:research:ploopc [2016/03/23 13:44]
apeiron
en:research:ploopc [2018/02/16 01:25] (current)
Line 1: Line 1:
-FIXME **This article is a work in progress.**+====== Title ======
  
-The article is still in review and the final version ​of the abstract ​and the article are not written yet.+An Imperative Language Characterizing PTIME Algorithms 
 + 
 +====== 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). 
 + 
 +**Keywords**:​ ASM, computability,​ imperative language, implicit complexity, polynomial time, sequential algorithms, simulation. 
 + 
 +====== Links ====== 
 + 
 +Here is the {{:​en:​research:​ploopc2.pdf|submitted version}}.