@string{jan = {janvier}}
@string{feb = {f{\'e}vrier}}
@string{mar = {mars}}
@string{apr = {avril}}
@string{jul = {juillet}}
@string{aug = {ao{\^u}t}}
@string{sep = {septembre}}
@string{oct = {octobre}}
@string{nov = {novembre}}
@string{dec = {d{\'e}cembre}}
@string{acadsci = {Comptes Rendus de l'Acad{\'e}mie des Sciences Paris}}
@string{acadsciusa = {Proceedings of the National Academy of Sciences of the USA}}
@string{amermonth = {The American Mathematical Monthly}}
@string{bullamer = {Bulletin of the American Mathematical Society}}
@string{bullsmf = {Bulletin de la Soci{\'e}t{\'e} Math{\'e}matique de France}}
@string{duke = {Duke Mathematical Journal}}
@string{entcs = {Electronic Notes in Theoretical Computer Science}}
@string{fundinform = {Fundamenta Informaticae}}
@string{fundmath = {Fundamenta Mathematicae}}
@string{ieeeann = {{IEEE} Annals of the History of Computing}}
@string{jcomp = {Journal of Complexity}}
@string{jcss = {Journal of Computer and System Sciences}}
@string{lncs = {Lecture Notes in Computer Science}}
@string{michigan = {The Michigan Mathematical Journal}}
@string{mlq = {Mathematical Logic Quarterly}}
@string{phdthesis = {{PhD} Thesis}}
@string{procamer = {Proceedings of the American Mathematical Society}}
@string{studlogic = {Studies in Logic and the Foundations of Mathematics}}
@string{tcs = {Theoretical Computer Science}}
@string{transamer = {Transactions of the American Mathematical Society}}
@string{ijuc = {International Journal of Unconventional Computing}}


@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 = lncs,
	VOLUME = {9458},
	PAGES = {387--404},
	YEAR = {2015},
	MONTH = Nov,
	PDF = {https://hal.inria.fr/hal-01206161/file/ICCOW.pdf},
	HAL_ID = {hal-01206161},
	HAL_VERSION = {v1},
	abstract  = {A  type system  based on  non-interference
		and  data  ramification   principles  is  introduced  in
		order  to capture  the  set of  functions computable  in
		polynomial time on OO  programs. The studied language is
		general  enough to  capture most  OO constructs  and our
		characterization is  quite expressive  as it  allows the
		analysis  of a  combination of  imperative loops  and of
		data ramification scheme based  on Bellantoni and Cook's
		safe recursion using function algebra}
}

@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   = tcs,
	volume    = {585},
	pages     = {41--54},
	year      = 2015,
	publisher =	elsevier,
	url       = {http://dx.doi.org/10.1016/j.tcs.2015.03.008},
	doi       = {10.1016/j.tcs.2015.03.008},
	abstract  = {This paper provides a criterion based on interpretation methods on term rewrite systems in order to characterize the polynomial time complexity of second order functionals. For that purpose it introduces a first order functional stream language that allows the programmer to implement second order functionals. This characterization is extended through the use of exp-poly interpretations as an attempt to capture the class of Basic Feasible Functionals (bff). Moreover, these results are adapted to provide a new characterization of polynomial time complexity in computable analysis. These characterizations give a new insight on the relations between the complexity of functional stream programs and the classes of functions computed by Oracle Turing Machine, where oracles are treated as inputs.}
}


@article{BGH13-jcss,
	year	=	2013,
	title	=	{Computation with perturbed dynamical systems },
	journal	=	{Journal of Computer and System Sciences},
	volume	=	{79},
	number	=	{5},
	pages	=	{714 - 724},
	issn	=	{0022-0000},
	doi	=	{10.1016/j.jcss.2013.01.025},
	url	=	{http://www.sciencedirect.com/science/article/pii/S0022000013000469},
	author	=	{Olivier Bournez and Daniel S. Gra\c{c}a and Emmanuel Hainry},
	abstract	=	{This paper analyzes the computational power of dynamical
		systems robust to infinitesimal perturbations. Previous work on the
		subject has delved on very specific types of systems. Here we obtain
		results for broader classes of dynamical systems (including those systems
		defined by Lipschitz/analytic functions). In particular we show that systems
		robust to infinitesimal perturbations only recognize recursive languages. We
		also show the converse direction: every recursive language can be robustly
		recognized by a computable system. By other words we show that robustness is
		equivalent to decidability.}
}


@inproceedings{HMP13-fossacs,
	year	=	2013,
	isbn	=	{978-3-642-37074-8},
	booktitle	=	{Foundations of Software Science and Computation Structures},
	volume	=	{7794},
	series	=	lncs,
	editor	=	{Pfenning, Frank},
	doi	=	{10.1007/978-3-642-37075-5_20},
	title	=	{Type-Based Complexity Analysis for Fork Processes},
	url	=	{http://dx.doi.org/10.1007/978-3-642-37075-5_20},
	publisher	=	springer,
	keywords	=	{Implicit Computational Complexity; Tiering; Secure Information Flow; Concurrent Programming; PSpace},
	author	=	{Hainry, Emmanuel and Marion, Jean-Yves and P{\'e}choux, Romain},
	abstract	=	{We introduce a type system for concurrent programs
			described as a parallel imperative language using while-loops and
			fork/wait instructions, in which processes do not share a global
			memory, in order to analyze computational complexity. The type
			system provides an analysis of the data-flow based both on a data
			ramification principle related to tiering discipline and on secure
			typed languages. The main result states that well-typed processes
			characterize exactly the set of functions computable in polynomial
			space under termination, confluence and lock-freedom assumptions.
			More precisely, each process computes in polynomial time so that
			the evaluation of a process may be performed in polynomial time on
			a parallel model of computation. Type inference of the presented
			analysis is decidable in linear time provided that basic operator
			semantics is known.},
	pages	=	{305-320}
}

@article{BGH11-ijuc,
	author	=	{Bournez, Olivier and Gomaa, Walid and Hainry, Emmanuel},
	title	=	{Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions},
	journal	=	ijuc,
	volume	=	{7},
	number	=	{5},
	year	=	2011,
	pages	=	{331-351},
	URL	=	{http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC7.5abstracts/IJUCv7n5p331-351Bournez.html},
	abstract	=	{Recursive analysis is the most classical approach to model
		and discuss computations over the real numbers. Recently, it has been
		shown that computability classes of functions in the sense of
		recursive analysis can be defined (or characterized) in an
		algebraic machine independent way, without resorting to Turing
		machines. In 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 Moore 96 have been obtained. However,
		until now, this has been done only at the computability level, and not
		at the complexity level. In this paper we provide a framework that
		allows us to dive into the complexity level of real functions. In
		particular we provide the first algebraic characterization of
		polynomial-time computable functions over the reals. This framework
		opens the field of implicit complexity of analog functions, and
		also provides a new reading of some of the existing
		characterizations at the computability level.}
}


@inproceedings{BGH10-mfcs,
	author	=	{Bournez, Olivier and Gra\c{c}a, Daniel~S. and Hainry, Emmanuel},
	title	=	{Robust Computations with Dynamical Systems},
	pages	=	{198-208},
	url	=	{http://dx.doi.org/10.1007/978-3-642-15155-2_19},
	editor	=	{Hlin{\v{e}}n{\'y}, Petr and Ku{\v{c}}era, Anton\'{\i}n},
	booktitle	=	{Mathematical Foundations of Computer Science 2010, MFCS 2010, Brno, Czech Republic},
	publisher	=	{Springer},
	series	=	lncs,
	volume	=	6281,
	year	=	2010,
	isbn	=	{978-3-642-15154-5},
	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.}
}


@inproceedings{FHHP10-isaac,
	HAL_ID	=	{inria-00518381},
	title	=	{{I}nterpretation of stream programs: characterizing type 2 polynomial time complexity},
	author	=	{{F}{\'e}r{\'e}e, {H}ugo and {H}ainry, {E}mmanuel and {H}oyrup, {M}athieu and {P}{\'e}choux, {R}omain},
	booktitle	=	{{I}nternational {S}ymposium on {A}lgorithms and {C}omputation ({ISAAC}) },
    editor  =   {Cheong, Ottfried and Chwa, Kyung-Wong and Park, Kunsoo},
	publisher	=	{{S}pringer },
	address	=	{{J}eju {I}sland, South Korea},
	audience	=	{internationale },
	series	=	lncs,
	volume	=	{6506},
	pages	=	{291-303},
	URL	=	{http://dx.doi.org/10.1007/978-3-642-17517-6_27},
	year	=	2010,
	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.},
}


@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	=	aug,
	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},
	Booktitle	=	{Computability in Europe 2008, Ath\`{e}nes, Gr\`{e}ce},
	Editor	=	{Beckmann, Arnold and Dimitracopoulos, Costas and L{\"o}we, Benedikt},
	Series	=	lncs,
	Volume	=	5028,
	Title	=	{Reachability in Linear Dynamical Systems},
	Url	=	"http://dx.doi.org/10.1007/978-3-540-69407-6_28",
	Pages	=	{241--250},
	Year	=	2008,
	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.}
}


@inproceedings{Hai08-uc,
	Author	=	{Hainry, Emmanuel},
	Title	=	{Computing omega-limit Sets in Linear Dynamical Systems},
	Booktitle	=	{Unconventional Computation, UC 2008, Vienne, Autriche},
	Editor	=	{Calude, Cristian S. and Costa, Jos\'{e} F\'{e}lix and Freund, Rudolf and Oswald, Marion and Rozenberg, Grzegorz},
	Series	=	lncs,
	Volume	=	5204,
	Url	=	{http://dx.doi.org/10.1007/978-3-540-85194-3_9},
	Pages	=	{83--95},
	Year	=	2008,
	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.}
}


@article{bcgh07-jcomp,
	Author	=	{Bournez, Olivier and Campagnolo, Manuel L. and Gra\c{c}a, Daniel S. and Hainry, Emmanuel},
	Journal	=	jcomp,
	Keywords	=	{Analog computation; Computable analysis; General Purpose Analog Computer; Church--Turing thesis; Differential equations},
	Local-Url	=	{file://localhost/Users/manu/Documents/articles/BouCamGra06a.pdf},
	Url	=	{http://dx.doi.org/10.1016/j.jco.2006.12.005},
	Number	=	3,
	Pages	=	{317--335},
	Title	=	{Polynomial differential equations compute all real computable functions on computable compact intervals},
	Volume	=	23,
	Year	=	{2007},
	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.}}


@inproceedings{bh07-mcu,
	Author	=	{Bournez, Olivier and Hainry, Emmanuel},
	Booktitle	=	{Machines, Computations, and Universality - MCU 2007, Orl\'{e}ans, France},
	Editor	=	{Durand-Lose, J\'{e}r\^{o}me and Margenstern, Maurice},
	Url	=	"http://dx.doi.org/10.1007/978-3-540-74593-8_2",
	Pages	=	{12-23},
	Publisher	=	{Springer},
	Series	=	lncs,
	Title	=	{On the computational capabilities of several models},
	Volume	=	{4664},
	Year	=	2007,
	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.},
}

@article{bh06-fi,
	Affiliation	=	{PROTHEO [INRIA Lorraine - LORIA]},
	Author	=	{Bournez, Olivier and Hainry, Emmanuel},
	Journal	=	fundinform,
	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. }}


@inproceedings{bcgh06-tamc,
	Author	=	{Bournez, Olivier and Campagnolo, Manuel L. and Gra{\c{c}}a, Daniel S. and Hainry, Emmanuel},
	Booktitle	=	{Theory and Applications of Models of Computation, TAMC 2006},
	Editor	=	{Cai, Jin-Yi and Cooper, S. Barry and Li, Angsheng},
	Local-Url	=	{file://localhost/Users/manu/Documents/articles/BouCamGra06.pdf},
	Pages	=	{631 -- 643},
	Publisher	=	{Springer},
	Series	=	lncs,
	Title	=	{The General Purpose Analog Computer and Computable Analysis are Two Equivalent Paradigms of Analog Computation},
	Url	=	{http://dx.doi.org/10.1007/11750321_60},
	Volume	=	{3959},
	Year	=	{2006},
	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.}}


@phdthesis{hainry06,
	Author	=	{Hainry, Emmanuel},
	Month	=	dec,
	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	=	phdthesis,
	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}
}


@article{bh05-tcs,
	Author	=	{Bournez, Olivier and Hainry, Emmanuel},
	Journal	=	tcs,
	Keywords	=	{Analog computation; Recursive analysis; Real recursive functions; Computability; Analysis},
	Local-Url	=	{file://localhost/Users/manu/Documents/articles/BouHai05.pdf},
	Month	=	dec,
	Number	=	{2-3},
	Pages	=	{130--147},
	Title	=	{Elementary computable functions over the real numbers and {R}-sub-recursive functions},
	Url	=	{http://dx.doi.org/10.1016/j.tcs.2005.09.010},
	Volume	=	{348},
	Year	=	{2005},
	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.}}


@inproceedings{bh04-mcu,
	Author	=	{Bournez, Olivier and Hainry, Emmanuel},
	Booktitle	=	{Machines, Computations, and Universality, MCU 2004},
	Editor	=	{Margenstern, Maurice},
	Local-Url	=	{file://localhost/Users/manu/Documents/articles/BouHai04.pdf},
	Loria	=	{bournez04c,A04-R-290},
	Pages	=	{116-127},
	Publisher	=	{Springer-Verlag},
	Series	=	lncs,
	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.}}


@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	=	apr,
	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},
	Pages	=	{269-280},
	Series	=	lncs,
	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	=	jul,
	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.},
}