We will study computations performed with limited memory. This will bring us into contact with several ideas in the area of randomness and computation. We will illustrate these ideas using the following toy example.
Mesh networks have become increasingly important because they can be easily implemented without much infrastructure and can support adequate bandwidth with a flexible multi-hop wireless communication among their routers serving the clients.
XZ=ZY is called the conjugacy equation. Given languages X and Y we are interested in knowing if there exists a non empty language Z which makes this equation true. This problem is undecidable in the general setting.
Suppose we have a polynomial $P$ in variables $X_1, \\ldots, X_n$ with coefficients from a field $F$, with total degree at most $d$. The polynomial $P$ is given in terms of some algebraic expression involving $X_1, \\ldots, X_n$.
I shall describe two approaches to the study of self-assembly. The first approach involves experiments with DNA molecules. We use DNA like a construction material --- akin to the uses of brick, cement, glass, etc. --- to form nanostructures.
Many stochastic systems are governed by events that, though they have a small probability of occurrence, are crucial to performance.
Large deviations is an asymptotic theory that allows