Search

We consider non-cooperative binding, so-called 'temperature 1', in deterministic or directed (called here confluent) tile self-assembly systems in two dimensions and show a necessary and sufficient condition for such system to have an ultimately periodic assembly path. We prove that an infinite maximal assembly has an ultimately periodic assembly path if and only if it contains an infinite assembly path that does not intersect a periodic path in the Z2 grid. Moreover we show that every infinite assembly must satisfy this condition, and therefore, contains an ultimately periodic path. This result is obtained through a super-position and a combination of two paths that produce a new path with desired properties, a technique that we call co-grow of two paths. The paper is an updated and improved version of the first part of arXiv 1901.08575., Comment: 16 pages, 11 pictures. arXiv admin note: substantial text overlap with arXiv:1901.08575

We consider non cooperative binding in so called `temperature 1', in deterministic (here called {\it confluent}) tile self-assembly systems (1-TAS) and prove the standing conjecture that such systems do not have universal computational power. We call a TAS whose maximal assemblies contain at least one ultimately periodic assembly path {\it para-periodic}. We observe that a confluent 1-TAS has at most one maximal producible assembly, $\alpha_{max}$, that can be considered a union of path assemblies, and we show that such a system is always para-periodic. This result is obtained through a superposition and a combination of two paths that produce a new path with desired properties, a technique that we call \emph{co-grow} of two paths. Moreover we provide a characterization of an $\alpha_{max}$ of a confluent 1-TAS as one of two possible cases, so called, a grid or a disjoint union of combs. To a given $\alpha_{max}$ we can associate a finite labeled graph, called \emph{quipu}, such that the union of all labels of paths in the quipu equals $\alpha_{max}$, therefore giving a finite description for $\alpha_{max}$. This finite description implies that $\alpha_{max}$ is a union of semi-affine subsets of $\mathbb{Z}^2$ and since such a finite description can be algorithmicly generated from any 1-TAS, 1-TAS cannot have universal computational power.

The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of "invisible" pebbles (as opposed to the usual "visible" ones). The resulting pebble tree automata recognize the regular tree languages (i.e., can validate all generalized DTD's) and hence can find all matches of MSO definable patterns. Moreover, when viewed as a navigational device, they lead to an XPath-like formalism that has a path expression for every MSO definable binary pattern. The resulting pebble tree transducers can apply arbitrary MSO definable tests to (the observable part of) their configurations, they (still) have a decidable typechecking problem, and they can model the recursion mechanism of XSLT. The time complexity of the typechecking problem for conjunctive queries that use MSO definable patterns can often be reduced through the use of invisible pebbles., Comment: 96 pages, 6 figures, 7 tables

We present counterexamples to a 30-year-old conjecture of Las Vergnas [J. Combin. Theory Ser. B, 1988] regarding the Tutte polynomial of binary matroids., Comment: 3 pages, no figures, supplementary sage source files can be found in the gzipped tar source file

We consider global dynamics of reaction systems as introduced by Ehrenfeucht and Rozenberg. The dynamics is represented by a directed graph, the so-called transition graph, and two reaction systems are considered equivalent if their corresponding transition graphs are isomorphic. We introduce the notion of a skeleton (a one-out graph) that uniquely defines a directed graph. We provide the necessary and sufficient conditions for two skeletons to define isomorphic graphs. This provides a necessary and sufficient condition for two reactions systems to be equivalent, as well as a characterization of the directed graphs that correspond to the global dynamics of reaction systems., Comment: 14 pages, 6 figures

Non-deterministic Constraint Logic is a family of graph games introduced by Demaine and Hearn that facilitates the construction of complexity proofs. It is convenient for the analysis of games, providing a uniform view. We focus on the acyclic version, apply this to Klondike, Mahjong Solitaire and Nonogram (that requires planarity), and discuss the more complicated game of Dou Shou Qi. While for the first three games we reobtain known characterizations in a simple and uniform manner, the result for Dou Shou Qi is new., Comment: 14 pages, originally published at: ICGA Journal Vol. 37, pp. 3-16, 2014

Binary delta-matroids are closed under vertex flips, which consist of the natural operations of twist and loop complementation. In this note we provide an extension of this result from GF(2) to GF(4). As a consequence, quaternary matroids are "safe" under vertex flips (vf-safe for short). As an application, we find that the matroid of a bicycle space of a quaternary matroid is independent of the chosen representation. This extends a result of Vertigan [J. Comb. Theory B (1998)] concerning the bicycle dimension of quaternary matroids., Comment: 8 pages, no figures, the contents of this paper is now merged into v2 of [arXiv:1210.7718] (except for this comment, v2 is identical to v1)

In contrast to matroids, vf-safe delta-matroids have three kinds of minors and are closed under the operations of twist and loop complementation. We show that the delta-matroids representable over GF(4) with respect to the nontrivial automorphism of GF(4) form a subclass of the vf-safe delta-matroids closed under twist and loop complementation. In particular, quaternary matroids are vf-safe. Using this result, we show that the matroid of a bicycle space of a quaternary matroid M is obtained from M by using loop complementation. As a consequence, the matroid of a bicycle space of a quaternary matroid M is independent of the chosen representation. This also leads to, e.g., an extension of a known parity-type characterization of the bicycle dimension, a generalization of the tripartition of Rosenstiehl and Read [Ann. Disc. Math. (1978)], and a suitable generalization of the dual notions of bipartite and Eulerian binary matroids to a vf-safe delta-matroids. Finally, we generalize a number of results concerning the Penrose polynomial from binary matroids to vf-safe delta-matroids. In this general setting the Penrose polynomial turns out to have a recursive relation much like the recursive relation of the Tutte polynomial., Comment: 26 pages, 4 figures, the paper is significantly revised w.r.t. v1 and the contents of [arXiv:1302.4415] is now merged into this paper

If $G$ is a looped graph, then its adjacency matrix represents a binary matroid $M_{A}(G)$ on $V(G)$. $M_{A}(G)$ may be obtained from the delta-matroid represented by the adjacency matrix of $G$, but $M_{A}(G)$ is less sensitive to the structure of $G$. Jaeger proved that every binary matroid is $M_{A}(G)$ for some $G$ [Ann. Discrete Math. 17 (1983), 371-376]. The relationship between the matroidal structure of $M_{A}(G)$ and the graphical structure of $G$ has many interesting features. For instance, the matroid minors $M_{A}(G)-v$ and $M_{A}(G)/v$ are both of the form $M_{A}(G^{\prime}-v)$ where $G^{\prime}$ may be obtained from $G$ using local complementation. In addition, matroidal considerations lead to a principal vertex tripartition, distinct from the principal edge tripartition of Rosenstiehl and Read [Ann. Discrete Math. 3 (1978), 195-226]. Several of these results are given two very different proofs, the first involving linear algebra and the second involving set systems or delta-matroids. Also, the Tutte polynomials of the adjacency matroids of $G$ and its full subgraphs are closely connected to the interlace polynomial of Arratia, Bollob\'{a}s and Sorkin [Combinatorica 24 (2004), 567-584]., Comment: v1: 19 pages, 1 figure. v2: 20 pages, 1 figure. v3:29 pages, no figures. v3 includes an account of the relationship between the adjacency matroid of a graph and the delta-matroid of a graph. v4: 30 pages, 1 figure. v5: 31 pages, 1 figure. v6: 38 pages, 3 figures. v6 includes a discussion of the duality between graphic matroids and adjacency matroids of looped circle graphs

We provide a unified framework in which the interlace polynomial and several related graph polynomials are defined more generally for multimatroids and delta-matroids. Using combinatorial properties of multimatroids rather than graph-theoretical 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 delta-matroids that correspond to new interrelationships and results for the corresponding graphs polynomials. As a tool we prove the equivalence of tight 3-matroids and delta-matroids closed under the operations of twist and loop complementation, called vf-safe delta-matroids. This result is of independent interest and related to the equivalence between tight 2-matroids and even delta-matroids observed by Bouchet., Comment: 35 pages, 3 figures

We show that the symmetric difference distance measure for set systems, and more specifically for delta-matroids, corresponds to the notion of nullity for symmetric and skew-symmetric matrices. In particular, as graphs (i.e., symmetric matrices over GF(2)) may be seen as a special class of delta-matroids, this distance measure generalizes the notion of nullity in this case. We characterize delta-matroids in terms of equicardinality of minimal sets with respect to inclusion (in addition we obtain similar characterizations for matroids). In this way, we find that, e.g., the delta-matroids obtained after loop complementation and after pivot on a single element together with the original delta-matroid fulfill the property that two of them have equal "null space" while the third has a larger dimension., Comment: Changes w.r.t. v4: different style, Section 8 is extended, and in addition a few small changes are made in the rest of the paper. 15 pages, no figures

We show that the effect of principal pivot transform on the nullity values of the principal submatrices of a given (square) matrix is described by the symmetric difference operator (for sets). We consider its consequences for graphs, and in particular generalize the recursive relation of the interlace polynomial and simplify its proof., Comment: small revision of Section 8 w.r.t. v2, 14 pages, 6 figures

We study the interplay between principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S_3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized., Comment: 21 pages, 7 figures, significant additions w.r.t. v3 are Thm 7 and Remark 25

We consider principal pivot transform (pivot) on graphs. We define a natural variant of this operation, called dual pivot, and show that both the kernel and the set of maximally applicable pivots of a graph are invariant under this operation. The result is motivated by and applicable to the theory of gene assembly in ciliates., Comment: modest revision (including different latex style) w.r.t. v2, 16 pages, 5 figures

We give a characterization of the effect of sequences of pivot operations on a graph by relating it to determinants of adjacency matrices. This allows us to deduce that two sequences of pivot operations are equivalent iff they contain the same set S of vertices (modulo two). Moreover, given a set of vertices S, we characterize whether or not such a sequence using precisely the vertices of S exists. We also relate pivots to perfect matchings to obtain a graph-theoretical characterization. Finally, we consider graphs with self-loops to carry over the results to sequences containing both pivots and local complementation operations., Comment: 16 pages

Gene assembly is an intricate biological process that has been studied formally and modeled through string and graph rewriting systems. Recently, a restriction of the general (intramolecular) model, called simple gene assembly, has been introduced. This restriction has subsequently been defined as a string rewriting system. We show that by extending the notion of overlap graph it is possible to define a graph rewriting system for two of the three types of rules that make up simple gene assembly. It turns out that this graph rewriting system is less involved than its corresponding string rewriting system. Finally, we give characterizations of the `power' of both types of graph rewriting rules. Because of the equivalence of these string and graph rewriting systems, the given characterizations can be carried over to the string rewriting system., Comment: 12 pages, 9 figures

String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure. Here we elaborate this result, and match the number of heads to the arity of the transitive closure. More precisely, first-order logic with k-ary deterministic transitive closure has the same power as deterministic automata walking on their input with k heads, additionally using a finite set of nested pebbles. This result is valid for strings, ordered trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Other examples of such families are grids, toruses, and rectangular mazes. For nondeterministic automata, the logic is restricted to positive occurrences of transitive closure. The special case of k=1 for trees, shows that single-head deterministic tree-walking automata with nested pebbles are characterized by first-order logic with unary deterministic transitive closure. This refines our earlier result that placed these automata between first-order and monadic second-order logic on trees., Comment: Paper for Logical Methods in Computer Science, 27 pages, 1 figure

Formal models for gene assembly in ciliates have been developed, in particular the string pointer reduction system (SPRS) and the graph pointer reduction system (GPRS). The reduction graph is a valuable tool within the SPRS, revealing much information about how gene assembly is performed for a given gene. The GPRS is more abstract than the SPRS and not all information present in the SPRS is retained in the GPRS. As a consequence the reduction graph cannot be defined for the GPRS in general, but we show that it can be defined (in an equivalent manner as defined for the SPRS) if we restrict ourselves to so-called realistic overlap graphs. Fortunately, only these graphs correspond to genes occurring in nature. Defining the reduction graph within the GPRS allows one to carry over several results within the SPRS that rely on the reduction graph., Comment: 22 pages, 14 figures

The biological process of gene assembly has been modeled based on three types of string rewriting rules, called string pointer rules, defined on so-called legal strings. It has been shown that reduction graphs, graphs that are based on the notion of breakpoint graph in the theory of sorting by reversal, for legal strings provide valuable insights into the gene assembly process. We characterize which legal strings obtain the same reduction graph (up to isomorphism), and moreover we characterize which graphs are (isomorphic to) reduction graphs., Comment: 24 pages, 13 figures

Gene assembly in ciliates is an extremely involved DNA transformation process, which transforms a nucleus, the micronucleus, to another functionally different nucleus, the macronucleus. In this paper we characterize which loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) can possibly be applied in the transformation of a given gene from its micronuclear form to its macronuclear form. We also characterize in which order these loop recombination operations are applicable. This is done in the abstract and more general setting of so-called legal strings., Comment: 22 pages, 14 figures

Gene assembly in ciliates is one of the most involved DNA processings going on in any organism. This process transforms one nucleus (the micronucleus) into another functionally different nucleus (the macronucleus). We continue the development of the theoretical models of gene assembly, and in particular we demonstrate the use of the concept of the breakpoint graph, known from another branch of DNA transformation research. More specifically: (1) we characterize the intermediate gene patterns that can occur during the transformation of a given micronuclear gene pattern to its macronuclear form; (2) we determine the number of applications of the loop recombination operation (the most basic of the three molecular operations that accomplish gene assembly) needed in this transformation; (3) we generalize previous results (and give elegant alternatives for some proofs) concerning characterizations of the micronuclear gene patterns that can be assembled using a specific subset of the three molecular operations., Comment: 30 pages, 13 figures

String transductions that are definable in monadic second-order (mso) logic (without the use of parameters) are exactly those realized by deterministic two-way finite state transducers. Nondeterministic mso definable string transductions (i.e., those definable with the use of parameters) correspond to compositions of two nondeterministic two-way finite state transducers that have the finite visit property. Both families of mso definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite state transducers with the finite visit property that are allowed to rewrite their input tape., Comment: 63 pages, LaTeX2e. Extended abstract presented at 26-th ICALP, 1999