Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
fr:research:ploopc [2016/03/23 13:45] apeiron créée |
fr:research:ploopc [2021/04/05 17:21] apeiron supprimée |
||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | FIXME **Cette page n'est pas encore traduite entièrement. Merci de terminer la traduction** | + | **An Imperative Language Characterizing PTIME Algorithms** (Yoann Marquer, Pierre Valarcher) est un article directement issu de [[fr:research:thesis-defense|mes travaux de thèse]], et qui a été publié en 2016 dans Developments in Implicit Computational Complexity, volume 3, pages 91 - 130 |
| - | FIXME **This article is a work in progress.** | + | ====== Abstract ====== |
| - | The article is still in review and the final version of the abstract and the article are not written yet. | + | 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. | ||
| + | |||
| + | ====== Versions ====== | ||
| + | |||
| + | Here is the {{:en:research:ploopc2.pdf|submitted version}}. | ||