Lógica, Provas e Algoritmos

Alessandra Carbone

Current Position

Associate Professor, Department of Mathematics and Computer Science, University of Paris 12


  • 1985 University of Milan (Italy), M.A. in Computer Science.
  • 1988 University of Siena (Italy), Specialization School in Mathematical Logic.
    Thesis advisors: Franco Montagna and Dick de Jongh
  • 1992 The City College of New York, M.A. in Pure Mathematics
  • 1993 The Graduate School of the City University of New York, PhD in Mathematics.
    Thesis advisor: Rohit Parikh


    Proof complexity, structures of proofs, combinatorics, combinatorial group theory, automata theory.

    Visiting positions (selected)

  • Jun-Jul 1989 and Jun-Jul 1990 Department of Mathematics of the University of Amsterdam (The Netherlands)
  • Sept 1993 - Aug 1995 Department of Mathematics, University of Paris 7. Holding a postdoctoral fellowship from the EC.
  • Dec 1993 and April 1994 Department of Mathematics of the Technische Universität Wien (Austria).
  • Sept 1995- Aug 1996 Department of Discrete Mathematics and Algebra of the Technische Universität Wien (Austria). Holding a Lise-Meitner Fellowship for Science of the Austrian Science Foundation.
  • Jan-Feb 1996 Institut des Hautes Études Scientifiques, Bures-sur-Yvette (France).
  • April 1996 DIMACS, Piscataway (USA).
  • December 1996 Tata Institute of Fundamental Research, Bombay (India) and Institute of Mathematical Sciences, Madras (India).
  • April 1997 Courant Institute of Mathematical Sciences, New York (USA)

    Invited addresses (selection)

  • Proof Theory, Complexity, Metamathematics, 5-8 April, 1994. Technische Universität Wien (Vienna, Austria).
  • Proof Theory and Proof Search Workshop, 11-12 November, 1994. University of Paris 7 (Paris, France).
  • Workshop on Feasible Arithmetics and Length of Proofs, 21-23 April, 1996. DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University (NJ, USA).
  • Section in Honor of Prof. Parikh - 16 FST-TCS Conference, 18-20 December, 1996. Hyderabad (India).
  • Geometry and Complexity, 5-9 May, 1997. The Fields Institute, Toronto (Canada).

    Service (selection)

  • Co-organizer, with Misha Gromov (IHES) of the meeting Patterns formation in geometry, biology and computer graphics, I.H.E.S. (Bures sur Yvette, Francia), December 1997.
  • Member of the Program Committee for the A.S.L. Meeting (joint to the annual meeting of the AMS), Baltimore, USA, January 1998.
  • Member of Program Committee of CSL'98, annual conference of the European Association of Computer Science Logic (EACSL). Brno, Check Republic, August 31-September 4, 1998.

    List of Publications (selected)


  • Ph.D. Dissertation, On logical flow graphs, The City University of New York, NY, USA, 1993.
  • Thesis of Specialization in Mathematical Logic, The length of proofs, University of Siena, 1988.

    Research articles (selection)

  • ``Rosser Orderings in Bimodal Logics'' with Franco Montagna, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 35:343-358, 1989.
  • ``Much Shorter Proofs: a Bimodal Investigations'' with Franco Montagna, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 36, 1990.
  • ``Provable Fixed Points in $I\Delta _0 +\Omega _1$'' Notre Dame Journal of Formal Logic. 32:562-572,1991.
  • ``Interpolants, Cut Elimination and Flow Graphs for the Propositional Calculus'', Annals of Pure and Applied Logic 83:249-299, 1997.
  • ``The Craig Interpolation Theorem for Schematic Systems''. In Collegium Logicum - Annals of the Kurt Gödel Society, Springer-Verlag, vol. 2, 1996, 87-100.
  • ``Making proofs without Modus Ponens: an introduction to the combinatorics and complexity of cut elimination'', with Stephen Semmes. In Bullettin of the American Mathematical Society 34:131--159, 1997.
  • ``Turning cycles into spirals''. To appear in Annals of Pure and Applied Logic, 1997.
  • ``Looking from the inside and from the outside'', with Stephen Semmes, IHES preprint M/96/44, Bures-sur-Yvette (France), 1996. Submitted.
  • ``Some Combinatorics behind Proofs''. Submitted, 1996.
  • ``No Speed-Up for the Non-Standard Theory of Feasible Numbers''. Submitted, 1997.


  • Geometry and Symmetry of Implicit Representations. Graphs, Formal proofs, Algorithmic Recursion and Complexity. with Stephen Semmes. In preparation, 1997.