Boğaziçi University Mathematics Colloquium

On the counting and growth functions of context-free languages
Flavio D'Alessandro
Università di Roma, Italy
Özet : Given a formal language L, the counting function of L (resp., growth function of L) is the function that maps every non negative integer n into the number of words of L of length n (resp., n at most). The interest of these functions relies on the fact that the study of their asymptotic behaviour provide information on the structure of the language. In this talk we will survey some classical and recent results on the counting and growth functions of context-free languages. The talk will be self-contained.
  Tarih : 05.04.2017
  Saat : 15:00
  Yer : TB 250
  Dil : English
    Yazdır