A note on the Kolmogorov data complexity and nonuniform logical definitions

✍ Scribed by Jerzy Tyszkiewicz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 773 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00172-5

✦ Synopsis

We define a new Kolmogorov complexity based measure of complexity of logics. Then we use this new tool to prove a sharp estimate of the length of first order sentences defining nonuniformly more complicated Lindstrijm quantifiers in terms of simpler ones. @ 1997 Published by Elsevier Science B.V.