Selected publications at LSV

Abstract:
The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining directness and codirectness in Post Embedding problems leads to undecidability.

@inproceedings{KS-csr12,
   address = {Nizhni Novgorod, Russia},
   author = {Karandikar, Prateek and Schnoebelen, {\relax Ph}ilippe},
   booktitle = {{P}roceedings of the 7th {I}nternational {C}omputer {S}cience {S}ymposium in {R}ussia ({CSR}'12)},
   DOI = {10.1007/978-3-642-30642-6_22},
   editor = {Hirsch, Edward A. and Karhum{\"a}ki, Juhani and Lepist{\"o}, Arto and Prilutskii, Michail},
   month = jul,
   pages = {229-240},
   publisher = {Springer},
   series = {Lecture Notes in Computer Science},
   title = {Cutting Through Regular {P}ost Embedding Problems},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/KS-csr12.pdf},
   volume = {7353},
   year = {2012},
}

About LSV

Select by Year