Selected publications at LSV

Abstract:
We study the following summarization problem: given a parallel composition A = A1Vert...Vert An of labelled transition systems communicating with the environment through a distinguished component Ai, efficiently compute a summary Si such that EVert A and EVert Si are trace-equivalent for every environment E. While Si can be computed using elementary automata theory, the resulting algorithm suffers from the state-explosion problem. We present a new, simple but subtle algorithm based on net unfoldings, a partial-order semantics, give some experimental results using an implementation on top of Mole, and show that our algorithm can handle divergences and compute weighted summaries with minor modifications.

@inproceedings{EJS-fsttcs13,
   address = {Guwahati, India},
   author = {Esparza, Javier and Jezequel, Lo{\"\i}g and Schwoon, Stefan},
   booktitle = {{P}roceedings of the 33rd {C}onference on {F}oundations of {S}oftware {T}echnology and {T}heoretical {C}omputer {S}cience ({FSTTCS}'13)},
   DOI = {10.4230/LIPIcs.FSTTCS.2013.225},
   editor = {Seth, Anil and Vishnoi, Nisheeth},
   month = dec,
   pages = {225-236},
   publisher = {Leibniz-Zentrum f{\"u}r Informatik},
   series = {Leibniz International Proceedings in Informatics},
   title = {Computation of summaries using net unfoldings},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/EJS-fsttcs13.pdf},
   volume = {24},
   year = {2013},
}

About LSV