, as postdoctoral fellow. This research is performed at
. Project duration: Oct. 1, 2013  Sept. 30, 2016.
This is an extended version of the official project summary for the layman.
Selfassembly is the process in which intricate structures are obtained by spontaneous assembly of smaller building blocks. Selfassembly is present in a wide range of processes, and appears at various scales in nature. For example, the spontaneous formation of a molecular crystal and even the development of a single cell to a fullgrown multicellular organism may be seen as (highlyinvolved) selfassembly processes. Selfassembly techniques are fundamental for the development of nanotechnology.
The computing potential of selfassembly has recently been studied and partially experimentally verified. While there are now various selfassembly models available, their computational power is often too large to be either physically implementable or successfully analyzable. We often need only small computational power. So, why not compromise some of this power to obtain models that are more easy to implement or to analyze? Therefore, in this project, I aim to consider distinctly less powerful models in order to obtain models having some of these other attractive properties.
See the publications and slides listed below. Stay tuned for an explanation for the layman of some of these results.
Below are the publications belonging to this project. Slides of the talks are provided as well. See here for all my publications.

R. Brijder, Dominance and Deficiency for Petri Nets and Chemical Reaction Networks. arXiv preprint 1503.04005. Journal version of DNA21 paper.
Abstract
Inspired by Anderson et al. [J. R. Soc. Interface, 2014] we study the longterm behavior of discrete chemical reaction networks (CRNs). In particular, using techniques from both Petri net theory and CRN theory, we provide a powerful sufficient condition for a structurallybounded CRN to have the property that none of the nonterminal reactions can fire for all its recurrent configurations. We compare this result and its proof with a related result of Anderson et al. and show its consequences for the case of CRNs with deficiency one.

R. Brijder, Minimal Output Unstable Configurations in Chemical Reaction Networks and Deciders, To appear in Natural Computing, 2015. arXiv preprint 1404.3166. Journal version of DNA20 paper.
Abstract
We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently compute their finite set of minimal output unstable configurations. As a consequence, a relatively large set of configurations may be efficiently checked for output stability. We also provide a number of observations regarding the semilinearity result of Angluin et al. (Distrib Comput 20(4):279–304, 2007) from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computationfriendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.

R. Brijder, Dominance and Tinvariants for Petri Nets and
Chemical Reaction Networks, DNA Computing and Molecular Programming  21th International Conference (DNA 21) (A. Philips and P. Yin, eds.), Lecture Notes in Computer Science, v. 9211, 115, 2015. Local copy. Slides.
Abstract
Inspired by Anderson et al. [J. R. Soc. Interface, 2014] we
study the longterm behavior of discrete chemical reaction networks
(CRNs). In particular, using techniques from both Petri net theory and
CRN theory, we provide a powerful sufficient condition for a structurallybounded
CRN to have the property that none of the nonterminal reactions
can fire for all its recurrent configurations. We compare this result
and its proof with a related result of Anderson et al. and show its consequences
for the case of CRNs with deficiency one.

R. Brijder, Recombination Faults in Gene Assembly in Ciliates
Modeled Using Multimatroids, To appear in Theoretical Computer Science. Local copy.
Abstract
We formally model the process of gene assembly in ciliates on the level of individual
genes using the notion of multimatroids introduced by Bouchet. Gene
assembly involves heavy splicing and recombination, and it turns out that multimatroids
form a suitable abstract model that captures essential features of this
process. We use this abstract model to study the effect of faulty recombinations
during the gene assembly process.

R. Brijder and Lorenzo Traldi, Isotropic matroids. II. Circle graphs. arXiv preprint 1504.04299.
Abstract
We present several characterizations of circle graphs, which follow from Bouchet's circle graph obstructions theorem.

R. Brijder and Lorenzo Traldi, Isotropic matroids. I. Multimatroids and neighborhoods. arXiv preprint 1503.04406.
Abstract
We discuss the connections between two kinds of combinatorial structures associated with looped simple graphs: isotropic matroids and binary multimatroids. In addition, we detail the connection between isotropic matroids and vertex neighborhoods in families of locally equivalent graphs.

R. Brijder, Output Stability and Semilinear Sets in Chemical Reaction Networks and Deciders, DNA Computing and Molecular Programming  20th International Conference (DNA 20) (S. Murata and S. Kobayashi, eds.), Lecture Notes in Computer Science, v. 8727, 100113, 2014. Local copy. Slides.
Abstract
We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently calculate the (finite) set of minimal output stable configurations. As a consequence, a relatively large sequence of configurations may be efficiently checked for output stability.
We also provide a number of observations regarding the semilinearity result of Angluin et al. [Distrib. Comput., 2007] from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computationfriendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.

R. Brijder and H.J. Hoogeboom, Graph Polynomials Motivated by Gene Rearrangements in Ciliates,
10th Conference on Computability in Europe (CiE 2014), Lecture Notes in Computer Science, v. 8493, 6372, 2014. Local copy. Slides.
Abstract
Gene rearrangements within the process of gene assembly in ciliates can be represented using a 4regular graph. Based on this observation, Burns et al. [Discrete Appl. Math., 2013] propose a graph polynomial abstracting basic features of the assembly process, like the number of segments excised. We show that this assembly polynomial is essentially (i) a single variable case of the transition polynomial by Jaeger and (ii) a special case of the bracket polynomial introduced for simple graphs by Traldi and Zulli.

R. Brijder and H.J. Hoogeboom, Interlace Polynomials for Multimatroids and DeltaMatroids, European Journal of Combinatorics, v. 40, 142167, 2014. arXiv preprint 1010.4678.
Abstract
We provide a unified framework in which the interlace polynomial and several related graph polynomials are defined more generally for multimatroids and deltamatroids. Using combinatorial properties of multimatroids rather than graphtheoretical arguments, we find that various known results about these polynomials, including their recursive relations, are both more efficiently and more generally obtained. In addition, we obtain several interrelationships and results for polynomials on multimatroids and deltamatroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence of tight 3matroids and deltamatroids closed under the operations of twist and loop complementation, called vfsafe deltamatroids. This result is of independent interest and related to the equivalence between tight 2matroids and even deltamatroids observed by Bouchet.
Below are the slides of invited talks belonging to this project. See above for slides of conference talks belonging to contributed papers.