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.

Uniformisierbarkeit in Familien von abelschen t-Moduln höheren Ranges

Diese Arbeit beschäftigt sich mit der Frage, wie sich in einer Familie von abelschen t-Moduln die Teilfamilie der uniformisierbaren t-Moduln beschreiben lässt. Abelsche t-Moduln sind höherdimensionale Verallgemeinerungen von Drinfeld-Moduln über algebraischen Funktionenkörpern. Bekanntermaßen lassen sich Drinfeld-Moduln in allgemeiner Charakteristik durch analytische Tori parametrisieren. Diese Tatsache überträgt sich allerdings nur auf manche t-Moduln, die man als uniformisierbar bezeichnet. Die Situation hat eine gewisse Analogie zur Theorie von elliptischen Kurven, Tori und abelschen Varietäten über den komplexen Zahlen. Um zu entscheiden, ob ein t-Modul in diesem Sinne uniformisierbar ist, wendet man ein Kriterium von Anderson an, das die rigide analytische Trivialität der zugehörigen t-Motive zum Inhalt hat. Wir wenden dieses Kriterium auf eine Familie von zweidimensionalen t-Moduln vom Rang vier an, die von Koeffizienten a,b,c,d abhängen, und gelangen dabei zur äquivalenten Fragestellung nach der Konvergenz von gewissen rekursiv definierten Folgen. Das Konvergenzverhalten dieser Folgen lässt sich mit Hilfe von Newtonpolygonen gut untersuchen. Schließlich erhält man durch dieses Vorgehen einfach formulierte Bedingungen an die Koeffizienten a,b,c,d, die einerseits die Uniformisierbarkeit garantieren oder andererseits diese ausschließen.