On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

On the Descriptional Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.

A simple retroelement based knock-down system in Dictyostelium

Characteristics of DIRS-1 Mediated Knock-Downs __ We have previously shown that the most abundant Dictyostelium discoideum retroelement DIRS-1 is suppressed by RNAi mechanisms. Here we provide evidence that both inverted terminal repeats have strong promoter activity and that bidirectional expression apparently generates a substrate for Dicer. A cassette containing the inverted terminal repeats and a fragment of a gene of interest was sufficient to activate the RNAi response, resulting in the generation of ~21 nt siRNAs, a reduction of mRNA and protein expression of the respective endogene. Surprisingly, no transitivity was observed on the endogene. This was in contrast to previous observations, where endogenous siRNAs caused spreading on an artificial transgene. Knock-down was successful on seven target genes that we examined. In three cases a phenotypic analysis proved the efficiency of the approach. One of the target genes was apparently essential because no knock-out could be obtained; the RNAi mediated knock-down, however, resulted in a very slow growing culture indicating a still viable reduction of gene expression.