Selected publications at LSV: 2004

MS04
Nicolas Markey and Philippe SchnoebelenA PTIME-Complete Matching Problem for SLP-Compressed WordsInformation Processing Letters 90(1), pages 3-6, 2004.
PDF | PS | PS.GZ
doi: 10.1016/j.ipl.2004.01.002
Abstract:
SLP-compressed words are words given by simple deterministic grammars called "straight-line programs". We prove that the problem of deciding whether an SLP-compressed word is recognized by a FSA is complete for polynomial-time.

@article{ms-IPL2004,
   author = {Markey, Nicolas and Schnoebelen, {\relax Ph}ilippe},
   DOI = {10.1016/j.ipl.2004.01.002},
   journal = {Information Processing Letters},
   month = jan,
   number = {1},
   pages = {3-6},
   publisher = {Elsevier Science Publishers},
   title = {A {PTIME}-Complete Matching Problem for {SLP}-Compressed Words},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/MarSch-IPL2004.pdf},
   volume = {90},
   year = {2004},
}

About LSV