Catálogo de publicaciones - libros

Substitutions are powerful tools to study combinatorial properties of sequences. There exist strong characterizations through substitutions of the Sturmian sequences that are S -adic, substitutive or a fixed-point of a substitution. In this paper, we define a bidimensional version of Sturmian sequences and look for analogous characterizations. We prove in particular that a bidimensional Sturmian sequence is always S -adic and give sufficient conditions under which it is either substitutive or a fixed-point of a substitution.

Motivated by the research on pattern languages, we study a fundamental combinatorial question on morphisms in free semigroups: With regard to any string α over some alphabet we ask for the existence of a morphism σ such that σ ( α ) is unambiguous, i.e. there is no morphism ρ with $\rho \not= \sigma$ and ρ ( α ) = σ ( α ). Our main result shows that a rich and natural class of strings is provided with unambiguous morphic images.

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, by adapting Sipser’s method, for a given automaton (2dfa) with n states we build an automaton accepting the complement with at most 4 n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4 n –state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n –state two-way automaton (2nfa), can be accepted by an O ( n ^8)–state 2nfa. Here we also make the 2nfa halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O ( n ^8) states.

We develop a structural and language theoretical characterization of timed languages over discrete time in terms of a variant of Büchi automata and languages. The so-called tick automaton is a standard Büchi automaton with a special “clock-tick”-input symbol modeling the discrete flow of time. Based on these characterizations we give an alternative proof for the fact that the class of regular timed languages is closed under complementation and formulate a time-warp lemma which, similar to a pumping lemma, can be used to show that a timed language is not regular. The characterizations hold alike for timed automata with and without periodic clock constraints.

It is known that for monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right- or left-monotone. Actually in these cases it suffices to admit delete operations instead of the more general rewrite operations. In addition, we characterize the classes of languages that are accepted by these types of two-way restarting automata by certain combinations of deterministic pushdown automata and deterministic transducers.

The paper examines the concept of hairpin-free words motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free if it cannot be written in the form xvyθ ( v ) z , with certain additional conditions, for an involution θ (a function θ with the property that θ ^2 equals the identity function). We consider three involutions relevant to DNA computing: a) the mirror image function, b) the DNA complementarity function over the DNA alphabet { A , C , G , T } which associates A with T and C with G , and c) the Watson-Crick involution which is the composition of the previous two. We study elementary properties and finiteness of hairpin (-free) languages w.r.t. the involutions a) and c). Maximal length of hairpin-free words is also examined. Finally, descriptional complexity of maximal hairpin-free languages is determined.

We analyze models of infinite-state automata extended by monotonic counting mechanisms, starting from the (finite-state) Parikh automata studied by Klaedtke and Rueß. We show that, for linear-bounded automata, this extension does not increase the language recognition power. In the framework of infinite transition systems developed by Caucal and others, we show that adding monotonic counters to synchronized rational graphs still results in synchronized rational graphs, in contrast to the case of pushdown graphs or prefix-recognizable graphs. For prefix-recognizable graphs, however, we show that the extension by monotonic counters retains the decidability of the reachability problem.

For each language L , let $\hat{\mathcal F}_\cap(L)$ be the smallest intersection-closed full AFL generated by the language L . Furthermore, for each natural number k ≥ 2 let $P_k=\{a^{n^k}|n\in\mathbb N\}$ . By applying certain classical and recent results on Diophantine equations we show that $\mathcal L_{RE}=\hat{\mathcal F}_\cap(P_k)$ , i.e., the family of all recursively enumerable languages coincides with the smallest intersection-closed full AFL generated by the polynomial language P _ k for all k ≥ 2. This allows us to answer to an open problem of S. Ginsburg and J. Goldstine in [2].

It is known that for a regular language L and an arbitrary language K the largest solution of the inequality XK  ⊆  LX is regular. Here we show that there exist finite languages K and P and star-free languages L , M and R such that the largest solutions of the systems $\{XK\subseteq LX,\ X\subseteq M\}$ and $\{XK\subseteq LX,\ XP\subseteq RX\}$ are not recursively enumerable.

The power of tree series transducers of type I and II is studied for IO as well as OI tree series substitution. More precisely, it is shown that the IO tree series transformations of type I (respectively, type II) are characterized by the composition of homomorphism top-down IO tree series transformations with bottom-up (respectively, linear bottom-up) IO tree series transformations. On the other hand, polynomial OI tree series transducers of type I and II and top-down OI tree series transducers are equally powerful.