Sites Inria

Version française



Effective algorithms in formal computing

The work Effective algorithms in formal computing ('Algorithmes efficaces en calcul formel'), co-written by Frédéric Chyzak and Alin Bostan (SpecFun team - Inria), Bruno Salvy (Aric team - Inria), Marc Giusti and Grégoire Lecerf (Computer Science Laboratory of the École polytechnique) has just been published.

Initially aimed at students specialising in formal computing, on a wider scale this work will be able to serve as a reference or initiation for other researchers, in this discipline or others.


Formal computing deals with exact mathematical objects from a computer science perspective. This work,Effective algorithms in formal computing,explores two avenues:

  • computability,
  • and complexity. 

Computability studies classes of mathematical objects for which answers can be obtained algorithmically. Complexity then provides tools in order to compare algorithms in terms of their effectiveness.

This work is a synthesis of study notes written primarily for the course of the same name and which the authors gave for over ten years for the MPRI (Parisian master of research in computer science) at Paris Diderot University, thegrandes écolesENS Cachan and ENS Paris, and at the École polytechnique.

The section concerning polynomial systems also comes from study notes from classes given as part of the DEA (postgraduate degree) in algebraic methods then the master's in algebra and geometry at Pierre and Marie Curie University (UPMC), but also the DEA in computer science, mathematics and applications at ENS Paris, the École polytechnique, UPMC, Paris Diderot University and Paris-Sud University.

Several sections have also been the subject of more specialised mini-lectures given during the French National Formal Computing Days (JNCF) in 2007, 2010, 2011, and 2013.

Keywords: Effective algorithms Frédéric Chyzak Alin Bostan Specfun Formal computing