Duration of project "Feasible selfassembly models": Oct. 1, 2013  Sept. 30, 2016.
Duration of project "Fault tolerance in selfassembly models": Oct. 1, 2016  Sept. 30, 2019.
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 talks are provided as well. See here for all my publications.

R. Brijder, Dominance and Deficiency for Petri Nets and Chemical Reaction Networks, Natural Computing, v. 16, 285294, 2017. 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 and Lorenzo Traldi, Isotropic matroids III: Connectivity, Electronic Journal of Combinatorics, v. 24, P2.49, 2017. arXiv preprint 1602.03899.
Abstract
The isotropic matroid M[IAS(G)] of a graph G is a binary matroid, which is equivalent to the isotropic system introduced by Bouchet. In this paper we discuss four notions of connectivity related to isotropic matroids and isotropic systems. We show that the isotropic system connectivity defined by Bouchet is equivalent to vertical connectivity of M[IAS(G)], and if G has at least four vertices, then M[IAS(G)] is vertically 5connected if and only if G is prime (in the sense of Cunningham's split decomposition). We also show that MIAS(G)] is 3connected if and only if G is connected and has neither a pendant vertex nor a pair of twin vertices. Our most interesting theorem is that if G has n >= 7 vertices then M[IAS(G)] is not vertically nconnected. This abstractseeming result is equivalent to the more concrete assertion that G is locally equivalent to a graph with a vertex of degree < n1/2.

R. Brijder, D. Doty, and D. Soloveichik, Robustness of Expressivity in Chemical Reaction Networks, DNA Computing and Molecular Programming  22th International Conference (DNA 22) (Y. Rondelez and D. Woods, eds.), Lecture Notes in Computer Science, v. 9818, 5266, 2016.
Abstract
We show that some natural output conventions for errorfree computation in chemical reaction networks (CRN) lead to a common level of computational expressivity. Our main results are that the standard definition of errorfree CRNs have equivalent computational power to (1) asymmetric and (2) democratic CRNs. The former have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The latter define output by majority vote among “yes” and “no” voters.
Both results are proven via a generalized framework that simultaneously captures several definitions, directly inspired by a recent Petri net result of Esparza, Ganty, Leroux, and Majumder [CONCUR 2015]. These results support the thesis that the computational expressivity of errorfree CRNs is intrinsic, not sensitive to arbitrary definitional choices.

R. Brijder, Minimal Output Unstable Configurations in Chemical Reaction Networks and Deciders, Natural Computing, v. 15, 235244, 2016. 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, Theoretical Computer Science, v. 608, 2735, 2015.. 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, Electronic Journal of Combinatorics, v. 23, P4.2, 2016. 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, Electronic Journal of Combinatorics, v. 23, P4.1, 2016. 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.