Selected publications at LSV

P. Karandikar, M. Kufleitner and Ph. SchnoebelenOn the index of Simon's congruence for piecewise testabilityInformation Processing Letters 15(4), pages 515-519, 2015. ( Web page | PDF )
doi: 10.1016/j.ipl.2014.11.008
Simon's congruence, denoted n, relates words having the same subwords of length up to n. We show that, over a k-letter alphabet, the number of words modulo n is in 2Θ(nk-1.log n).

   author = {Karandikar, Prateek and Kufleitner, Manfred and Schnoebelen, {\relax Ph}ilippe},
   DOI = {10.1016/j.ipl.2014.11.008},
   journal = {Information Processing Letters},
   month = apr,
   number = {4},
   pages = {515-519},
   publisher = {Elsevier Science Publishers},
   title = {On the index of {S}imon's congruence for piecewise testability},
   url = {},
   volume = {15},
   year = {2015},

About LSV