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, F. Geerts, J. Van den Bussche, and T. Weerwag, On the expressive power of query languages for matrices, 21th International Conference on Database Theory, ICDT 2018 (B. Kimelfeld and Y. Amsterdamer, eds.), Leibniz International Proceedings in Informatics (LIPIcs), v. 98, 10:110:17, 2018. arXiv preprint 1709.08359.
Abstract
We investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv of inverting a matrix. In MATLANG + inv we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. The evaluation problem for MATLANG + eigen is shown to be complete for the complexity class Exists R.

R. Brijder, D. Doty, and D. Soloveichik, Democratic, Existential, and ConsensusBased Output Conventions in Stable Computation by Chemical Reaction Networks, Natural Computing, v. 17, 97108, 2018. arXiv preprint 1604.03687.
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 consensusbased output convention have equivalent computational power to (1) existencebased and (2) democracybased output conventions. The CRNs using the former output convention have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The CRNs using the latter output convention 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 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.

M.D. Johnston, D.F. Anderson, G. Craciun, and R. Brijder, Conditions for Extinction Events in Chemical Reaction Networks with Discrete State Spaces, Journal of Mathematical Biology, v. 76, 15351558, 2018. arXiv preprint 1701.02012
Abstract
We study chemical reaction networks with discrete state spaces and present sufficient conditions on the structure of the network that guarantee the system exhibits an extinction event. The conditions we derive involve creating a modified chemical reaction network called a dominationexpanded reaction network and then checking properties of this network. Unlike previous results, our analysis allows algorithmic implementation via systems of equalities and inequalities and suggests sequences of reactions which may lead to extinction events. We apply the results to several networks including an EnvZOmpR signaling pathway in Escherichia coli.

R. Brijder, Orienting Transversals and Transition Polynomials of Multimatroids, Advances in Applied Mathematics, v. 94, 120155, 2018. arXiv preprint 1605.04244.
Abstract
Multimatroids generalize matroids, deltamatroids, and isotropic systems, and transition polynomials of multimatroids subsume various polynomials for these latter combinatorial structures, such as the interlace polynomial and the Tutte–Martin polynomial.
We prove evaluations of the Tutte–Martin polynomial of isotropic systems from Bouchet directly and more efficiently in the context of transition polynomials of multimatroids. Moreover, we generalize some related evaluations of the transition polynomial of 4regular graphs from Jaeger to multimatroids. These evaluations are obtained in a uniform and matroidtheoretic way. We also translate the evaluations in terms of the interlace polynomial of graphs. Finally, we give an excludedminor theorem for the class of binary tight 3matroids (a subclass of multimatroids) based on the excludedminor theorem for the class of binary deltamatroids from Bouchet.

R. Brijder, Sorting by Reversals and the Theory of 4Regular Graphs, Theoretical Computer Science, v. 701, 4053, 2017. arXiv preprint 1701.07463.
Abstract
We show that the theory of sorting by reversals fits into the wellestablished theory of circuit partitions of 4regular multigraphs (which also involves the combinatorial structures of circle graphs and deltamatroids). In this way, we expose strong connections between the two theories that have not been fully appreciated before. We also discuss a generalization of sorting by reversals involving the doublecutandjoin (DCJ) operation. Finally, we also show that the theory of sorting by reversals is closely related to that of gene assembly in ciliates.

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 some invited talks belonging to this project. See above for slides of conference talks belonging to contributed papers.