+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Donnerstag, 22. Juli 2002, 13.00 Uhr
Ort: Zoom Videokonferenz
https://rwth.zoom.us/j/97475619537?pwd=NzBLYkFqREVISyt3QnNSd1ZoK2NZZz09
Referent: Dipl.-Inf. Joachim Protze
Lehrstuhl Informatik 12
Thema: Modular Techniques and Interfaces for Data Race Detection in
Multi-Paradigm Parallel Programming
Abstract:
The demand for ever-growing computing capabilities in scientific
computing and simulation has led to heterogeneous computing systems with
multiple parallelism levels. The aggregated performance of the Top 500
high-performance computing (HPC) systems showed an annual growth rate of
85% for the years 1993-2013. As this growth rate significantly exceeds
the growth rate of 40% to 60% supported by Moore’s law, the additional
growth was always supported by an increasing number of computing nodes
with distributed memory and connected by a network. The message passing
interface (MPI) proved to be the dominating programming paradigm for
distributed memory computing as the most coarse-grain level of
parallelism in HPC. While performance gain from Moore’s law in the last
century mainly went into single-core performance by increasing the clock
frequency, we see an increasing number of computing cores per socket
since the beginning of this century. The cores within a socket or a
node share the memory. Although MPI can be used and is used for shared
memory parallelization, explicit use of shared memory as with OpenMP can
improve the scalability and performance of parallel applications. As a
result, hybrid MPI and OpenMP programming is a common paradigm in HPC.
Memory access anomalies such as data races are a severe issue in
parallel programming. Data race detection has been studied for years,
and different static and dynamic analysis techniques have been
presented. This work will not try and propose fundamentally new analysis
techniques but will show how high-level abstraction of MPI and OpenMP
can be mapped to the low-level abstraction of analysis tools without
impact on the analysis’s soundness. This work develops and presents
analysis workflows to identify memory access anomalies in hybrid, multi-
paradigm parallel applications. This work collects parallel variants of
memory access anomalies known from sequential programming and identifies
specific patterns for distributed and shared memory programming.
Furthermore, this work identifies the high-level synchronization,
concurrency, and memory access semantics implicitly and explicitly
defined by the parallel programming paradigms’ specifications to provide
a mapping to the analysis abstraction. As part of these high-level
concurrency concepts, we can identify several sources of concurrency
within a thread. This work compares two techniques to handle this high-
level concurrency for data race analysis and finds that a combined
approach works best in the general case. The evaluation shows that this
work’s analysis workflow provides a high precision while enabling
increased recall for concurrency within a thread.
In this talk, we will focus on the mapping of high-level concurrency
abstractions to low-level analysis abstractions as an important key
point of this thesis and present the results of the work.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Freitag, 23. Juli 2021, 10:00 Uhr
Zoom: https://rwth.zoom.us/j/97181863376?pwd=VmZIUzlNTXhQRFl0S25uRFBTRW0wdz09
Meeting-ID: 971 8186 3376
Kenncode: 867315
Referent: Richard Wilke, M.Sc.
LuFG Mathematische Grundlagen der Informatik
Thema: Reasoning about Dependence and Independence: Teams and Multiteams
Abstract:
Team semantics is the mathematical basis of modern logics for reasoning about
dependence and independence. Its core feature is that formulae are evaluated
against a set of assignments, called a team. This approach dates back to Hodges (1997)
who used it to provide a compositional semantics for independence friendly logic.
Building on this idea, Väänänen (2007) suggested that dependencies between variables should
not be treated as annotations of quantifiers, but as atomic properties of teams.
However, being based on sets, team semantics can only be used to reason about the
presence or absence of data. Multiteam semantics instead takes multiplicities of
data into account and is based on multisets of assignments, called multiteams.
In this talk we give an overview of this formalism, explore a wide spectrum of logics
with multiteam semantics and compare them with regard to their expressive power.
We exhibit some striking differences between multiteam and team semantics, and also
show where these formalisms are similar. Moreover, we present a game-theoretic
semantics for our logic and establish connections between logics with multiteam
semantics and variants of existential second-order logic.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 19. Juli 2021, 14.30 Uhr
Zoom: https://rwth.zoom.us/j/99446295120?pwd=NWU0QmIvVkpONlV2R0xmbmloTkhZZz09
Referent: Dipl.-Ing. Evgeny Kusmenko
Lehrstuhl Informatik 3
Thema: Model-Driven Development Methodology and Domain-Specific Languages for the Design of Artificial Intelligence in Cyber-Physical Systems
Abstract:
The development of cyber-physical systems poses a multitude of challenges requiring experts from different fields. Such systems cannot be developed successfully without the support of appropriate processes, languages, and tools. Model-driven software engineering is an important approach which helps development teams to cope with the increasing complexity of today's cyber-physical systems. In this talk we are going to discuss a model-driven engineering methodology with a particular focus on interconnected intelligent cyber-physical systems such as cooperative vehicles.
The basis of the proposed methodology is a component-and-connector architecture description language focusing on the decomposition and integration of cyber-physical system software. It features a strong, math-oriented type system abstracting away from
the technical realization and incorporating physical units. To facilitate the development of highly-interconnected self-adaptive systems, the language enables its users to model component and connector arrays and supports architectural runtime-reconfiguration. Architectural elements can be altered, added, and removed dynamically upon the occurrence of trigger events.
In order to fully cover the development process, the proposed methodology, in addition to structural modeling, provides means for behavior specification and its seamless integration into the components of the architecture. A matrix-oriented scripting language enables
the developer to specify algorithms using a syntax close to the mathematical domain. What is more, a dedicated deep learning modeling language is provided for the development and training of neural networks as directed
acyclic graphs of neuron layers. The framework supports different learning methods including supervised, reinforcement, and generative adversarial learning, covering a broad range of applications from image and natural language processing to decision making and test data generation.
The presented toolchain enables an automated generation of fully functional C++ code together with the corresponding build and training scripts based on the architectural models and behavior specifications. Finally, to facilitate the integration and deployment of the modeled software in distributed environments, we use a tagging approach to model the middleware and to control a middleware generation toolchain.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Mittwoch, 14. Juli 2021, 10.00 Uhr
Ort: Zoom Videokonferenz
Link: https://rwth.zoom.us/j/94853770165?pwd=Uzk4TjI4TGNJQ3owaXJDbUxMT2d0UT09
Meeting-ID: 948 5377 0165
Kenncode: 046795
Referent: Patrick Landwehr M.Sc.
Lehrstuhl Informatik 7
Thema: Tree Automata with Constraints on Infinite Trees
Abstract:
Tree automata on infinite trees are a powerful tool that is widely used for decision procedures and synthesis of logical specifications.
It is well known that finite tree automata have good algorithmic properties, but somewhat limited expressive power.
For example, they cannot verify that certain subtrees of an input tree are equal.
In order to model such properties, we study extensions of tree automata that use so called constraints to compare whole subtrees of an input.
We distinguish between two types of constraints: local constraints and global constraints.
Local constraints can be used to compare the direct subtrees of each node.
In this thesis we first summarize the existing results of tree automata with local constraints for infinite trees.
Then we paritally answer the open question whether the class of languages recognizable by these automata is closed under projection.
That is, we show that in the case of automata with Büchi acceptance condition the class of recognizable languages is closed under projection.
As a consequence, we obtain a new decision algorithm for the emptiness problem as well as a proof for the fact that each non-empty language recognized by a Büchi tree automaton with sibling constraints contains a regular tree.
Moreover, we also study logical characterizations of this class of languages.
Tree automata with global constraints are able to compare compare subtrees whose positions are defined by the states reached in a run.
For example, this model can verify that all subtrees rooted at positions where a certain state is reached are equal.
In this thesis we generalize the model introduced on finite trees to the setting of infinite trees.
We show that most closure properties and decidability results can be extended from finite to infinite trees.
However, new techniques are required in order to do so.
While the decidability of the emptiness problem remains an open question in general, we present decidability results for some subclasses of tree automata with global constraints.
That is, if the automaton tests only for equality of subtrees (and not for inequality) the emptiness problem is decidable.
The same is true if the underlying language (i.e. when ignoring the constraints) is countable.
We also study the special case of automata with global constraints on unary infinite trees (omega-words).
Here we show that in contrast to branching trees, the class of languages recognizable by these automata is closed under complement.
Finally, we present precise logical characterizations for all of the subclasses mentioned, by extensions of monadic second order logic on infinite trees (or omega-words).
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Freitag, 19. Februar 2021, 11.00 Uhr
Zoom: https://rwth.zoom.us/j/2452218628
Referent: Andrea Schnorr, M.Sc.
LuFG i12
Thema: Feature Tracking for Space-Filling Structures
Abstract:
Feature-based visualization is a proven strategy to deal with the massive
amounts of data emerging from time-dependent simulations: the analysis
focuses on meaningful structures, i.e., said features.
Feature tracking algorithms aim at automatically finding corresponding
objects in successive time steps of these time-dependent data sets in order
to assemble the individual objects into spatio-temporal features.
Classically, feature-based visualization has focused on sparse structures,
i.e. structures which cover only a small portion of the data domain.
Given a sufficiently high temporal resolution, existing tracking approaches
are able to reliably resolve the correspondence between feature objects of
successive time steps.
Our research is motivated by our collaborators' work on the statistical
analysis of structures that are space-filling by definition: dissipation
elements.
Space-filling structures partition the entire domain.
Our collaborators aim at extending their statistical analysis to a
time-dependent setting.
Hence, we introduce an efficient approach for general feature tracking
which handles both sparse and space-filling data.
To this end, we develop a framework for automatic evaluation of tracking
approaches, an algorithmic framework for feature tracking, and an efficient
implementation of this framework.
First, we propose a novel evaluation framework based on algorithmic data
generators, which provide synthetic data sets and the corresponding ground
truth data.
This framework facilitates the structured quantitative analysis of an
approach's feature tracking performance and the comparison of different
approaches based on the resulting measurements.
Second, we introduce a novel approach for tracking both sparse and
space-filling features.
The correspondence between neighboring time-steps is determined by
successively solving two graph optimization problems.
In the first phase, one-to-one assignments are resolved by computing a
maximum-weight, maximum-cardinality matching on a bi-partite graph.
In its second phase, the algorithm detects events by finding a maximum
weight independent set in a graph of all possible, potentially conflicting
event explanations.
Third, we show an optimized version of the second stage of the tracking
framework which exploits the model-specific graph structure arising for the
tracking problem.
The method's effectiveness is demonstrated by a set of case studies
including the use of the evaluation framework as well as the analysis of
miscellaneous real-world simulation data sets.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Dienstag, 20. Juli 2021, 10:00-11:00 Uhr
Zoom:
<https://rwth.zoom.us/j/93538347394?pwd=YXlqZ1VqSE0vRjRnclRtQTY5RVJOZz09>
https://rwth.zoom.us/j/93538347394?pwd=YXlqZ1VqSE0vRjRnclRtQTY5RVJOZz09
Meeting-ID: 935 3834 7394
Kenncode: 388699
Referent: Herr Peter Marcel de Lange, M.Sc.
Lehrstuhl Informatik 5
Thema: Scaffolding Decentralized Community Information Systems for
Lifelong Learning Communities
Abstract:
With the rise of the Web 2.0, social networking sites and content management
systems enabled professional communities to create Web content. But it
simultaneously put the communities at the mercy of the platform operators
and software providers. Decentralized community information systems bring in
a new perspective by offering self-hosting, self-governing and
self-developing communities.
In this dissertation, we followed a design science approach that provides
support for communities to create and host their own, decentralized
community information systems. On the one hand, we produced several
artifacts to provide possible answers to the question of what properties
such an infrastructure needs to fulfill. On the other hand, we transfer the
metaphor of educational scaffolding to the domain of service development.
We demonstrated and evaluated our open source artifacts on a European scale,
with three longitudinal studies conducted within several communities from
different areas of technology enhanced learning, such as the European
voluntary service, vocational and educational training providers and in
higher education mentoring scenarios.
Es laden ein: die Dozentinnen und Dozenten der Informatik
_______________________________
Leany Maaßen
RWTH Aachen University
Lehrstuhl Informatik 5, LuFG Informatik 5
Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke,
Prof. Gerhard Lakemeyer Ph.D.
Ahornstrasse 55
D-52074 Aachen
Tel: 0241-80-21509
Fax: 0241-80-22321
E-Mail: maassen(a)dbis.rwth-aachen.de
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 21. Juni 2021, 13.00 Uhr
Ort: Videokonferenz (Zoom-Meeting, Informationen siehe unten)
Referent: David Thönnessen, M.Sc.
Lehrstuhl Informatik 11
Thema: Hardware-in-the-Loop Testing of Industrial Automation Systems
Using PLC Languages
Abstract:
Testing industrial controllers such as Programmable Logic Controllers
(PLCs) poses specific challenges to the test process. Especially in the
context of Cyber-Physical Production System (CPPS) the control systems
are subject to continuous reconfiguration. Therefore, it is no longer
sufficient to test solely before commissioning, but it must be possible
to test existing control systems after their reconfiguration with low
effort and to put them back into operation.
Our approach for this is to develop a test environment that allows an
efficient and modular test case specification and can therefore be
easily adapted to changing environmental conditions. We have chosen
Hardware-in-the-Loop (HiL) simulation as the basis for this test
environment since not only the control model or control program is
included in the test, but also the control hardware. Our architecture
uses slightly extended PLC programming languages to specify test cases.
Thus, we avoid the change in methodology that occurs when using
dedicated test case specification languages and corresponding test
environments. Furthermore, we have provided our concept with the
possibility of randomized test case generation, such that a large number
of test cases can be generated and tested without a tester having to
specify them manually.
Our hypothesis is that this will lead to faster and more reliable
customizable test cases and thus create the desired agility. The
evaluation of our implementation shows that especially developers who
are familiar with PLC programming languages can achieve an increase in
testing efficiency compared to existing test tools. Furthermore, by
randomized testing of Safety Programmable Logic Controllers (Safety PLCs),
we show that our test tool can find critical errors in control systems,
which would have been found with traditional test methods only to a
limited extent.
From these results we conclude that the concept presented here is a
valuable addition to existing test methods and well-tailored to the
challenges of CPPS.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
Thema: PhD Defense David Thönnessen
Uhrzeit: 21.Juni.2021 01:00 PM Amsterdam, Berlin, Rom, Stockholm, Wien
Zoom-Meeting beitreten
https://rwth.zoom.us/j/96024814962?pwd=eEU5SmNFTjYyWitJVldVRmQ3TE5pdz09
Meeting-ID: 960 2481 4962
Kenncode: 158094
+**********************************************************************
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Dienstag, 15. Juni 2021, 14:00-15:00 Uhr
Zoom:
https://rwth.zoom.us/j/95286197657?pwd=TWtHZHBpa3Q4bmNIZUZXZ21NSmdydz09
Meeting-ID: 952 8619 7657
Kenncode: 048149
Referent: Herr Dipl.-Inform. Sevket Gökay
Lehrstuhl Informatik 5
Thema: Scalable Real-Time Ride-Sharing with Meeting Points for
Flexible On-Demand Public Transportation
Abstract:
The landscape of personal transportation is colorful and ever-changing.
Ride-sharing, a member of the on-demand transportation family, sits between
the private and public transportation categories. It can transport multiple
passengers with similar journeys in the same vehicle in a flexible and
convenient manner. This work explores real-time ride-sharing in three steps.
First, we develop and evaluate a dynamic (i.e. flexible, on-demand) bus-like
service as an alternative to the traditional bus service in rural areas with
low demand. Simulations conducted in Aachen and in Ulm indicate that both
the providers and the customers might benefit from this alternative. Next,
we address the computational scalability issue of the service in urban areas
with high demand. We present an approach to reduce processing time by
employing an improved trip-vehicle fitness heuristic. The evaluation
simulates New York City taxi trips in a ride-sharing context, and exhibits
significant performance improvement, together with improved customer
satisfaction and vehicle costs. Finally, we investigate the prevention of
small detours of vehicles, by merging location visits with close proximity
into one by introducing small walking paths. The results hint at a
significant increase in the number of satisfied trip requests.
Es laden ein: die Dozentinnen und Dozenten der Informatik
_______________________________
Leany Maaßen
RWTH Aachen University
Lehrstuhl Informatik 5, LuFG Informatik 5
Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke,
Prof. Gerhard Lakemeyer Ph.D.
Ahornstrasse 55
D-52074 Aachen
Tel: 0241-80-21509
Fax: 0241-80-22321
E-Mail: maassen(a)dbis.rwth-aachen.de
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 14. Juni 2021, 16:00 Uhr
Ort: Zoom Videokonferenz
Link:
https://rwth.zoom.us/j/94470149252?pwd=ZnYwVXQrbStveVdDNDk1V1BlN1lJUT09
Meeting-ID: 944 7014 9252
Kenncode: 004247
Referent: Daniel Wiebking, M.Sc.
Lehrstuhl Informatik 7
Thema: A Decomposition-Compatible Canonization Framework for the Graph
Isomorphism Problem
Abstract:
The Graph Isomorphism Problem is one of a few famous problems in NP
that is neither known to be solvable in polynomial time nor to be
NP-complete.
The problem asks whether two given input graphs are structurally
equivalent, which means that both graphs coincide up to a renaming of
the vertices.
With Babai's celebrated breakthrough (STOC 2016) it was shown that the
problem can be decided in quasipolynomial time.
One way of solving the Graph Isomorphism Problem is by applying a
canonization approach.
Graph canonization is the task of transforming a graph into a canonical
form, that is, a graph representation that coincides for structurally
equivalent graphs.
As far as we know, graph canonization might be harder than the Graph
Isomorphism Problem.
In particular, there are isomorphism tests for various graph classes and
objects for which to date no canonization algorithm with the same
asymptotic running time is known.
In this thesis, we devise a unified canonization framework for graphs,
and beyond that for combinatorial objects in general.
We use that framework to design new fastest canonization algorithms with
an asymptotic running time matching the best known isomorphism tests.
Our framework supports the use of decomposition techniques.
By combining our framework with new graph-theoretic decompositions,
we not only match but even improve the running time of existing
isomorphism tests for graphs of bounded treewidth and graphs excluding
fixed minors.
Our improved algorithms for restricted graph classes come hand in hand
with new insights about the automorphism groups.
We prove several restrictions on these groups by analyzing them from a
purely mathematical point of view.
Beyond that, our decomposition-friendly framework has also applications
in computational group theory.
In particular, we design a new fastest algorithm computing normalizers
of permutation groups.
Finally, we investigate the connections between isomorphism testing and
canonization from a logical perspective.
To this end, we provide a new computation model that supports a
construction turning isomorphism tests into canonization algorithms.
Es laden ein: die Dozentinnen und Dozenten der Informatik