Catálogo de publicaciones - libros

We study the subshift behavior of one dimensional cellular automata and we show how to associate to any subshift of finite type a cellular automaton which contains it. The relationships between some topological properties of subshifts and the behavior of the related languages are investigated. In particular we focus our attention to the notion of full transitivity. We characterize the language related to a full transitive subshift extending the notion of irreducibility.

It is a very common procedure in biology to observe the progress of an experiment and regard the result of this observation as the final outcome. Inspired by this, a new approach for generating formal languages, called evolution/observation, has been introduced [6]. In the current work we consider evolution/observation as a new strategy also for accepting languages: a word is accepted, if the (observed) evolution of a certain system starting from this input follows a regular pattern.

We obtain the following result: checking if the (observed) evolution of a context-free system follows a regular pattern is enough to accept every recursively enumerable languages. On the other hand, if we observe the evolution of systems using very simple rules (of the kind → ), then it is possible to accept exactly the class of context-sensitive languages.

In this paper we show how to explore the classical theory of computability using the tools of Analysis: a differential scheme is substituted for the classical recurrence scheme and a limit operator is substituted for the classical minimalization. We show that most relevant problems of computability over the non negative integers can be dealt with over the reals: elementary functions are computable, Turing machines can be simulated, the hierarchy of non computable functions be represented (being the classical halting problem solvable in some level). The most typical concepts in Analysis become natural in this framework.

The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer’s) time any recursively enumerable () problem. In this paper, we provide a geometric model of computation, , that, although being based on rational numbers, has the same property: it can simulate any Turing machine and can decide any problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect.

The (Life) is a two-state, two-dimensional, nearest neighbor cellular automaton (CA), which John Horton Conway proved is universal. The (LtL) family of CAs generalizes Life to large neighborhoods and general birth and survival thresholds. A specific of Life to LtL yields , which is a CA with dynamics similar to Life. In the 1990s Conway challenged us to prove that rules such as Bosco’s are, like Life, universal. Here we show that Bosco’s rule supports patterns such as those used in the proof that Life is universal. Specifically, we build a , similar to the auxiliary storage device Conway described and claimed could be built. Our construction is based on Life’s sliding block memory designed and built by Dean Hickerson in 1990. In a companion paper we explore various questions which have arisen since Conway posed his challenge, including whether the details given in his proof that Life is universal are sufficient and what necessary and sufficient conditions are required to prove that Bosco’s rule, or any two-dimensional CA, is universal.

We introduce a new variant of membrane systems where the rules are directly assigned to membranes (and not to the regions as this is usually observed in the area of membrane systems) and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. For the application of rules leading from one configuration of the system to the succeeding configuration we consider a sequential derivation mode and do not use the mode of maximal parallelism. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for such systems using a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets generated by context-free matrix grammars (with -rules).

We present complexity hierarchies on circuits under two DLOGTIME-uniformity conditions. It is shown that there is a language which can be recognized by a family of -uniform circuits of depth  and size but not by any family of -uniform circuits of depth  and size , where > 0, >0, >1, and ≥1 are arbitrary rational constants. It is also shown that there is a language which can be recognized by a family of -uniform circuits of depth (1+(1))()log () and size (16()+()(log ()))(()) but not by any family of -uniform circuits of depth () and size (), where () is an arbitrary slowly growing function not bounded by (1).

We propose several new generalized synchronization algorithms for 2-D cellular arrays. Firstly, a generalized linear-time synchronization algorithm and its 14-state implementation are given. It is shown that there exists a 14-state 2-D CA that can synchronize any × rectangular array in + + max( + , + – – + 2) – 4 steps with the general at an arbitrary initial position (, ),where 1 ≤ ≤ , 1 ≤ ≤ . The generalized linear-time synchronization algorithm is interesting in that it includes an optimum-step synchronization algorithm as a special case where the general is located at one corner. In addition, we propose a noveloptimum-time generalized synchronization scheme that can synchronize any × array in  +  + max (, ) −  min (,  −  + 1) −  min (,  −  + 1) − 1 optimum steps.

We study the register complexity of -, -, and -programs, that is the number of registers (or variables) needed to compute certain unary (partial) functions from the non-negative integers to the non-negative integers. It turns out that the hierarchy of -computable (-, and -computable, respectively) functions :ℕ →ℕ (partial functions , respectively) that is induced by the number of registers collapses to a fixed level. In all three cases the first levels are separated. Our results show that there exist universal - and -programs with a constant number of registers.

A reversible logic element is a model of a computing element that has an analogous property to physical reversibility. In this paper, we investigate -symbol reversible elements with one-bit memory (i.e., two states) for =2, 3, and 4. We classified all of them, and showed the total numbers of essentially different elements are 8 (=2), 24 (=3), and 82 (=4). So far, a rotary element, a 2-state 4-symbol reversible element, has been known to be logically universal. Here, we proved that a new and interesting elements called 3- and 4-symbol left-/right-rotate elements are both universal. We also gave a new concise construction method of a Fredkin gate out of rotary elements.