Catálogo de publicaciones - libros

The classical towers of Hanoi have been generalized in several ways. In particular the second named author has studied the 3-peg Hanoi towers with all possible restrictions on the permitted moves between pegs. We prove that all these Hanoi puzzles give rise to infinite morphic sequences of moves, whose appropriate truncations describe the transfer of any given number of disks. Furthermore two of these infinite sequences are actually automatic sequences.

A word w over a finite alphabet Σ is n - collapsing if for an arbitrary DFA ${\mathcal A}=\langle Q,\Sigma,\delta\rangle$ , the inequality | δ ( Q , w )| ≤ | Q | −  n holds provided that | δ ( Q , u )| ≤ | Q | −  n for some word u ∈Σ^ +  (depending on ${\mathcal A}$ ). We overview some recent results related to this notion. One of these results implies that the property of being n -collapsing is algorithmically recognizable for any given positive integer n .

Locally consistent parsing (LCP) is a context sensitive partitioning method which achieves partition consistency in (almost) linear time. When iteratively applied, LCP followed by consistent block labeling provides a powerful tool for processing strings for a multitude of problems. In this paper we summarize applications of LCP in approximating well known distance measures between pairs of strings in (almost) linear time.

A word w is central if it has two periods p and q which are coprime and such that | w |= p + q –2. Central words play an essential role in the combinatorics of Sturmian words. The aim of this paper is to give an overview on central words focusing some recent developments in the study of their structure, combinatorics, and arithmetics. Moreover, some results are concerned with remarkable languages of central words such as central codes and Farey’s codes. Another interesting class of central languages is given by the so-called Farey languages which give faithful representations of Farey’s series.

Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. This paper is a short survey of research on reversible cellular automata over the past fourty plus years. We discuss the classic results by Hedlund, Moore and Myhill that relate injectivity, surjectivity and reversibility with each other. Then we review algorithmic questions and some results on computational universality. Finally we talk about local reversibility vs. global reversibility.

My ostensible purpose in this talk is to describe some new results (found in collaboration with Amitabha Roy) on expressibility of regular languages in certain generalizations of first-order logic. [10]. This provides me with a good excuse for describing some the work on the algebraic theory of regular languages in what one might call “nonregular settings”. The syntactic monoid and syntactic morphism of a regular language provide a highly effective tool for proving that a given regular language is not expressible or recognizable in certain compuational models, as long as the model is guaranteed to produce only regular languages. This includes finite automata, of course. but also formulas of propositional temporal logic, and first-order logic, provided one is careful to restrict the expressive power of such logics. (For example, by only allowing the order relation in first-order formulas.) Things become much harder, and quite a bit more interesting, when we drop this kind of restriction on the model. The questions that arise are important (particularly in computational complexity), and most of them are unsolved. They all point to a rich theory that extends the reach of algebraic methods beyond the domain of finite automata

We present two different types of complexity lower bounds for quantum uniform automata (finite automata) and nonuniform automata (OBDDs). We call them “metric” and “entropic” lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering “almost all Boolean functions” on n variables our entropic lower bounds gives exponential (2^ c ( δ )( n  − −  log n )) lower bound for the width of quantum OBDDs depending on the error δ allowed. Next we consider “generalized measure-many” quantum automata. It is appeared that for uniform and nonuniform automata (for space restricted models) their measure-once and measure-many models have different computational power.

Let Σ be a finite alphabet. A set $\mathcal{R}$ of regular languages over Σ is called rational if there exists a finite set $\mathcal E$ of regular languages over Σ, such that $\mathcal{R}$ is a rational subset of the finitely generated semigroup $(\mathcal{S},\cdot)=\langle\mathcal E\rangle$ with $\mathcal E$ as the set of generators and language concatenation as a product. We prove that for any rational set $\mathcal{R}$ and any regular language R  ⊆ Σ^* it is decidable (1) whether $R\in\mathcal{R}$ or not, and (2) whether $\mathcal{R}$ is finite or not.

We consider tissue P systems with antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, any recursively enumerable set of natural numbers can be generated with at most seven cells. On the other hand, with only one cell we can only generate regular sets when using one channel with the environment, whereas one cell with two channels between the cell and the environment obtains computational completeness with at most five symbols. Between these extreme cases of one symbol and one cell, respectively, there seems to be a trade-off between the number of cells and the number of symbols, e.g., for the case of tissue P systems with two channels between a cell and the environment we show that computational completeness can be obtained with two cells and three symbols as well as with three cells and two symbols, respectively.

A deterministic incomplete automaton ${\mathcal A}=\langle Q,\Sigma,\delta\rangle$ is partially monotonic if its state set Q admits a linear order such that each partial transformation $\delta(\rule{6pt}{.4pt}\,,a)$ with a ∈Σ preserves the restriction of the order to the domain of the transformation. We show that if ${\mathcal A}$ possesses a ‘killer’ word w ∈Σ^* whose action is nowhere defined, then ${\mathcal A}$ is ‘killed’ by a word of length $|Q|+\left\lfloor\dfrac{|Q|-1}2\right\rfloor$ .