BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Olivier Bournez

Olivier Bournez appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer ScienceDistributed, Parallel, and Cluster ComputingComputational ComplexityComputer Science and Game Theorymath.LO

Catalog footprint

What is connected

6works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

Surreal fields stable under exponential and logarithmic functions

Surreal numbers, have a very rich and elegant theory. This class of numbers, denoted by No, includes simultaneously the ordinal numbers and the real numbers, and forms a universal huge real closed field: It is universal in the sense that any real closed field can be embedded in it. Following Gonshor, surreal numbers can also be seen as signs sequences of ordinal length, with some exponential and logarithmic functions that extend the usual functions over the reals. No can actually also be seen as an elegant particular (generalized) power series field with real coefficients, namely Hahn series with exponents in No itself. It can also be considered as a particular field of transseries, providing tools to do some analysis and asymptotic analysis for functions over the continuum, providing natural concepts for discussing hyperexponential or sublogarithm functions, and their asymptotics. In this article, we consider stability of subfields of No under exponential and logarithmic functions. Namely, we consider the set surreal numbers whose signs sequences have length less than some ordinal λ. Extending the discussion from van den Dries and Ehrlich, we show that is stable by exponential and logarithm iff λ is some ε-number. Motivated in a longer term by computability issues using ordinal machines, we consider subfields stables by exponential and logarithmic functions defined by Hahn series that does not require to go up to cardinal lengths and exponents. We prove that No can be expressed as a strict hierarchy of subfields stable by exponential and logarithmic functions. This provides many explicit examples of subfields of No stable by exponential and logarithmic functions, and does not require to go up to a cardinal λ to provide such examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Continuous Ordinary Differential Equations and Transfinite Computations

We consider Continuous Ordinary Differential Equations (CODE) y'=f(y), where f is a continuous function. They are known to always have solutions for a given initial condition y(0)=y0, these solutions being possibly non unique. We restrict to our attention to a class of continuous functions, that we call greedy: they always admit unique greedy solutions, i.e. going in greedy way in some fixed direction. We prove that they can be seen as models of computation over the ordinals and conversely in a very strong sense. In particular, for such ODEs, to a greedy trajectory can be associated some ordinal corresponding to some time of computation, and conversely models of computation over the ordinals can be associated to some CODE. In particular, analyzing reachability for one or the other concept with respect to greedy trajectories has the same hardness. This also brings new perspectives on analysis in Mathematics, by providing ways to translate results for ITTMs to CODEs. This also extends some recent results about the relations between ordinary differential equations and Turing machines, and more widely with (generalized) computability theory.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Framework for Algebraic Characterizations in Recursive Analysis

Algebraic characterizations of the computational aspects of functions defined over the real numbers provide very effective tool to understand what computability and complexity over the reals, and generally over continuous spaces, mean. This is relevant for both communities of computer scientists and mathematical analysts, particularly the latter who do not understand (and/or like) the language of machines and string encodings. Recursive analysis can be considered the most standard framework of computation over continuous spaces, it is however defined in a very machine specific way which does not leave much to intuitiveness. Recently several characterizations, in the form of function algebras, of recursively computable functions and some sub-recursive classes were introduced. These characterizations shed light on the hidden behavior of recursive analysis as they convert complex computational operations on sequences of real objects to "simple" intuitive mathematical operations such as integration or taking limits. The authors previously presented a framework for obtaining algebraic characterizations at the complexity level over compact domains. The current paper presents a comprehensive extension to that framework. Though we focus our attention in this paper on functions defined over the whole real line, the framework, and accordingly the obtained results, can be easily extended to functions defined over arbitrary domains.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Homonym Population Protocols

The population protocol model was introduced by Angluin \emph{et al.} as a model of passively mobile anonymous finite-state agents. This model computes a predicate on the multiset of their inputs via interactions by pairs. The original population protocol model has been proved to compute only semi-linear predicates and has been recently extended in various ways. In the community protocol model by Guerraoui and Ruppert, agents have unique identifiers but may only store a finite number of the identifiers they already heard about. The community protocol model provides the power of a Turing machine with a $O(n\log n)$ space. We consider variations on the two above models and we obtain a whole landscape that covers and extends already known results. Namely, by considering the case of homonyms, that is to say the case when several agents may share the same identifier, we provide a hierarchy that goes from the case of no identifier (population protocol model) to the case of unique identifiers (community protocol model). We obtain in particular that any Turing Machine on space $O(\log^{O(1)} n)$ can be simulated with at least $O(\log^{O(1)} n)$ identifiers, a result filling a gap left open in all previous studies. Our results also extend and revisit in particular the hierarchy provided by Chatzigiannakis \emph{et al.} on population protocols carrying Turing Machines on limited space, solving the problem of the gap left by this work between per-agent space $o(\log \log n)$ (proved to be equivalent to population protocols) and $O(\log n)$ (proved to be equivalent to Turing machines).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Asymetric Pavlovian Populations

Population protocols have been introduced by Angluin et al. as a model of networks consisting of very limited mobile agents that interact in pairs but with no control over their own movement. A collection of anonymous agents, modeled by finite automata, interact pairwise according to some rules that update their states. Predicates on the initial configurations that can be computed by such protocols have been characterized as semi-linear predicates. In an orthogonal way, several distributed systems have been termed in literature as being realizations of games in the sense of game theory. We investigate under which conditions population protocols, or more generally pairwise interaction rules, correspond to games. We show that restricting to asymetric games is not really a restric- tion: all predicates computable by protocols can actually be computed by protocols corresponding to games, i.e. any semi-linear predicate can be computed by a Pavlovian population multi-protocol.

0 citations0 reviewsNo code linkedOpen access