Author name cluster

James I. Lathrop

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2020 Journal Article

Robust biomolecular finite automata

Titus H. Klinge
James I. Lathrop
Jack H. Lutz

We present a uniform method for translating an arbitrary nondeterministic finite automaton (NFA) into a deterministic mass action input/output chemical reaction network (I/O CRN) that simulates it. The I/O CRN receives its input as a continuous time signal consisting of concentrations of chemical species that vary to represent the NFA's input string in a natural way. The I/O CRN exploits the inherent parallelism of chemical kinetics to simulate the NFA in real time with a number of chemical species that is linear in the size of the NFA. We prove that the simulation is correct and that it is robust with respect to perturbations of the input signal, the initial concentrations of species, the output (decision), and the rate constants of the reactions of the I/O CRN.

Details DOI

TCS Journal 2009 Journal Article

Strict self-assembly of discrete Sierpinski triangles

James I. Lathrop
Jack H. Lutz
Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i. e. , the task of tiling a discrete Sierpinski triangle and nothing else. We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2007).

Details DOI

TCS Journal 2004 Journal Article

Finite-state dimension

Jack J. Dai
James I. Lathrop
Jack H. Lutz
Elvira Mayordomo

Classical Hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. The theorem of Eggleston (Quart. J. Math. Oxford Ser. 20 (1949) 31–36) relating Hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). Every rational sequence has finite-state dimension 0, but every rational number in [0, 1] is the finite-state dimension of a sequence in the low-level complexity class AC0. Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.

Details DOI

I&C Journal 1999 Journal Article

Recursive Computational Depth

James I. Lathrop
Jack H. Lutz

In the 1980s, Bennett introduced computational depth as a formal measure of the amount of computational history that is evident in an object's structure. In particular, Bennett identified the classes of weakly deep and strongly deep sequences and showed that the halting problem is strongly deep. Juedes, Lathrop, and Lutz subsequently extended this result by defining the class of weakly useful sequences and proving that every weakly useful sequence is strongly deep. The present paper investigates refinements of Bennett's notions of weak and strong depth, called recursively weak depth (introduced by Fenner, Lutz, and Mayordomo) and recursively strong depth (introduced here). It is argued that these refinements naturally capture Bennett's idea that deep objects are those which “contain internal evidence of a nontrivial causal history. ” The fundamental properties of recursive computational depth are developed, and it is shown that the recursively weakly (respectively, strongly) deep sequences form a proper subclass of the class of weakly (respectively, strongly) deep sequences. The above-mentioned theorem of Juedes, Lathrop, and Lutz is then strengthened by proving that every weakly useful sequence is recursively strongly deep. It follows from these results that not every strongly deep sequence is weakly useful, thereby answering a question posed by Juedes.

Details DOI

TCS Journal 1994 Journal Article

Computational depth and reducibility

David W. Juedes
James I. Lathrop
Jack H. Lutz

This paper reviews and investigates Bennett's notions of strong and weak computational depth (also called logical depth) for infinite binary sequences. Roughly, an infinite binary sequence x is defined to be weakly useful if every element of nonnegligible set of decidable sequences is reducible to x in recursively bounded time. It is shown that every weakly useful sequence is strongly deep. This result (which generalizes Bennett's observation that the halting problem is strongly deep) implies that every high Turing degree contains strongly deep sequences. It is also shown that, in the sense of Baire category, almost every infinite binary sequence is weakly deep, but not strongly deep.

Details DOI