Conference rusure::math

1032.0. "Kolmogorov Comp. request and survey cites." by CADSYS::COOPER (Topher Cooper) Wed Feb 22 1989 12:46

Newsgroups: sci.math,sci.logic,sci.philosophy.tech,sci.math.stat,sci.physics
Path: decwrl!ucbvax!ucsd!sdcsvax!ucsdhub!esosun!seismo!uunet!mcvax!paulv
Subject: Kolmogorov complexity textbook
Posted: 20 Feb 89 15:14:42 GMT
Organization: 
Xref: decwrl sci.math:6162 sci.logic:362 sci.philosophy.tech:1013 sci.math.stat:603 sci.physics:6408
 
 
      Textbook on Kolmogorov Complexity: in the making
 
 
 
 
 
For some time we have been engaged in a project to  write  a
book  on  ``Introduction  to  Kolmogorov  Complexity and its
Applications,'' by Ming Li and Paul Vitanyi, to be published
by  Addison-Wesley,  1990? We are aiming at a self-contained
text-book with many examples and exercises  in  both  Kolmo-
gorov  complexity  (KC)  and its applications. We strive for
comprehensive treatment of KC and all known applications  of
KC,  either  to use in the main text or as examples or exer-
cises.  Knowledge on the subject is scattered far and  wide,
in  different locations like East and West, and in different
disciplines like Statistics, Logics, Computer Science,  Pro-
bability  Theory, Philosophy, Mathematics.  Therefore we ask
your help. If you know of any nice examples or exercises (no
matter how trivial or difficult) we would be grateful if you
could you send them to us.
 
     We sollicit any help and suggestions you can give us on
subjects  you  feel  are  missing in the surveys below, more
detail on subjects that are mentioned,  examples  and  exer-
cises,  work  that  is  not  referenced  or  is missing.  (A
separate  comprehensive   bibliography   is   available   on
request.)
 
     Unpublished material we use will be  properly  credited
in  the  main  text of all versions. Lemmas, examples, exer-
cises and so on will be properly attributed.
 
     Addresses  (we  prefer  you  to  use  the   Netherlands
address): Ming Li, Computer Science Department, York Univer-
sity,  4700  Keeler  Street,   Ontario,   Canada   M3J   1P3
([email protected]);  or  Paul  Vitanyi, CWI, Kruislaan 413,
1098 SJ Amsterdam, The Netherlands  ([email protected]  or
[email protected]).
 
Some pilot publications:
 
M. Li and P.M.B. Vitanyi, Two Decades of Applied  Kolmogorov
Complexity,  Proc.  3rd  IEEE Structure in Complexity Theory
Conference, 1988, pp.  80-101.  (Full  expanded  version  to
appear  as  "Kolmogorov  Complexity and its Applications" in
the `Handbook of  Theoretical  Computer  Science'  (Jan  van
Leeuwen,  Managing  Editor), North-Holland.  Preprint as CWI
report.)
 
M.  Li  and  P.M.B.  Vitanyi,  Kolmogorovskaya   slozhnost':
dvadsat'  let  spustia,  Uspekhi Mat. Nauk, 43:6 (1988), pp.
129-166.  (= Russian Mathematical Surveys)