Master’s Thesis Presentation • Algorithms and Complexity — Style Recognition in Music with Context Free Grammars and Kolmogorov ComplexityExport this event to calendar

Thursday, March 5, 2020 — 1:30 PM EST

Tiasa Mondol, Master’s candidate
David R. Cheriton School of Computer Science

The Kolmogorov Complexity of an object is incomputable. But built in its structure is a way to specify description methods of an object that is computable in some sense. Such a description method then can be exploited to quantify the bits of information needed to generate the object from scratch. 

We show that Context-Free Grammars form such a viable description method to specify an object and the size of the grammar can reliably estimate the Kolmogorov Complexity. We use such estimation in approximating the Information Distance between two musical strings. We also show that such distance measure in music can be used to recognize the genre, composer and style and also for music classification.

Location 
DC - William G. Davis Computer Research Centre
2310
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2020 (156)
    1. September (1)
    2. August (21)
    3. July (14)
    4. June (19)
    5. May (17)
    6. April (20)
    7. March (17)
    8. February (25)
    9. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)