about this paper

presentation abstract bibitem

downloads

paper talk
Pierre Boutillier, Iona Cristescu, and Jérôme Feret.
Counters in Kappa: Semantics, Simulation, and Static Analysis. Jérôme Feret.
In Proceedings of the European Symposium on Programming, ESOP'19, Prague, Czech Republic, April 6-11, 2019, Luís Caires (Ed.), Lecture Notes in Computer Science 11423, pp. 176-204
© Springer-Verlag, Berlin, Germany.

Abstract: Site-graph rewriting languages, such as Kappa or BNGL, offer parsimonious ways to describe highly combinatorial systems of mechanistic interactions among proteins. These systems may be then simulated efficiently. Yet, the modeling mechanisms that involve counting (a number of phosphorylated sites for instance) require an exponential number of rules in Kappa. In BNGL, updating the set of the potential applications of rules in the current state of the system comes down to the sub-graph isomorphism problem (which is NP-complete).

In this paper, we extend Kappa to deal both parsimoniously and efficiently with counters. We propose a single push-out semantics for Kappa with counters. We show how to compile Kappa with counters into Kappa without counters (without requiring an exponential number of rules). We design a static analysis, based on affine relationships, to identify the meaning of counters and bound their ranges accordingly. 

@inproceedings{DBLP:conf/esop/BoutillierCF19,
  author    = {Pierre Boutillier and
               Ioana Cristescu and
               J{\'{e}}r{\^{o}}me Feret},
  title     = {Counters in Kappa: Semantics, Simulation, and Static Analysis},
  booktitle = {Programming Languages and Systems - 28th European Symposium on Programming,
               {ESOP} 2019, Held as Part of the European Joint Conferences on Theory
               and Practice of Software, {ETAPS} 2019, Prague, Czech Republic, April
               6-11, 2019, Proceedings},
  pages     = {176--204},
  year      = {2019},
  crossref  = {DBLP:conf/esop/2019},
  url       = {https://doi.org/10.1007/978-3-030-17184-1\_7},
  doi       = {10.1007/978-3-030-17184-1\_7},
  timestamp = {Tue, 20 Aug 2019 15:27:49 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/esop/BoutillierCF19},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/esop/2019,
  editor    = {Lu{\'{\i}}s Caires},
  title     = {Programming Languages and Systems - 28th European Symposium on Programming,
               {ESOP} 2019, Held as Part of the European Joint Conferences on Theory
               and Practice of Software, {ETAPS} 2019, Prague, Czech Republic, April
               6-11, 2019, Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {11423},
  publisher = {Springer},
  year      = {2019},
  url       = {https://doi.org/10.1007/978-3-030-17184-1},
  doi       = {10.1007/978-3-030-17184-1},
  isbn      = {978-3-030-17183-4},
  timestamp = {Tue, 14 May 2019 10:00:41 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/esop/2019},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}