Selected publications at LSV

KS14
P. Karandikar and Ph. SchnoebelenOn the state complexity of closures and interiors of regular languages with subwordsIn DCFS'14, LNCS 8614, pages 234-245. Springer-Verlag, 2014. ( PDF )
doi: 10.1007/978-3-319-09704-6_21
Abstract:
We study the state complexity of the set of subwords and superwords of regular languages, and provide new lower bounds in the case of languages over a two-letter alphabet. We also consider the dual interior sets, for which the nondeterministic state complexity has a doubly-exponential upper bound. We prove a matching doubly-exponential lower bound for downward interiors in the case of an unbounded alphabet.

@inproceedings{KS-dcfs2014,
   address = {Turku, Finland},
   author = {Karandikar, Prateek and Schnoebelen, {\relax Ph}ilippe},
   booktitle = {{P}roceedings of the 16th {W}orkshop on {D}escriptional {C}omplexity of {F}ormal {S}ystems ({DCFS}'14)},
   DOI = {10.1007/978-3-319-09704-6_21},
   editor = {J{\"u}rgensen, Helmut and Karhum{\"a}ki, Juhani and Okhotin, Alexander},
   month = aug,
   pages = {234-245},
   publisher = {Springer-Verlag},
   series = {Lecture Notes in Computer Science},
   title = {On the state complexity of closures and interiors of regular languages with subwords},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/KS-dcfs2014.pdf},
   volume = {8614},
   year = {2014},
}

About LSV