Bruce Edward Litow

We give a method to decide whether or not an

ordinary finite order linear recurrence with constant, rational

coefficients ever generates zero.

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

This paper explores the impact of geometry on computability =

and complexity in

Winfree's model of nanoscale self-assembly. We work in the =

two-dimensional

tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =

first

main theorem says that there is a roughly quadratic function f ...
more >>>

Antoine Taveneaux

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>