Extremal combinatorics is the study of the size that a certain collection of objects must have in order to certainly satisfy a property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behaviour of large reaction systems by means of extremal combinatorics. We defined several different properties that capture some basic behaviour of a reaction system and we prove that they must necessarily be satisfied by large enough systems. Explicit bounds and formulae are also provided.
Extremal combinatorics of reaction systems
Manzoni Luca
2014-01-01
Abstract
Extremal combinatorics is the study of the size that a certain collection of objects must have in order to certainly satisfy a property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behaviour of large reaction systems by means of extremal combinatorics. We defined several different properties that capture some basic behaviour of a reaction system and we prove that they must necessarily be satisfied by large enough systems. Explicit bounds and formulae are also provided.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.