1 citations · 2 across the 5 of their papers we have counts for
5 papers
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…
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…