Degrees of Free Word-Order and Freely Rewriting Restarting Automata

In natural languages with a high degree of word-order freedom syntactic phenomena like dependencies (subordinations) or valencies do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: 1. the degree of j-monotonicity, and 2. the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

Learning analysis by reduction from positive data

Analysis by reduction is a linguistically motivated method for checking correctness of a sentence. It can be modelled by restarting automata. In this paper we propose a method for learning restarting automata which are strictly locally testable (SLT-R-automata). The method is based on the concept of identification in the limit from positive examples only. Also we characterize the class of languages accepted by SLT-R-automata with respect to the Chomsky hierarchy.

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 function of the Dictyostelium Argonaute A protein (AgnA) in epigenetic gene regulation

With molecular biology methods and bioinformatics, the Argonaute proteins in Dictyostelium discoideum were characterized, and the function of the AgnA protein in RNAi and DNA methylation was investigated, as well as cellular features. Also interaction partners of the PAZ-Piwi domain of AgnA (PAZ-PiwiAgnA) were discovered. The Dictyostelium genome encodes five Argonaute proteins, termed AgnA/B/C/D/E. The expression level of Argonaute proteins was AgnB/D/E > AgnA > AgnC. All these proteins contain the characteristic conserved of PAZ and Piwi domains. Fluorescence microscopy revealed that the overexpressed C-terminal GFP-fusion of PAZ-PiwiAgnA (PPWa-GFP) localized to the cytoplasm. Overexpression of PPWa-GFP leaded to an increased gene silencing efficiency mediated by RNAi but not by antisense RNA. This indicated that PAZ-PiwiAgnA is involved in the RNAi pathway, but not in the antisense pathway. An analysis of protein-protein interactions by a yeast-two-hybrid screen on a cDNA library from vegetatively grown Dictyostelium revealed that several proteins, such as EF2, EF1-I, IfdA, SahA, SamS, RANBP1, UAE1, CapA, and GpdA could interact with PAZ-PiwiAgnA. There was no interaction between PAZ-PiwiAgnA and HP1, HelF and DnmA detected by direct yeast-two-hybrid analysis. The fluorescence microscopy images showed that the overexpressed GFP-SahA or IfdA fusion proteins localized to both cytoplasm and nuclei, while the overexpressed GFP-SamS localized to the cytoplasm. The expression of SamS in AgnA knock down mutants was strongly down regulated on cDNA and mRNA level in, while the expression of SahA was only slightly down regulated. AgnA knock down mutants displayed defects in growth and phagocytosis, which suggested that AgnA affects also cell biological features. The inhibition of DNA methylation on DIRS-1 and Skipper retroelements, as well as the endogenous mvpB and telA gene, observed for the same strains, revealed that AgnA is involved in the DNA methylation pathway. Northern blot analysis showed that Skipper and DIRS-1 were rarely expressed in Ax2, but the expression of Skipper was upregulated in AgnA knock down mutants, while the expression of DIRS-1 was not changed. A knock out of the agnA gene failed even though the homologous recombination of the disruption construct occurred at the correct site, which indicated that there was a duplication of the agnA gene in the genome. The same phenomenon was also observed in ifdA knock out experiments.

Computeralgebraische Herleitung und Auswertung atomarer Störungsreihen und deren Anwendung auf geschlossenschalige und einfache offenschalige Systeme

In der vorliegenden Arbeit wurde gezeigt, wie mit Hilfe der atomaren Vielteilchenstörungstheorie totale Energien und auch Anregungsenergien von Atomen und Ionen berechnet werden können. Dabei war es zunächst erforderlich, die Störungsreihen mit Hilfe computeralgebraischer Methoden herzuleiten. Mit Hilfe des hierbei entwickelten Maple-Programmpaketes APEX wurde dies für geschlossenschalige Systeme und Systeme mit einem aktiven Elektron bzw. Loch bis zur vierten Ordnung durchgeführt, wobei die entsprechenden Terme aufgrund ihrer großen Anzahl hier nicht wiedergegeben werden konnten. Als nächster Schritt erfolgte die analytische Winkelreduktion unter Anwendung des Maple-Programmpaketes RACAH, was zu diesem Zwecke entsprechend angepasst und weiterentwickelt wurde. Erst hier wurde von der Kugelsymmetrie des atomaren Referenzzustandes Gebrauch gemacht. Eine erhebliche Vereinfachung der Störungsterme war die Folge. Der zweite Teil dieser Arbeit befasst sich mit der numerischen Auswertung der bisher rein analytisch behandelten Störungsreihen. Dazu wurde, aufbauend auf dem Fortran-Programmpaket Ratip, ein Dirac-Fock-Programm für geschlossenschalige Systeme entwickelt, welches auf der in Kapitel 3 dargestellen Matrix-Dirac-Fock-Methode beruht. Innerhalb dieser Umgebung war es nun möglich, die Störungsterme numerisch auszuwerten. Dabei zeigte sich schnell, dass dies nur dann in einem angemessenen Zeitrahmen stattfinden kann, wenn die entsprechenden Radialintegrale im Hauptspeicher des Computers gehalten werden. Wegen der sehr hohen Anzahl dieser Integrale stellte dies auch hohe Ansprüche an die verwendete Hardware. Das war auch insbesondere der Grund dafür, dass die Korrekturen dritter Ordnung nur teilweise und die vierter Ordnung gar nicht berechnet werden konnten. Schließlich wurden die Korrelationsenergien He-artiger Systeme sowie von Neon, Argon und Quecksilber berechnet und mit Literaturwerten verglichen. Außerdem wurden noch Li-artige Systeme, Natrium, Kalium und Thallium untersucht, wobei hier die niedrigsten Zustände des Valenzelektrons betrachtet wurden. Die Ionisierungsenergien der superschweren Elemente 113 und 119 bilden den Abschluss dieser Arbeit.

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.

Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

Bismarck und der Arbeiterschutz

The eighteen-eighties under Chancellor Otto von Bismarck saw the establishment of statutory workers' insurance in Germany. Germany remained backwards, however, in the statutory protection of workers at their workplace, the prevention of dangers arising from industrial work, and the limitation of hours of work for children, young persons, women or even workers in general. The protection of young workers, for example, remained until 1891 as it had been in 1853. That was due to the fundamental refusal of all improvments in matters of regulations for the protection of workers on the part of Bismarck, who blocked all relevant initiatives. Along with other sources this article draws on previously rarely used marginalia of Bismarck's in ministerial documents on factory inspection, children's and women's labour, the prohibition of Sunday work, and the introduction of a standard working day. The investigation deals with the Chancellor's motives and the arguments deployed in his prevention of measures of workers' protection, which he called an infringement of workers' freedom of action.

Alltag, Organisationskultur und beruflicher Habitus

Aus der Einleitung: "Weder in den klassischen, allgemein erziehungswissenschaftlichen Hand- und Wörterbüchern der letzten drei Dekaden (vgl. u.a. Speck/Wehle 1970; Lenzen 1989; Krüger/Grunert 2004) noch in den entsprechenden Überblickspublikationen der Sozialpädagogik (vgl. u.a. Deutscher Verein für öffentliche und private Fürsorge 2002; Lauermann/Knapp 2003; Otto/Thiersch 2005; Kreft/Mielenz 2005) werden Frage- und Problemstellungen der Relation von Distanz und Nähe – zumindest nicht unter dieser Titulatur – diskutiert. Demgegenüber wird in den pflegeorientierten und gesundheitspräventiven wie auch patientenbezogenen Diskussionen der Medizin, in der Theologie und Ethnologie, in der Medien- und Migrationwissenschaft, der Germanistik und der vergleichenden Geschichtswissenschaft sowie in den psychotherapeutischen Diskursen der Nähe-Distanz-Problematik größere Aufmerksamkeit zuteil als in den pädagogischen und erziehungswissenschaftlichen Reflexionen und Diskursen. Wenn sie dennoch Objekt von erziehungswissenschaftlich gefärbten Beobachtungen wird, dann nur mittelbar und allenfalls in Randnotizen, wenn es – thematisch eingegrenzt – um das Ausbalancieren von Distanz und Nähe in den Beziehungen von PädagogInnen und AdressatInnen und der in diesem pädagogischen Verhältnis eingelagerten Intimität geht (vgl. u. a. Bittner/Rehm 1966). Die 'Erotik' im pädagogischen Alltag, die Ängste und die Verdrängungen dieser Dimension durch Aufbau von Distanz oder schließlich die Angst, durch eine zu große Nähe zu den AdressatInnen 'Kontrolle' über den Beruf zu 'verlieren', bleiben weitgehend ebenso unbeleuchtet wie eine nähere Betrachtung der Auswirkungen von zu viel Nähe zu Beruf und AdressatInnen auf die privaten, intimen wie freundschaftlichen Beziehungen (aus ethnopsychoanalytischer Perspektive hierzu u. a. Parin 1978). Zudem wird das Verhältnis von Nähe und Distanz – wenn überhaupt – jeweils spezifisch und auf eine je eigene Art als ein individuelles, nicht jedoch als ein in die Organisation des Pädagogischen immanent eingelagertes Problem beleuchtet, das sich zusätzlich aus den in den jeweiligen pädagogischen Arbeitsfeldern eingelagerten Handlungslogiken speist. Selbstverständlich kann das ambivalente Verhältnis von Nähe und Distanz nicht aus dem personalen Kontext entlassen werden. Wie immer es auch gewendet und thematisiert wird, es bleibt eine in Interaktionen eingewobene Polarität. Doch, und darauf zielen die Suchbewegungen in diesem Beitrag ab, wird es im pädagogischen Alltag von der jeweiligen Kultur der Organisation des Pädagogischen respektive der Sozialen Arbeit gerahmt – quasi kontextualisiert – und geprägt von den jeweils different modellierten beruflichen Habitus der professionellen AkteurInnen. Organisationskulturelle und habituelle Rahmungen des interaktiven Geschehens wiederum sind nicht ohne die Betrachtung der jeweils vorzufindenden feldspezifischen Regeln (vgl. Bourdieu/Wacquant 1996; zur Berücksichtigung einer Theorie des pädagogischen Feldes für Professionalisierung und Qualität vgl. Honig 2004). Diesen Rahmungen von Distanz und Nähe wird nachfolgend nachgespürt, indem erstens einige Beobachtungen aus dem sozialpädagogischen Alltag vorgestellt (1) und sie zweitens hinsichtlich der Ausbuchstabierung von Distanz und Nähe betrachtet werden (2). Drittens werden die bisherigen Überlegungen mit einem weiteren Fallportrait angereichert (3), um schließlich zu rekonstruieren, in welche Modalitäten Nähe und Distanz habituell, organisationskulturell und feldspezifisch eingebunden sind (4)."

"Bildungsbremse" Herkunft

Aus der Einleitung: "Die bildungsorientierte Betreuung von Kindern im vorschulischen Alter und die Frage, wie sich Familie und Beruf – insbesondere weibliche Berufskarrieren und Mutterschaft – miteinander vereinbaren lassen, genießen zur Zeit eine erhöhte öffentliche Aufmerksamkeit. In den öffentlichen Debatten wird 'Bildung fast über Nacht mit Vorschule und früher Kindheit zusammen gedacht' (Stamm 2004, S. 865). Der Beitrag schließt an die diesbezüglichen Diskussionen an und fragt danach, von welchen gesellschaftlich zu realisierenden Bedarf an außerfamilialen, bildungsorientierten Betreuungsangeboten für unter dreijährige Kinder zukünftig auszugehen ist. Die Gemengelage der gegenwärtig intensiv diskutierten sozial- und bildungspolitischen Themen stellt sich allerdings äußerst komplex und diffus dar. Die öffentliche Diskussion der zur Lösung anstehenden Fragen zeigt erstens partiell eine recht wahllose Inanspruchnahme empirischer Befunde (1) und scheint zweitens eine Diversifizierung der fachwissenschaftlichen Aufmerksamkeiten zu provozieren (2)."

DNA methylation in Dictyostelium discoideum

DNA methyltransferases of type Dnmt2 are a highly conserved protein family with enigmatic function. The aim of this work was to characterize DnmA, the Dnmt2 methyltransferase in Dictyostelium discoideum, and further to investigate its implication in DNA methylation and transcriptional gene silencing. The genome of the social amoeba Dictyostelium encodes DnmA as the sole DNA methyltransferase. The enzyme bears all ten characteristic DNA methyltransferase motifs in its catalytic domain. The DnmA mRNA was found by RT-PCR to be expressed during vegetative growth and down regulated during development. Investigations using fluorescence microscopy showed that both DnmA-myc and DnmA-GFP fusions predominantly localised to the nucleus. The function of DnmA remained initially unclear, but later experiment revealed that the enzyme is an active DNA methyltransferase responsible for all DNA (cytosine) methylation in Dictyostelium. Neither in gel retardation assays, nor by the yeast two hybrid system, clues on the functionality of DnmA could be obtained. However, immunological detection of the methylation mark with an α - 5mC antibody gave initial evidence that the DNA of Dictyostelium was methylated. Furthermore, addition of 5-aza-cytidine as demethylating agent to the Dictyostelium medium and subsequent in vitro incubation of the DNA isolated from these cells with recombinant DnmA showed that the enzyme binds slightly better to this target DNA. In order to investigate further the function of the protein, a gene knock-out for dnmA was generated. The gene was successfully disrupted by homologous recombination, the knock-out strain, however, did not show any obvious phenotype under normal laboratory conditions. To identify specific target sequences for DNA methylation, a microarray analysis was carried out. Setting a threshold of at least 1.5 fold for differences in the strength of gene expression, several such genes in the knock-out strain were chosen for further investigation. Among the up-regulated genes were the ESTs representing the gag and the RT genes respectively of the retrotransposon skipper. In addition Northern blot analysis confirmed the up-regulation of skipper in the DnmA knock-out strain. Bisufite treatment and sequencing of specific DNA stretches from skipper revealed that DnmA is responsible for methylation of mostly asymmetric cytosines. Together with skipper, DIRS-1 retrotransposon was found later also to be methylated but was not present on the microarray. Furthermore, skipper transcription was also up-regulated in strains that had genes disrupted encoding components of the RNA interference pathway. In contrast, DIRS 1 expression was not affected by a loss of DnmA but was strongly increased in the strain that had the RNA directed RNA polymerase gene rrpC disrupted. Strains generated by propagating the usual wild type Ax2 and the DnmA knock-out cells over 16 rounds in development were analyzed for transposon activity. Northern blot analysis revealed activation for skipper expression, but not for DIRS-1. A large number of siRNAs were found to be correspondent to the DIRS-1 sequence, suggesting concerted regulation of DIRS-1 expression by RNAi and DNA methylation. In contrast, no siRNAs corresponding to the standard skipper element were found. The data show that DNA methylation plays a crucial role in epigenetic gene regulation in Dictyostelium and that different, partially overlapping mechanisms control transposon silencing for skipper and DIRS-1. To elucidate the mechanism of targeting the protein to particular genes in the Dictyostelium genome, some more genes which were up-regulated in the DnmA knock-out strain were analyzed by bisulfite sequencing. The chosen genes are involved in the multidrug response in other species, but their function in Dictyostelium is uncertain. Bisulfite data showed that two of these genes were methylated at asymmetrical C-residues in the wild type, but not in DnmA knock-out cells. This suggested that DNA methylation in Dictyostelium is involved not only in transposon regulation but also in transcriptional silencing of specific genes.