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 / Dennunzio, Alberto; Formenti, Enrico; Manzoni, Luca. - STAMPA. - 8370:(2014), pp. 297-307. ( 8th International Conference on Language and Automata Theory and Applications, LATA 2014 Madrid, esp 2014) [10.1007/978-3-319-04921-2_24].
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
