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 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.

Diazafluoren-9-yliden als Bindungsmotiv für Metallfragmente in kreuzkonjugierten π-Systemen

In der vorliegenden Dissertation wurden kreuzkonjugierte organische Verbindungen basierend auf Diazafluorenmethyliden- sowie Dipyridylmethyliden-Bausteinen synthetisiert, die zum einen photoredoxaktive Metallfragmente komplexieren können und zum anderen erweiterte π-konjugierte Pfade auf der Grundlage von Alkineinheiten ermöglichen. Das kreuzkonjugierte Motiv wurde über die Kupplung von Alkineinheiten an halogenierte Methyliden-Einheiten, den so genannten Dibromolefinen, zugänglich gemacht. Zur Synthese von Dibromolefinen wurden verschiedene Methoden untersucht. Literaturbekannte Methoden wie die Wittig-Reaktion und ihre Modifikationen sowie die Corey-Fuchs-Reaktion konnten für die Diazafluoreneinheit nicht erfolgreich angewendet werden. Bei einer mikrowellenunterstützten Reaktion konnte sowohl ausgehend von Diazafluoren-9-on als auch von Di-2-pyridylketon eine Dibromolefinierung (55 % und 65 %) erreicht werden. Die Eignung der Mikrowellenstrahlung für Dibromolefinierungsreaktionen nach Corey und Fuchs wurde weiterhin an verschiedenen Aldehyden und Ketonen untersucht. In den meisten Fällen konnten gute bis sehr gute Ergebnisse erzielt werden. Durch die erfolgreiche Synthese von Dibromolefinen über Mikrowellensynthese wurde die Realisierung von diversen π-konjugierten Systemen möglich. Dies erfolgte exemplarisch durch die Kupplung der Alkine 5-Ethinyl-2,2’-bipyridin, 1-(Ferrocenylethinyl)-4-(ethinyl)benzol, Tri(tolyl)propin sowie der TIPS- und TMS-Acetylene. Neben der Vielfalt an Möglichkeiten zur Funktionalisierung von Dipyridyl- und Diazafluorenbausteinen zeigte sich zudem, dass sogar räumlich anspruchsvolle Verbindungen wie die geminale angeordneten voluminösen Tri(tolyl)propinyl-Substituenten an der Doppelbindung erfolgreich synthetisiert werden können. Die Koordinationseigenschaften der neu synthetisierten Verbindungen konnten durch Umsetzungen der Diazafluoren- und Dipyridylverbindungen mit PdCl2 und [RuCl2(bpy)2] erfolgreich gezeigt werden. Im Hinblick auf die Herstellung von Funktionsmaterialien eignen sich die Endiin-Strukturmotive aufgrund von diversen Variationsmöglichkeiten wie Koordination von Übergangsmetallen sowie Funktionalisierung der Peripherie gut. Dadurch können die elektronischen Eigenschaften wie die Absorption oder elektrochemische Potentiale der Verbindungen modifiziert werden. Die UV/Vis-Spektren der neu synthetisierten Verbindungen zeigen, dass Absorptionen in längerwelligen Bereichen durch Verlängerung des Konjugationspfades gesteuert werden können. Zudem lassen sich weitere photophysikalische Eigenschaften wie MC-, LC-, LMCT- oder MLCT-Übergänge durch Koordination von Metallen generieren. Die elektrochemischen Potentiale der Dipyridyl- und Diazafluorenbausteine konnten durch Anbindung von verschiedenen Substituenten beeinflusst werden. Es zeigte sich, dass sich die Reduktionswellen im Vergleich zu denen der Ketone zu niedrigeren Potentialen verschieben, wenn Alkine an die Dipyridylmethyliden- und Diazafluorenmethyliden-Bausteine geknüpft wurden. Zudem konnte beobachtet werden, dass die Signale nicht immer reversibel sind. Insbesondere die Dipyridylverbindungen zeichneten sich durch irreversible Reduktionswellen aus. Die Realisierung von π-konjugierten Systemen gelang auch mit cyclischen kohlenstoffbasierten Verbindungen. Über das separat synthetisierte 2,2’-Diethinyltolan konnte eine cyclische Verbindung, ein dehydroannulen-radialenisches System, erfolgreich hergestellt werden. Die Koordination von redoxaktiven Metallzentren wie [Ru(bpy)2] konnte für diese Verbindung ebenfalls erfolgreich gezeigt werden. Die elektronische Wechselwirkung zwischen dem Metallzentrum und dem dehydroannulenischen System könnte sowohl über theoretische Methoden (zeitabhängige Dichtefunktionaltheorie) als auch experimentell wie z. B. über transiente Absorptionsspektroskopie untersucht werden. Diese zukünftig durchzuführenden Untersuchungen können Aufschluss über die Ladungstransferraten und -dauer geben. Im Hinblick auf die Realisierung von Modellverbindungen für molekulare Drähte wurden lineare Systeme basierend auf der Diazafluoreneinheit synthetisiert. Zur Synthese von derartigen Systemen war es zunächst notwendig, die Dibromolefine unsymmetrisch zu alkinylieren. Die unsymmetrische Substitution gestaltete sich als Herausforderung, da eine Einfachkupplung mit einem Acetylen nicht möglich war. In den meisten Fällen wurden zweifach substituierte Spezies mit den identischen Alkinen erhalten. Die besten Ausbeuten konnten durch die konsekutive Zugabe von TIPS-Acetylen und darauffolgend TMS-Acetylen in die Reaktionsmischung erhalten werden. Offenbar spielt der räumliche Anspruch des Erstsubstituenten in diesem Zusammenhang eine Rolle. Die selektive Entschützung der unterschiedlich silylierten Verbindungen erfolgte mit K2CO3 in MeOH/THF (1:1). Die oxidative Homokupplungsreaktion erfolgte ohne Isolierung der entschützten Spezies, da diese instabil ist und zur Polymerisation neigt. Aufgrund der Instabilität der entschützten Spezies sowie möglichen Nebenreaktionen waren die Ausbeuten sowohl bei der TIPS-geschützten Verbindung als auch bei der TTP-geschützten Verbindung gering. Versuche, lineare Systeme von dipyridylbasierten Verbindungen zu erhalten, schlugen fehl. Die π-konjugierten Systeme lassen aufgrund der effektiven Überlappung der beteiligten π-Orbitale hohe Ladungsträgermobilitäten vermuten. Die im Rahmen dieser Arbeit synthetisierten Verbindungen könnten mit Schwefelverbindungen die Anbindung an Elektroden zulassen, worüber die Leitfähigkeiten der Verbindungen gemessen werden könnten.