Extremal combinatorics is the study of the size that a collection of objects must have in order to certainly satisfy a given property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behavior of large reaction systems by means of extremal combinatorics. We define several different properties that capture some basic and dynamical behaviors of a reaction system and we prove that they must necessarily be satisfied if the system is large enough. Explicit bounds and formulae are also provided.

Dennunzio, A., Formenti, E., Manzoni, L. (2015). Reaction systems and extremal combinatorics properties. THEORETICAL COMPUTER SCIENCE, 598, 138-149 [10.1016/j.tcs.2015.06.001].

Reaction systems and extremal combinatorics properties

DENNUNZIO, ALBERTO
;
MANZONI, LUCA
2015

Abstract

Extremal combinatorics is the study of the size that a collection of objects must have in order to certainly satisfy a given property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behavior of large reaction systems by means of extremal combinatorics. We define several different properties that capture some basic and dynamical behaviors of a reaction system and we prove that they must necessarily be satisfied if the system is large enough. Explicit bounds and formulae are also provided.
Articolo in rivista - Articolo scientifico
Combinatorics; Natural computing; Reaction systems; Theoretical Computer Science; Computer Science (all)
English
138
149
12
Dennunzio, A., Formenti, E., Manzoni, L. (2015). Reaction systems and extremal combinatorics properties. THEORETICAL COMPUTER SCIENCE, 598, 138-149 [10.1016/j.tcs.2015.06.001].
Dennunzio, A; Formenti, E; Manzoni, L
File in questo prodotto:
File Dimensione Formato  
pubblicazione5.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 378.05 kB
Formato Adobe PDF
378.05 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/107085
Citazioni
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
Social impact