8 citations · 24 across the 20 of their papers we have counts for
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…