Description logics (DLs) are used to represent knowledge of an application domain and provide standard reasoning services to infer consequences of this knowledge. However, classical DLs are not suited to represent vagueness in the description of the knowledge. We consider a combination of DLs and Fuzzy Logics to address this task. In particular, we consider the t-norm-based semantics for fuzzy DLs introduced by Hájek in 2005. Since then, many tableau algorithms have been developed for reasoning in fuzzy DLs. Another popular approach is to reduce fuzzy ontologies to classical ones and use existing highly optimized classical reasoners to deal with them. However, a systematic study of the computational complexity of the different reasoning problems is so far missing from the literature on fuzzy DLs. Recently, some of the developed tableau algorithms have been shown to be incorrect in the presence of general concept inclusion axioms (GCIs). In some fuzzy DLs, reasoning with GCIs has even turned out to be undecidable. This work provides a rigorous analysis of the boundary between decidable and undecidable reasoning problems in t-norm-based fuzzy DLs, in particular for GCIs. Existing undecidability proofs are extended to cover large classes of fuzzy DLs, and decidability is shown for most of the remaining logics considered here. Additionally, the computational complexity of reasoning in fuzzy DLs with semantics based on finite lattices is analyzed. For most decidability results, tight complexity bounds can be derived.

Ontology-based data access (OBDA) augments classical query answering in databases by including domain knowledge provided by an ontology. An ontology captures the terminology of an application domain and describes domain knowledge in a machine-processable way. Formal ontology languages additionally provide semantics to these specifications. Systems for OBDA thus may apply logical reasoning to answer queries; they use the ontological knowledge to infer new information, which is only implicitly given in the data. Moreover, they usually employ the open-world assumption, which means that knowledge not stated explicitly in the data or inferred is neither assumed to be true nor false. Classical OBDA regards the knowledge however only w.r.t. a single moment, which means that information about time is not used for reasoning and hence lost; in particular, the queries generally cannot express temporal aspects. We investigate temporal query languages that allow to access temporal data through classical ontologies. In particular, we study the computational complexity of temporal query answering regarding ontologies written in lightweight description logics, which are known to allow for efficient reasoning in the atemporal setting and are successfully applied in practice. Furthermore, we present a so-called rewritability result for ontology-based temporal query answering, which suggests ways for implementation. Our results may thus guide the choice of a query language for temporal OBDA in data-intensive applications that require fast processing, such as context recognition.

In this workshop we present an innovative teaching, learning and research setting that engages beginning teachers in mathematical inquiry as they investigate, represent and connect mathematical ideas through mathematical conversation, reasoning and argument. This workshop connects to the themes of teacher preparation and teaching through problem solving. Drawing on new paradigms to think about teaching and learning, we orient our work within complexity theory (Davis & Sumara, 2006; Holland, 1998; Johnson, 2001; Maturana & Varela, 1987; Varela, Thompson & Rosch, 1991) to understand teaching|learning as a complex iterative process through which opportunities for learning arise out of dynamic interactions. Varela, Thompson and Rosch, (1991) use the term co-emergence to understand how the individual and the environment inform each other and are “bound together in reciprocal specification and selection” (p.174). In particular we are interested in the conditions that enable the co-emergence of teaching|learning collectives that support the generation of new mathematical and pedagogical ideas and understandings. The setting is a one-week summer math program designed for prospective elementary teachers to deepen particular mathematical concepts taught in elementary school. The program is facilitated by recently graduated secondary mathematics teachers to provide them an opportunity to experience mathematics teaching|learning through rich problems. The data collected include questionnaires, interviews, and video recordings. Our analyses show that many a-ha moments of mathematical and pedagogical insight are experienced by both groups as they work together throughout the week. In this workshop we will actively engage the audience in an exploration of the mathematics problems that we pose in this unique teaching|learning environment. We will present our data on the participants’ mathematical and pedagogical responses and open a discussion of the implications of our work.

Die symbolische Aufbereitung mathematischer Modelle ist eine wesentliche Voraussetzung, um die Dynamik komplexer physikalischer Systeme mit Hilfe numerischer Simulationen zu untersuchen. Deren Modellierung mit gleichungsbasierten objektorientierten Sprachen bietet gegenüber der signalflussbasierenden Modellierung den Vorteil, dass die sich aus der Mathematik und Physik ergebenden Gleichungen in ihrer ursprünglichen Form zur Modellbeschreibung verwendet werden können. Die akausale Beschreibung mit Gleichungen erhöht die Wiederverwendbarkeit der Modelle und reduziert den Aufwand bei der Modellierung. Die automatisierte Überführung der Gleichungen in Zuweisungen lässt sich theoretisch auf Modelle beliebiger Größe und Komplexität anwenden. In der praktischen Anwendung ergeben sich jedoch, insbesondere bei der automatisierten Überführung großer Modelle, mathematische Systeme mit sehr vielen Gleichungen und zeitabhängigen Variablen. Die daraus resultierenden langen Ausführungszeiten schränken die Anwendbarkeit der symbolischen Aufbereitung erheblich ein. Die vorliegende Arbeit beschreibt den Prozess der automatisierten Überführung eines Modells bis zur numerischen Simulation. Alle Teilschritte werden detailliert untersucht und bezüglich ihrer theoretischen Komplexität bewertet. Geeignete Algorithmen werden im OpenModelica Compiler umgesetzt und bezüglich ihrer Laufzeit anhand praxisrelevanter Modelle miteinander verglichen und für jeden Teilschritt die beste Implementierung ausgewählt. Dadurch konnte ein nahezu linearer Zusammenhang zwischen Modellgröße und benötigter Zeit zur Überführung erreicht werden. Zusätzlich bietet die Arbeit eine umfassende Dokumentation mit zahlreichen Empfehlungen für die Implementierung eines BackEnds eines Modelica Compilers. Dies erleichtert den Einstieg für neue Entwickler sowie die Weiterentwicklung bestehender Algorithmen. Letzteres wird durch ein modulares Konzept einer BackEnd-Pipeline unterstützt. Außerdem werden Methoden diskutiert, wie ein neues Modul innerhalb dieser Pipeline effizient getestet werden kann.:1 Einleitung 1.1 Modellierung und Simulation 1.2 Gleichungsbasierte objektorientierte Modellierung und Simulation 1.3 Motivation 1.4 Ziele, Forschungsschwerpunkt und Arbeitsvorhaben 2 Modellierung und Simulation mit Modelica 2.1 Anwendersicht 2.2 Die Modelica Sprache 2.3 Das Modelica Modell 2.4 Transformation des Modells zum Simulator 2.5 Laufzeituntersuchungen eines Modelica Compiler BackEnds 3 Graphen 3.1 Graphen für Gleichungssysteme 3.2 Suchalgorithmen 3.3 Matching Algorithmen 3.4 Laufzeituntersuchungen an Matching Algorithmen mit Modelica 4 Kausalisierung 4.1 Kausalisieren von algebraischen Systemen und Systemen gewöhnlicher Differentialgleichungen erster Ordnung 4.1.1 Zuweisen 4.1.2 Sortieren 4.2 Kausalisieren von differential algebraischen Systemen 4.2.1 Pantelides Algorithmus 4.2.2 Auswahl der Zustände des Systems 4.2.3 Singuläre Systeme 5 Symbolische Optimierung 5.1 Definition und Anwendung symbolischer Optimierungen 5.2 Allgemeine symbolische Optimierung 5.2.1 Finden und Entfernen trivialer Gleichungen 5.2.2 Tearing und Relaxation 5.2.3 Inline Integration 5.2.4 Parallelisierung 5.3 Fachbereichsspezifische symbolische Optimierung 5.3.1 Relaxation O(n) für Mehrkörpersysteme 6 Umsetzung Modelica Compiler BackEnd 6.1 Konzepte für die Implementation 6.1.1 Datenstruktur 6.1.2 Teilschritte der Analyse und Optimierungsphase 6.1.3 BackEnd Pipeline 6.1.4 Kausalisierung 6.2 Testen der Implementation 7 Laufzeituntersuchung an skalierbaren Modellen 7.1 Software-Benchmark Umgebung für Modelica Compiler - ModeliMark 7.2 Modelle für Laufzeituntersuchungen 7.3 Ergebnisse 8 Zusammenfassung und Ausblick / The symbolic treatment of mathematical models is essential to study the dynamics of complex physical systems by means of numerical simulations. In contrast to signal flow based approaches, modeling with equation-based and object-oriented languages has the advantage that the original equations can be used directly. The acausal description of equations increases reusability and reduces the effort for the modeller. The automated transformation of equations into assignments can in theory be applied to models of any size and complexity. In practice, however, problems arise when large models, i.e. mathematical systems with many equations and time-dependent variables, shall be transformed. Long execution times that occur limit the applicability of symbolic processing considerably. The present work describes the process of automated transformation from a model to program code which can be simulated numerically. All steps are examined in detail and evaluated in terms of its theoretical complexity. Suitable algorithms are implemented in the OpenModelica Compiler. Their execution times are compared by looking at models which are relevant to engineering. The best implementations for each sub-step are selected and combined to a Modelica Compiler BackEnd. Thus a relationship between model size and the time needed for transformation has been achieved which is mostly linear. In addition, a comprehensive discussion with numerous recommendations for the implementation of a Modelica Compiler BackEnd is given. This is supposed to help new developers as well as to facilitate the development of existing algorithms. The latter is supported by a modular concept of a BackEnd pipeline. Moreover, methods are discussed how new modules can be tested efficiently using this pipeline.:1 Einleitung 1.1 Modellierung und Simulation 1.2 Gleichungsbasierte objektorientierte Modellierung und Simulation 1.3 Motivation 1.4 Ziele, Forschungsschwerpunkt und Arbeitsvorhaben 2 Modellierung und Simulation mit Modelica 2.1 Anwendersicht 2.2 Die Modelica Sprache 2.3 Das Modelica Modell 2.4 Transformation des Modells zum Simulator 2.5 Laufzeituntersuchungen eines Modelica Compiler BackEnds 3 Graphen 3.1 Graphen für Gleichungssysteme 3.2 Suchalgorithmen 3.3 Matching Algorithmen 3.4 Laufzeituntersuchungen an Matching Algorithmen mit Modelica 4 Kausalisierung 4.1 Kausalisieren von algebraischen Systemen und Systemen gewöhnlicher Differentialgleichungen erster Ordnung 4.1.1 Zuweisen 4.1.2 Sortieren 4.2 Kausalisieren von differential algebraischen Systemen 4.2.1 Pantelides Algorithmus 4.2.2 Auswahl der Zustände des Systems 4.2.3 Singuläre Systeme 5 Symbolische Optimierung 5.1 Definition und Anwendung symbolischer Optimierungen 5.2 Allgemeine symbolische Optimierung 5.2.1 Finden und Entfernen trivialer Gleichungen 5.2.2 Tearing und Relaxation 5.2.3 Inline Integration 5.2.4 Parallelisierung 5.3 Fachbereichsspezifische symbolische Optimierung 5.3.1 Relaxation O(n) für Mehrkörpersysteme 6 Umsetzung Modelica Compiler BackEnd 6.1 Konzepte für die Implementation 6.1.1 Datenstruktur 6.1.2 Teilschritte der Analyse und Optimierungsphase 6.1.3 BackEnd Pipeline 6.1.4 Kausalisierung 6.2 Testen der Implementation 7 Laufzeituntersuchung an skalierbaren Modellen 7.1 Software-Benchmark Umgebung für Modelica Compiler - ModeliMark 7.2 Modelle für Laufzeituntersuchungen 7.3 Ergebnisse 8 Zusammenfassung und Ausblick

Während das lokale Verhalten von geodätischen Kurven in Riemannschen Mannigfaltigkeiten gut verstanden ist, ist es wesentlich schwieriger das globale Verhalten dieser Kurven zu untersuchen. Die vorliegende Dissertation greift daher zwei Themen heraus, in denen globale Eigenschaften von Geodätischen mit Invarianten Riemannscher Mannigfaltigkeiten in Verbindung gebracht werden. Zum Einen wird das Koprodukt der String-Topologie untersucht. Diese auf der Homologie des freien Schleifenraumes einer geschlossenen Mannigfaltigkeit definierte Abbildung kann geometrisch verstanden werden als Operation, welche Schleifen mit Selbstschnitten in zwei Teile zerschneidet. In der vorliegenden Dissertation wird gezeigt, dass das nicht-triviale Verhalten einer Iteration des Koprodukts genutzt werden kann um die Multiplizitäten bestimmter geschlossener Geodätischer abzuschätzen. Zudem wird das Koprodukt für bestimmte Klassen von Mannigfaltigkeiten untersucht. Der freie Schleifenraum einer Lie-Gruppe ist homömorph zum Produkt der Gruppe mit ihrem Schleifenraum bezüglich eines Punktes. Dies induziert einen Isomorphismus in Homologie und es wird gezeigt, dass sich das Koprodukt unter diesem Isomorphismus gut verhält. Durch das Nutzen expliziter Zykel kann man zudem sehen, dass das Koprodukt für kompakte, einfach zusammenhängende Lie-Gruppen von höherem Rang trivial ist. Anschließend wird das Koprodukt für den komplexen und den quaternionisch projektiven Raum berechnet. Hierfür werden wieder explizite Zykel genutzt, auf die das Koprodukt in gewisser Weise zurückgezogen werden kann. Im zweiten Teil der Dissertation wird die geodätische Komplexität einer vollständigen Riemannschen Mannigfaltigkeit untersucht. Die geodätische Komplexität ist eine ganzzahlige Isometrie-Invariante von vollständigen Riemannschen Mannigfaltigkeiten, welche man als Abstraktion des Problems der geodätischen Bewegungsplanung verstehen kann. Es stellt sich heraus, dass die geodätische Komplexität stark vom Schnittort einer vollständigen Riemannschen Mannigfaltigkeit abhängt. In der vorliegenden Dissertation wird die Struktur des Schnittorts von homogenen Riemannschen Mannigfaltigkeiten genutzt um eine obere Schranke an die geodätische Komplexität solcher Räume zu erhalten. Diese Abschätzung liefert insbesondere für Lie-Gruppen gute Resultate und kann genutzt werden um die geodätische Komplexität von zweidimensionalen flachen Tori und von Berger-Sphären zu bestimmen. Eine andere obere Schranke für die geodätische Komplexität erhält man durch das Betrachten von sogenannten gefaserten Zerlegungen des Schnittorts. In der vorliegenden Dissertation werden diese Zerlegungen eingeführt und es wird gezeigt, dass die Schnittorte aller kompakten irreduziblen einfach zusammenhängenden symmetrischen Räume solch eine Zerlegung zulassen. Dieses Resultat kann dann genutzt werden um eine Abschätzung der geodätischen Komplexität dieser Räume zu erhalten. Insbesondere kann die geodätische Komplexität vom komplexen und vom quaternionisch projektiven Raum bestimmt werden. Dieser zweite Teil der Dissertation geht aus einem gemeinsamen Projekt mit Stephan Mescher hervor. / While the local behavior of geodesics in Riemannaian manifolds is well understood, it is much harder to study the global behavior of such curves. In this thesis we study two problems which connect global properties of geodesics to invariants of Riemannian manifolds. Firstly, we study the string topology coproduct. This is a map on the homology of the free loop space of a closed manifold and can be understood as an operation that cuts loops with self-intersections into two parts. It is shown in the thesis that the non-trivial behavior of an iterate of the coproduct can be used to estimate the multiplicity of certain closed geodesics. Furthermore, we study the coproduct for particular classes of manifolds. The free loop space of a Lie group is homeomorphic to the product of the group with its based loop space. This induces an isomorphism in homology and we show that the coproduct behaves well with respect to this isomorphism. By considering explicit cycles one can show that the string topology coproduct is trivial for compact simply connected Lie groups of higher rank. Moreover, the string topology coproduct is computed explicitly for complex and quaternionic projective space again by using certain explicit cycles. In the second part of the thesis we study the geodesic complexity of complete Riemannian manifolds. Geodesic complexity is a numerical isometry invariant of complete Riemannian manifolds and can be understood as an abstraction of the geodesic motion planning problem. It turns out that the geodesic complexity of a complete Riemannian manifold highly depends on the cut locus of that manifold. We use the structure of the cut loci of homogeneous Riemannian manifolds to obtain an upper bound on the geodesic complexity of these spaces. This bound turns out to work very well for Lie groups and we use it to compute the geodesic complexity of flat two-dimensional tori and of Berger spheres. Another upper bound on geodesic complexity can be obtained by considering fibered decompositions of the total cut locus. In this thesis we introduce the concept of a fibered decomposition and show that the cut loci of compact irreducible simply connected symmetric spaces admit such decompositions. This result can then be used to prove an upper bound on the geodesic complexity of these spaces. In particular we determine the geodesic complexity of complex and quaternionic projective space. This second part of the thesis is based on joint work with Stephan Mescher.

Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet, auf endlichen Strukturen, ist bekanntermassen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen, wie Constraint Satisfaction Problems (CSP): Im Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen, dass Datalog auf linearen Ordnungen (auch dichte und diskrete, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist. Für die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme, die sich ohne Rekursion lösen lassen. Ein Transfer unserer Methoden auf CSPs zeigt, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen, wie Datalog. / Datalog is the relational variant of logic programming and has become a standard query language in database theory. The (program) complexity of datalog in its main context so far, on finite databases, is well known to be in EXPTIME. We research the complexity of datalog on infinite databases, motivated by possible applications of datalog to infinite structures (e.g. linear orders) in temporal and spatial reasoning on one hand and the upcoming interest in infinite structures in problems related to datalog, like constraint satisfaction problems: Unlike datalog on finite databases, on infinite structures the computations may take infinitely long, leading to the undecidability of datalog on some infinite structures. But even in the decidable cases datalog on infinite structures may have arbitrarily high complexity, and because of this result, we research some structures with the lowest complexity of datalog on infinite structures: Datalog on linear orders (also dense or discrete, with and without constants, even colored) and tree orders has EXPTIME-complete complexity. To achieve the upper bound on these structures, we introduce a tool set specialized for datalog on orders: Order types, distance types and type disjoint programs. The type concept yields a finite representation of the infinite program results, which could also be of interest for practical applications. We create special type disjoint versions of the programs allowing to solve datalog without the recursion inherent in each datalog program. A transfer of our methods shows that constraint satisfaction problems on infinite structures occur with arbitrarily high time complexity, like datalog.

Human infants have been shown to have an innate capacity to acquire their mother tongue. In recent decades, the advent of the functional magnetic resonance imaging (fMRI) technique has made it feasible to explore the neural basis underlying language acquisition and processing in children, even in newborn infants (for reviews, see Kuhl & Rivera-Gaxiola, 2008; Kuhl, 2010) . Spontaneous low-frequency (< 0.1 Hz) fluctuations (LFFs) in the resting brain have been shown to be physiologically meaningful in the seminal study (Biswal et al., 1995) . Compared to task-based fMRI, resting-state fMRI (rs-fMRI) has some unique advantages in neuroimaging research, especially in obtaining data from pediatric and clinical populations. Moreover, it enables us to characterize the functional organization of the brain in a systematic manner in the absence of explicit tasks. Among brain systems, the language network has been well investigated by analyzing LFFs in the resting brain. This thesis attempts to investigate the functional connectivity within the language network in typically developing preschool children and the covariation of this connectivity with children’s language development by using the rs-fMRI technique. The first study (see Chapter 2.1; Xiao et al., 2016a) revealed connectivity differences in language-related regions between 5-year-olds and adults, and demonstrated distinct correlation patterns between functional connections within the language network and sentence comprehension performance in children. The results showed a left fronto-temporal connection for processing syntactically more complex sentences, suggesting that this connection is already in place at age 5 when it is needed for complex sentence comprehension, even though the whole functional network is still immature. In the second study (see Chapter 2.2; Xiao et al., 2016b), sentence comprehension performance and rs-fMRI data were obtained from a cohort of children at age 5 and a one-year follow-up. This study examined the changes in functional connectivity in the developing brain and their relation to the development of language abilities. The findings showed that the development of intrinsic functional connectivity in preschool children over the course of one year is clearly observable and individual differences in this development are related to the advancement in sentence comprehension ability with age. In summary, the present thesis provides new insights into the relationship between intrinsic functional connectivity in the brain and language processing, as well as between the changes in intrinsic functional connectivity and concurrent language development in preschool children. Moreover, it allows for a better understanding of the neural mechanisms underlying language processing and the advancement of language abilities in the developing brain.