bibHainry.bib

@comment{{This file has been generated by bib2bib 1.99}}
@comment{{Command line: bib2bib -c 'author : "Hainry"' -s year -r -q /home/manu/Travail/hainry.bib}}
@inproceedings{HP23-popl,
  author = {Hainry, Emmanuel and P\'{e}choux, Romain},
  title = {A General Noninterference Policy for Polynomial Time},
  booktitle = {Principles of Programming Languages, POPL 2023},
  year = 2023,
  publisher = {ACM},
  volume = {7},
  pages = {806--832},
  doi = {10.1145/3571221},
  abstract = {We introduce a new noninterference policy to capture the class of functions computable in polynomial time on an object-oriented programming language. This policy makes a clear separation between the standard noninterference techniques for the control flow and the layering properties required to ensure that each “security” level preserves polynomial time soundness, and is thus very powerful as for the class of programs it can capture. This new characterization is a proper extension of existing tractable characterizations of polynomial time based on safe recursion. Despite the fact that this noninterference policy is Π10-complete, we show that it can be instantiated to some decidable and conservative instance using shape analysis techniques.},
  series = {Proc. ACM Program. Lang.},
  articleno = {28},
  numpages = {27},
  url = {https://inria.hal.science/hal-04190355},
  pdf = {https://inria.hal.science/hal-04190355/file/shapedTiering.pdf},
  keywords = {Polynomial time, Noninterference, Shape Analysis, Computational Complexity}
}
@inproceedings{HPS23-fossacs,
  title = {A programming language characterizing quantum polynomial time},
  author = {Hainry, Emmanuel and P{\'e}choux, Romain and Silva, M{\'a}rio},
  url = {https://inria.hal.science/hal-04190385},
  booktitle = {Foundations of Software Science and Computation Structures (FoSSaCS 2023)},
  address = {Paris, France},
  year = 2023,
  month = {april},
  doi = {10.1007/978-3-031-30829-1_8},
  pdf = {https://inria.hal.science/hal-04190385/file/paper_FBQP_revised.pdf},
  hal_id = {hal-04190385},
  hal_version = {v1}
}
@inproceedings{HKMP22-fossacs,
  author = {Emmanuel Hainry and Bruce M. Kapron and Jean-Yves Marion and Romain P{\'{e}}choux},
  title = {Complete and tractable machine-independent characterizations of second-order polytime},
  booktitle = {Foundations of Software Science and Computation Structures (FoSSaCS 2022)},
  series = {Lecture Notes in Computer Science},
  pages = {368--388},
  publisher = {Springer},
  year = 2022,
  doi = {10.1007/978-3-030-99253-8_19},
  url = {https://hal.inria.fr/hal-03722245},
  pdf = {https://hal.inria.fr/hal-03722245/file/ctcbff.pdf},
  hal_id = {hal-03722245},
  hal_version = {v1}
}
@article{HKMP22-lmcs,
  author = {Emmanuel Hainry and Bruce M. Kapron and Jean-Yves Marion and Romain P{\'{e}}choux},
  title = {A tier-based typed programming language characterizing Feasible Functionals},
  year = 2022,
  journal = {Logical Methods in Computer Science},
  volume = 18,
  number = 1,
  doi = {10.46298/lmcs-18(1:33)2022},
  url = {https://hal.inria.fr/hal-03722168},
  pdf = {https://hal.inria.fr/hal-03722168/file/hkmplmcs.pdf},
  hal_id = {hal-03722168},
  hal_version = {v1}
}
@inproceedings{HJPZ21-ictac,
  author = {Emmanuel Hainry and Emmanuel Jeandel and Romain P{\'{e}}choux and Olivier Zeyen},
  editor = {Antonio Cerone and Peter Csaba {\"{O}}lveczky},
  title = {ComplexityParser: An Automatic Tool for Certifying Poly-Time Complexity of Java Programs},
  booktitle = {{ICTAC} 2021 - 18th International Colloquium on Theoretical Aspects of Computing},
  address = {Nur-Sultan, Kazakhstan},
  series = {Lecture Notes in Computer Science},
  volume = 12819,
  pages = {357--365},
  publisher = {Springer},
  month = {september},
  year = 2021,
  doi = {10.1007/978-3-030-85315-0_20},
  url = {https://hal.inria.fr/hal-03337755},
  pdf = {https://hal.inria.fr/hal-03337755/file/ictac-tool.pdf},
  hal_id = {hal-03337755},
  hal_version = {v1}
}
@inproceedings{HKMP20-lics,
  title = {{A tier-based typed programming language characterizing Feasible Functionals}},
  author = {Hainry, Emmanuel and Kapron, Bruce M. and Marion, Jean-Yves and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-02881308},
  booktitle = {Logic in Computer Science, LICS 2020},
  address = {Saarbr{\"u}cken, Germany},
  publisher = {{ACM}},
  pages = {535-549},
  year = {2020},
  month = {july},
  doi = {10.1145/3373718.3394768},
  keywords = {Feasible functionals ; BFF ; implicit computational complexity ; tiering ; type-2 ; type system},
  pdf = {https://hal.inria.fr/hal-02881308/file/bff-lics.pdf},
  hal_id = {hal-02881308},
  hal_version = {v1}
}
@inproceedings{HMP20-flops,
  title = {{Polynomial time over the reals with parsimony}},
  author = {Hainry, Emmanuel and Mazza, Damiano and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-02499149},
  booktitle = {Functional and Logic Programming (FLOPS 2020)},
  address = {Akita, Japan},
  year = {2020},
  month = {april},
  doi = {10.1007/978-3-030-59025-3_4},
  pdf = {https://hal.inria.fr/hal-02499149/file/main.pdf},
  hal_id = {hal-02499149},
  hal_version = {v1}
}
@article{HP20-LMCS,
  title = {{Theory of Higher Order Interpretations and Application to Basic Feasible Functions}},
  author = {Hainry, Emmanuel and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-02499206},
  journal = {{Logical Methods in Computer Science}},
  publisher = {{Logical Methods in Computer Science Association}},
  volume = {16},
  number = {4},
  pages = {25},
  year = {2020},
  month = {december},
  doi = {10.23638/LMCS-16(4:14)2020},
  keywords = {Implicit computational complexity ; basic feasible functionals},
  pdf = {https://hal.inria.fr/hal-02499206v2/file/1801.08350v4.pdf},
  hal_id = {hal-02499206},
  hal_version = {v2}
}
@article{HP18-ic,
  title = {{A Type-Based Complexity Analysis of Object Oriented Programs}},
  author = {Hainry, Emmanuel and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-01712506},
  journal = {{Information and Computation}},
  publisher = {{Elsevier}},
  series = {Information and Computation},
  volume = {261},
  number = {1},
  pages = {78-115},
  year = {2018},
  month = {august},
  doi = {10.1016/j.ic.2018.05.006},
  keywords = {Object Oriented Program ; Type system ; complexity ; polynomial time},
  pdf = {https://hal.inria.fr/hal-01712506/file/Object.pdf},
  hal_id = {hal-01712506},
  hal_version = {v1}
}
@inproceedings{HP17-lpar,
  author = {Emmanuel Hainry and Romain P{\'e}choux},
  title = {Higher order interpretation for higher order complexity},
  booktitle = {LPAR-21. 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning},
  year = 2017,
  editor = {Thomas Eiter and David Sands},
  volume = {46},
  series = {EPiC Series in Computing},
  pages = {269--285},
  abstract = {We design an interpretation-based theory of higher-order functions that is well-suited for the complexity analysis of a standard higher- order functional language a` la ml. We manage to express the interpretation of a given program in terms of a least fixpoint and we show that when restricted to functions bounded by higher-order polynomials, they characterize exactly classes of tractable functions known as Basic Feasible Functions at any order.},
  doi = {10.29007/1tkw},
  file = {:articles/HP17-lpar .pdf:PDF}
}
@article{FHHP15-tcs,
  author = {F{\'{e}}r{\'{e}}e, Hugo and Hainry, Emmanuel and Hoyrup, Mathieu and P{\'{e}}choux, Romain},
  title = {Characterizing polynomial time complexity of stream programs using interpretations},
  journal = {Theoretical Computer Science},
  year = 2015,
  volume = {585},
  pages = {41--54},
  doi = {10.1016/j.tcs.2015.03.008},
  publisher = {Elsevier}
}
@inproceedings{HP15-aplas,
  title = {{Objects in Polynomial Time}},
  author = {Hainry, Emmanuel and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-01206161},
  booktitle = {APLAS 2015},
  address = {Pohang, South Korea},
  editor = {Xinyu Feng and Sungwoo Park},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  volume = {9458},
  pages = {387--404},
  year = 2015,
  month = {november},
  doi = {10.1007/978-3-319-26529-2_21},
  pdf = {https://hal.inria.fr/hal-01206161/file/ICCOW.pdf},
  hal_id = {hal-01206161}
}
@article{BGH13-jcss,
  title = {Computation with perturbed dynamical systems},
  author = {Bournez, Olivier and Gra{\c c}a, Daniel and Hainry, Emmanuel},
  url = {https://hal.inria.fr/hal-00643634},
  journal = {Journal of Computer and System Sciences},
  publisher = {Elsevier},
  volume = {79},
  number = {5},
  pages = {714-724},
  year = 2013,
  doi = {10.1016/j.jcss.2013.01.025},
  keywords = {robustness ; Dynamical systems ; reachability ; computational power ; verification},
  hal_id = {hal-00643634}
}
@inproceedings{HMP13-fossacs,
  title = {Type-based complexity analysis for fork processes},
  author = {Hainry, Emmanuel and Marion, Jean-Yves and P{\'e}choux, Romain},
  url = {https://hal.inria.fr/hal-00755450},
  booktitle = {Foundations of Software Science and Computation Structures (FoSSaCS 2013)},
  address = {Rome, Italy},
  editor = {Pfenning, Frank},
  publisher = {Springer},
  volume = {7794},
  pages = {305-320},
  year = 2013,
  doi = {10.1007/978-3-642-37075-5_20},
  keywords = {Implicit Computational Complexity ; Tiering ; Secure Information Flow ; Concurrent Programming ; PSpace},
  hal_id = {hal-00755450}
}
@article{bgh11-ijuc,
  title = {{Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions}},
  author = {Bournez, Olivier and Gomaa, Walid and Hainry, Emmanuel},
  url = {https://hal.inria.fr/hal-00644361},
  journal = {{International Journal of Unconventional Computing}},
  publisher = {{Old City Publishing}},
  volume = {7},
  number = {5},
  pages = {331-351},
  year = 2011,
  keywords = {Recursive Analysis ; Polynomial Time ; Algebraic Characterization ; Real Computation ; Oracle Turing Machines}
}
@inproceedings{BGH10-mfcs,
  author = {Bournez, Olivier and Gra\c{c}a, Daniel S. and Hainry, Emmanuel},
  title = {Robust Computations with Dynamical Systems},
  booktitle = {Mathematical Foundations of Computer Science, MFCS 2010},
  year = 2010,
  editor = {Hlin{\v{e}}n{\'y}, Petr and Ku{\v{c}}era, Anton\'{\i}n},
  volume = {6281},
  series = {Lecture Notes in Computer Science},
  pages = {198-208},
  publisher = {Springer},
  abstract = {In this paper we discuss the computational
             power of Lipschitz dynamical systems which are robust to
             infinitesimal perturbations.  Whereas the study in [1] was done
             only for not-so-natural systems from a classical mathematical
             point of view (discontinuous differential equation systems,
             discontinuous piecewise affine maps, or perturbed Turing
             machines), we prove that the results presented there can be
             generalized to Lipschitz and computable dynamical systems.  In
             other words, we prove that the perturbed reachability problem
             (i.e. the reachability problem for systems which are subjected
             to infinitesimal perturbations) is co-recursively enumerable
             for this kind of systems.  Using this result we show that if
             robustness to infinitesimal perturbations is also required, the
             reachability problem becomes decidable. This result can be
             interpreted in the following manner: undecidability of
             verification doesn't hold for Lipschitz, computable and robust
             systems.  We also show that the perturbed reachability problem
             is co-r.e.  complete even for C$\infty$-systems.},
  doi = {10.1007/978-3-642-15155-2_19},
  isbn = {978-3-642-15154-5}
}
@inproceedings{FHHP10-isaac,
  author = {{F}{\'e}r{\'e}e, {H}ugo and {H}ainry, {E}mmanuel and {H}oyrup, {M}athieu and {P}{\'e}choux, {R}omain},
  title = {{I}nterpretation of stream programs: characterizing type 2 polynomial time complexity},
  booktitle = {{I}nternational {S}ymposium on {A}lgorithms and {C}omputation ({ISAAC})},
  year = 2010,
  editor = {Cheong, Ottfried and Chwa, Kyung-Wong and Park, Kunsoo},
  volume = {6506},
  series = {Lecture Notes in Computer Science},
  pages = {291-303},
  address = {{J}eju {I}sland, South Korea},
  publisher = {{S}pringer},
  abstract = {{W}e study polynomial time complexity of type
             2 functionals. {F}or that purpose, we introduce a first order
             functional stream language. {W}e give criteria, named
             well-founded, on such programs relying on second order
             interpretation that characterize two variants of type 2
             polynomial complexity including the {B}asic {F}easible
             {F}unctions ({BFF}). {T}hese characterizations provide a new
             insight on the complexity of stream programs.  {F}inally, we
             adapt these results to functions over the reals, a particular
             case of type 2 functions, and we provide a characterization of
             polynomial time complexity in {R}ecursive {A}nalysis.},
  audience = {internationale },
  doi = {10.1007/978-3-642-17517-6_27},
  hal_id = {inria-00518381}
}
@inproceedings{BGH09-lcc,
  title = {{I}mplicit complexity in recursive analysis},
  author = {Bournez, Olivier and Gomaa, Walid and Hainry, Emmanuel},
  abstract = {{R}ecursive analysis is a model of analog
             computation which is based on type 2 {T}uring machines.
             {V}arious classes of functions computable in recursive analysis
             have recently been characterized in a machine independent and
             algebraical context. {I}n particular nice connections between
             the class of computable functions (and some of its sub and
             sup-classes) over the reals and algebraically defined (sub- and
             sup-) classes of {R}-recursive functions {\`{a}} la {M}oore have
             been obtained. {W}e provide in this paper a framework that
             allows to dive into complexity for functions over the reals.
             {I}t indeed relates classical computability and complexity
             classes with the corresponding classes in recursive analysis.
             {T}his framework opens the field of implicit complexity of
             functions over the reals. {W}hile our setting provides a new
             reading of some of the existing characterizations, it also
             provides new results: inspired by {B}ellantoni and {C}ook's
             characterization of polynomial time computable functions, we
             provide the first algebraic characterization of polynomial time
             computable functions over the reals.},
  language = {{A}nglais},
  affiliation = {{L}aboratoire d'informatique de l'{\'e}cole polytechnique - {LIX} - {CNRS} : {UMR}7161 - {P}olytechnique - {X} - {CARTE} - {INRIA} {L}orraine - {LORIA} - {CNRS} : {UMR}7503 - {INRIA} - {U}niversit{\'e} {H}enri {P}oincar{\'e} - {N}ancy {I} - {U}niversit{\'e} {N}ancy {II} - {I}nstitut {N}ational {P}olytechnique de {L}orraine },
  booktitle = {{LCC}'09 - {L}ogic and {C}omputational {C}omplexity },
  address = {{L}os {A}ngeles {\'E}tats-{U}nis d'{A}m{\'e}rique },
  audience = {internationale },
  day = 10,
  month = {august},
  year = 2009,
  url = {http://hal.inria.fr/inria-00429964/en/}
}
@techreport{Hai09-unpublished,
  title = {{D}ecidability and {U}ndecidability in {D}ynamical {S}ystems},
  author = {Hainry, Emmanuel},
  abstract = {{A} computing system can be modelized in
             various ways: one being in analogy with transfer functions,
             this is a function that associates to an input and optionally
             some internal states, an output ; another being focused on the
             behaviour of the system, that is describing the sequence of
             states the system will follow to get from this input to produce
             the output. {T}his second kind of system can be defined by
             dynamical systems. {T}hey indeed describe the ``local''
             behaviour of a system by associating a configuration of the
             system to the next configuration. {I}t is obviously interesting
             to get an idea of the ``global'' behaviour of such a dynamical
             system. {T}he questions that it raises can be for example
             related to the reachability of a certain configuration or set
             of configurations or to the computation of the points that will
             be visited infinitely often. {T}hose questions are
             unfortunately very complex: they are in most cases undecidable.
             {T}his article will describe the fundamental problems on
             dynamical systems and exhibit some results on decidability and
             undecidability in various kinds of dynamical systems.},
  language = {{A}nglais},
  affiliation = {{CARTE} - {INRIA} {L}orraine - {LORIA} - {CNRS} : {UMR}7503 - {INRIA} - {U}niversit{\'e} {H}enri {P}oincar{\'e} - {N}ancy {I} - {U}niversit{\'e} {N}ancy {II} - {I}nstitut {N}ational {P}olytechnique de {L}orraine },
  institution = {{CARTE} - {INRIA} {L}orraine - {LORIA} - {CNRS} : {UMR}7503 - {INRIA} - {U}niversit{\'e} {H}enri {P}oincar{\'e} - {N}ancy {I} - {U}niversit{\'e} {N}ancy {II} - {I}nstitut {N}ational {P}olytechnique de {L}orraine },
  pages = 27,
  type = {Research Report},
  year = 2009,
  url = {http://hal.inria.fr/inria-00429965/en/}
}
@inproceedings{Hai08-cie,
  author = {Hainry, Emmanuel},
  title = {Reachability in Linear Dynamical Systems},
  booktitle = {CiE 2008: Logic and Theory of Algorithms},
  year = 2008,
  editor = {Beckmann, Arnold and Dimitracopoulos, Costas and L{\"o}we, Benedikt},
  volume = {5028},
  series = {Lecture Notes in Computer Science},
  pages = {241--250},
  abstract = {Dynamical systems allow to modelize various phenomena or
             processes by only describing their local behaviour. The study of
             dynamical systems aims at knowing more on the global behaviour.
             Checking the reachability of a point is a fundamental problem. In
             this document, using results from the algebraic numbers theory such
             as Gelfond-Schneider's theorem, we will show that this problem that
             is undecidable in the general case is in fact decidable for a
             natural class of continuous-time dynamical systems: linear
             systems.},
  doi = {10.1007/978-3-540-69407-6_28}
}
@inproceedings{Hai08-uc,
  author = {Hainry, Emmanuel},
  title = {Computing omega-limit Sets in Linear Dynamical Systems},
  booktitle = {Unconventional Computing, UC 2008},
  year = 2008,
  editor = {Calude, Cristian S. and Costa, Jos\'{e} F\'{e}lix and Freund, Rudolf and Oswald, Marion and Rozenberg, Grzegorz},
  volume = {5204},
  series = {Lecture Notes in Computer Science},
  pages = {83--95},
  abstract = {Dynamical systems allow to modelize various phenomena or
             processes by only describing their local behaviour.  It is an important
             matter to study the global and the limit behaviour of such systems.
             A possible description of this limit behaviour is via the
             omega-limit set: the set of points that can be limit of
             subtrajectories. The omega-limit set is in general uncomputable. It
             can be a set highly difficult to apprehend. Some systems have for
             example a fractal omega-limit set. However, in some specific cases,
             this set can be computed. This problem is important to verify
             properties of dynamical systems, in particular to predict its
             collapse or its infinite expansion.  We prove in this paper that
             for linear continuous time dynamical systems, it is in fact
             computable. More, we also prove that the $\omega$-limit set is
             a semi-algebraic set. The algorithm to compute this set can
             easily be derived from this proof.},
  doi = {10.1007/978-3-540-85194-3_9}
}
@article{bcgh07-jcomp,
  author = {Bournez, Olivier and Campagnolo, Manuel L. and Gra\c{c}a, Daniel S. and Hainry, Emmanuel},
  title = {Polynomial differential equations compute all real computable functions on computable compact intervals},
  journal = {Journal of Complexity},
  year = 2007,
  volume = {23},
  number = {3},
  pages = {317--335},
  abstract = {In the last decade, there have been several attempts to
             understand the relations between the many models of analog computation.
             Unfortunately, most models are not equivalent. Euler's Gamma
             function, which is computable according to computable analysis, but
             that cannot be generated by Shannon's General Purpose Analog
             Computer (GPAC), has often been used to argue that the GPAC is less
             powerful than digital computation. However, when computability with
             GPACs is not restricted to real-time generation of functions, it
             has been shown recently that Gamma becomes computable by a GPAC.
             Here we extend this result by showing that, in an appropriate
             framework, the GPAC and computable analysis are actually equivalent
             from the computability point of view, at least in compact
             intervals. Since GPACs are equivalent to systems of polynomial
             differential equations then we show that all real computable
             functions over compact intervals can be defined by such models.},
  doi = {10.1016/j.jco.2006.12.005},
  file = {:articles/BouCamGra06a.pdf:PDF},
  keywords = {Analog computation; Computable analysis; General Purpose Analog Computer; Church--Turing thesis; Differential equations},
  local-url = {file://localhost/Users/manu/Documents/articles/BouCamGra06a.pdf}
}
@inproceedings{bh07-mcu,
  author = {Bournez, Olivier and Hainry, Emmanuel},
  title = {On the computational capabilities of several models},
  booktitle = {Machines, Computations, and Universality - MCU 2007, Orl\'{e}ans, France},
  year = 2007,
  editor = {Durand-Lose, J\'{e}r\^{o}me and Margenstern, Maurice},
  volume = {4664},
  series = {Lecture Notes in Computer Science},
  pages = {12-23},
  publisher = {Springer},
  abstract = {We review some results about the computational
             power of several computational models. Considered models have in common
             to be related to continuous dynamical systems.},
  doi = {10.1007/978-3-540-74593-8_2}
}
@inproceedings{bcgh06-tamc,
  author = {Bournez, Olivier and Campagnolo, Manuel L. and Gra{\c{c}}a, Daniel S. and Hainry, Emmanuel},
  title = {The General Purpose Analog Computer and Computable Analysis are Two Equivalent Paradigms of Analog Computation},
  booktitle = {Theory and Applications of Models of Computation, TAMC 2006},
  year = 2006,
  editor = {Cai, Jin-Yi and Cooper, S. Barry and Li, Angsheng},
  volume = {3959},
  series = {Lecture Notes in Computer Science},
  pages = {631 -- 643},
  publisher = {Springer},
  abstract = {In this paper we revisit one of the first models of analog
             computation, Shannon's General Purpose Analog Computer (GPAC). The GPAC
             has often been argued to be weaker than computable analysis. As
             main contribution, we show that if we change the notion of
             GPAC-computability in a natural way, we compute exactly all real
             computable functions (in the sense of computable analysis).
             Moreover, since GPACs are equivalent to systems of polynomial
             differential equations then we show that all real computable
             functions can be defined by such models.},
  doi = {10.1007/11750321_60},
  file = {:articles/BouCamGra06.pdf:PDF},
  local-url = {file://localhost/Users/manu/Documents/articles/BouCamGra06.pdf}
}
@article{bh06-fi,
  affiliation = {PROTHEO [INRIA Lorraine - LORIA]},
  author = {Bournez, Olivier and Hainry, Emmanuel},
  journal = {Fundamenta Informaticae},
  local-url = {file://localhost/Users/manu/Documents/articles/BouHai06.pdf},
  number = 4,
  pages = {409--433},
  publisher = {Annales Societatis Mathematicae Polonae},
  title = {Recursive Analysis Characterized as a Class of Real Recursive Functions},
  url = {http://hal.inria.fr/inria-00000515/en/},
  volume = 74,
  year = 2006,
  abstract = {Recently, using a limit schema, we presented an analog and
             machine independent algebraic characterization of elementarily
             computable functions over the real numbers in the sense of
             recursive analysis. In a dierent and orthogonal work, we proposed a
             minimization schema that allows to provide a class of real
             recursive functions that corresponds to extensions of computable
             functions over the integers. Mixing the two approaches we prove
             that computable functions over the real numbers in the sense of
             recursive analysis can be characterized as the smallest class of
             functions that contains some basic functions, and closed by
             composition, linear integration, minimization and limit schema. }
}
@phdthesis{hainry06,
  author = {Hainry, Emmanuel},
  month = {december},
  year = 2006,
  school = {Institut National Polytechnique de Lorraine},
  title = {Mod\`{e}les de calcul sur les r\'{e}els, r\'{e}sultats de comparaison},
  type = {{PhD} Thesis},
  local-url = {file://localhost/Users/manu/Documents/articles/Hai06.pdf},
  url = {https://members.loria.fr/ehainry/papers/manuscrit.pdf},
  abstract = {Il existe de nombreux mod\`{e}les de calcul sur les r\'{e}els. Ces
             diff\'{e}rents mod\`{e}les calculent diverses fonctions, certains sont plus
             puissants que d'autres, certains sont deux \`{a} deux incomparables. Le
             calcul sur les r\'{e}els est donc de ce point de vue bien diff\'{e}rent du
             calcul sur les entiers qui est unifi\'{e} par la th\`{e}se de Church-Turing
             qui affirme que tous les mod\`{e}les raisonnables calculent les m^{e}mes
             fonctions.
             
Les r\'{e}sultats de cette th\`{e}se sont de deux sortes. Premi\`{e}rement,
             nous montrons des \'{e}quivalences entre les fonctions r\'{e}cursivement
             calculables et une certaine classe de fonctions
             $\mathbb{R}$-r\'{e}cursives et entre les fonctions {GPAC}-calculables et
             les fonctions r\'{e}cursivement calculables. Ces deux r\'{e}sultats ne sont
             cependant valables que si les fonctions pr\'{e}sentent quelques
             caract\'{e}ristiques : elles doivent ^{e}tre d\'{e}finies sur un compact et dans
             le premier cas ^{e}tre de classe $\mathscr{C}^2$.  Deuxi\`{e}mement, nous
             montrons \'{e}galement une hi\'{e}rarchie de classes de fonctions
             $\mathbb{R}$-r\'{e}cursives qui caract\'{e}risent les fonctions
             \'{e}l\'{e}mentairement calculables, les fonctions $\mathscr{E}_n$-calculables
             pour $n\geq3$ (o\`{u} les $\mathcal{E}_n$ sont les fonctions de la
             hi\'{e}rarchie de Grzegorczyk), et des fonctions r\'{e}cursivement
             calculables.  Ce r\'{e}sultat utilise un op\'{e}rateur de limite dont nous
             avons prouv\'{e} la g\'{e}n\'{e}ralit\'{e} en montrant qu'il transf\`{e}re une inclusion
             sur la partie discr\`{e}te des fonctions en une inclusion sur les
             fonctions sur les r\'{e}els elles-m^{e}mes.
             
Ces r\'{e}sultats constituent donc une avanc\'{e}e vers une \'{e}ventuelle
             unification des mod\`{e}les de calcul sur les r\'{e}els.},
  keywords = {Analyse r\'{e}cursive, calculabilit\'{e} r\'{e}elle, fonctions \'{e}l\'{e}mentaires, hi\'{e}rarchie de Grzegorczyk, General Purpose Analog Computer}
}
@inproceedings{bh04-mcu,
  author = {Bournez, Olivier and Hainry, Emmanuel},
  booktitle = {Machines, Computations, and Universality, MCU 2004},
  editor = {Margenstern, Maurice},
  doi = {10.1007/978-3-540-31834-7_9},
  local-url = {file://localhost/Users/manu/Documents/articles/BouHai04.pdf},
  loria = {bournez04c,A04-R-290},
  pages = {116-127},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Real Recursive Functions and Real Extentions of Recursive Functions},
  volume = {3354},
  year = 2005,
  abstract = {Recently, functions over the reals that extend elementarily
             computable functions over the integers have been proved to correspond
             to the smallest class of real functions containing some basic
             functions and closed by composition and linear integration. We
             extend this result to all computable functions: functions over the
             reals that extend total recursive functions over the integers are
             proved to correspond to the smallest class of real functions
             containing some basic functions and closed by composition, linear
             integration and a very natural unique minimization schema.}
}
@article{bh05-tcs,
  author = {Bournez, Olivier and Hainry, Emmanuel},
  title = {Elementary computable functions over the real numbers and {R}-sub-recursive functions},
  journal = {Theoretical Computer Science},
  year = 2005,
  volume = {348},
  number = {2-3},
  pages = {130--147},
  month = {december},
  abstract = {We present an analog and machine-independent algebraic
             characterization of elementarily computable functions over the real
             numbers in the sense of recursive analysis: we prove that they
             correspond to the smallest class of functions that contains some
             basic functions, and closed by composition, linear integration, and
             a simple limit schema. We generalize this result to all higher levels
             of the Grzegorczyk Hierarchy. This paper improves several previous
             partial characterizations and has a dual interest:
             * Concerning recursive analysis, our results provide
             machine-independent characterizations of natural classes of
             computable functions over the real numbers, allowing to define
             these classes without usual considerations on higher-order (type 2)
             Turing machines.
             * Concerning analog models, our results provide a characterization
             of the power of a natural class of analog models over the real
             numbers and provide new insights for understanding the relations
             between several analog computational models.},
  doi = {10.1016/j.tcs.2005.09.010},
  keywords = {Analog computation; Recursive analysis; Real recursive functions; Computability; Analysis},
  local-url = {file://localhost/Users/manu/Documents/articles/BouHai05.pdf}
}
@inproceedings{bh04-appsem,
  author = {Bournez, Olivier and Hainry, Emmanuel},
  title = {An analog Characterization of Elementarily Computable Functions Over the Real Numbers},
  booktitle = {{2nd APPSEM II Workshop - APPSEM'2004, Tallinn, Estonia}},
  crinnumber = {A04-R-289},
  category = {3},
  equipe = {PROTHEO},
  year = 2004,
  month = {april},
  url = {http://www.loria.fr/publications/2004/A04-R-289/A04-R-289.ps},
  keywords = {analog models, complexity, computability},
  abstract = {We present an analog and machine-independent algebraic
             characterizations of elementarily computable functions over the real
             numbers in the sense of recursive analysis\,: we prove that they
             correspond to the smallest class of functions that contains some
             basic functions, and closed by composition, linear integration, and
             a simple limit schema. We generalize this result to all higher
             levels of the Grzegorczyk Hierarchy. Concerning recursive analysis,
             our results provide machine-independent characterizations of natural
             classes of computable functions over the real numbers, allowing to
             define these classes without usual considerations on higher-order
             (type 2) Turing machines. Concerning analog models, our results
             provide a characterization of the power of a natural class of
             analog models over the real numbers.}
}
@inproceedings{bh04-icalp,
  author = {Bournez, Olivier and Hainry, Emmanuel},
  booktitle = {International Colloquium on Automata, Languages and Programming (ICALP 2004)},
  editor = {D\'{i}az, Josep and Karhum{\"a}ki, Juhani and Lepist{\"o}, Arto and Sannella, Donald},
  local-url = {file://localhost/Users/manu/Documents/articles/BouHai04a.pdf},
  doi = {10.1007/978-3-540-27836-8_25},
  pages = {269-280},
  series = {Lecture Notes in Computer Science},
  title = {An analog characterization of elementary computable functions over the real numbers},
  volume = {3142},
  year = 2004,
  abstract = {We present an analog and machine-independent algebraic
             characterization of elementarily computable functions over the real
             numbers in the sense of recursive analysis: we prove that they
             correspond to the smallest class of functions that contains some
             basic functions, and closed by composition, linear integration, and
             a simple limit schema.  We generalize this result to all higher
             levels of the Grzegorczyk Hierarchy.  Concerning recursive
             analysis, our results provide machine-independent characterizations
             of natural classes of computable functions over the real numbers,
             making it possible to define these classes without usual considerations
             on higher-order (type 2) Turing machines. Concerning analog models,
             our results provide a characterization of the power of a natural class
             of analog models over the real numbers.}
}
@techreport{hainry03,
  author = {Hainry, Emmanuel},
  title = {Fonctions r{\'e}elles calculables et fonctions {R}-r{\'e}cursives},
  institution = {ENS Lyon},
  year = 2003,
  type = {Stage de DEA},
  month = {july},
  url = {http://www.loria.fr/publications/2003/A03-R-347/A03-R-347.ps},
  crinnumber = {A03-R-347},
  equipe = {PROTHEO},
  keywords = {computability, computation over reals, elementary functions, real rcomputable functions},
  abstract = {On d{\'e}finit des op{\'e}rateurs de limites sur les
             fonctions. A l'aide de ces op{\'e}rateurs, on d{\'e}finit de nouvelles
             classes de fonctions par cl{\^o}ture. On compare ces classes avec
             les fonctions {\'e}l{\'e}mentairement calculables (d{\'e}finies
             {\`a} partir de machines de Turing). On obtient ainsi une
             caract{\'e}risation des fonctions {\'e}l{\'e}mentairement calculables
             sous forme de cl{\^o}ture.}
}