51 citations
- Université Paris CitéFR20 papers
- Centre National de la Recherche ScientifiqueFR9 papers
- Institut national de recherche en sciences et technologies du numériqueFR5 papers
- École Normale Supérieure de LyonFR3 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR2 papers
- Laboratoire de l'Informatique du ParallélismeFR2 papers
- Orange (France)FR2 papers
- Center for Mathematical ModelingCL1 paper
- Computer Algorithms for MedicineAT1 paper
- Délégation Paris 7FR1 paper
- École Normale Supérieure - PSLFR1 paper
- Group Sense (China)CN1 paper
6 papers · 1 filter
Kolmogorov complexity in perspective
Marie Ferbus-Zanda, Serge Grigorieff
We survey the diverse approaches to the notion of information content: from Shannon entropy to Kolmogorov complexity. The main applications of Kolmogorov complexity are presented n…
Set theoretical Representations of Integers, I
Marie Ferbus-Zanda, Serge Grigorieff
We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations), in the perspective of Kolmogorov comp…
Kolmogorov complexities Kmax, Kmin on computable partially ordered sets
Marie Ferbus-Zanda, Serge Grigorieff
We introduce a machine free mathematical framework to get a natural formalization of some general notions of infinite computation in the context of Kolmogorov complexity. Namely, t…
Refinment of the "up to a constant" ordering using contructive co-immunity and alike. Application to the Min/Max hierarchy of Kolmogorov complexities
Marie Ferbus-Zanda, Serge Grigorieff
We introduce orderings between total functions f,g: N -> N which refine the pointwise "up to a constant" ordering <=cte and also insure that f(x) is often much less thang(x). With…
Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity
Marie Ferbus-Zanda, Serge Grigorieff
We consider classical representations of integers: Church's function iterators, cardinal equivalence classes of sets, ordinal equivalence classes of totally ordered sets. Since pro…
Is Randomness "Native" to Computer Science?
Marie Ferbus-Zanda, Serge Grigorieff
We survey the Kolmogorov's approach to the notion of randomness through the Kolmogorov complexity theory. The original motivation of Kolmogorov was to give up a quantitative defini…