Archive: Kolloquium News Presse

Informatik-Kolloquium der Universität Potsdam

 

Friday, 09. August 2013: Kolloquium der Professur Betriebssysteme und Verteilte Systeme

Referent:Jörg Lenhardt, FernUniversität in Hagen
Titel:Leistungseffiziente Server-Nutzung
Resümee:

Moderne Rechenzentren beherbergen eine Vielzahl von Servern verschiedener Leistungsfähigkeit. Begründet ist dies im Wesentlichen durch die unterschiedlichen Zeitpunkte von Neuanschaffungen leistungsfähiger Hardware und des Austauschs defekter oder veralteter Computersysteme. Insgesamt handelt es sich sowohl bezogen auf die Rechenleistung als auch auf die Methoden der Leistungs- bzw. Energie-Einsparungs-Mechanismen um eine äußerst heterogene Umgebung. Aus dem Blickwinkel der Energie-Effizienz gesehen, stellt sich die Frage, wie eine momentane Rechenlast (Operationen pro Zeiteinheit) so auf die Ressourcen verteilt werden kann, dass die elektrische Leistungsaufnahme minimiert wird. Eine Minimierung der elektrischen Leistungsaufnahme ist natürlich nur dann möglich, wenn die Rechenlast kleiner als die verfügbare maximale Rechenleistung ist. Auf diese Weise wird über einen Zeitraum hinweg eine Energieeinsparung möglich.

Im Vortrag werden mittelfristige Verteilungsstrategien betrachtet, bei denen der Zusatzaufwand für die Migration von Anwendungen und das Ab- und Anschalten von Serversystemen in Bezug auf den Energiebedarf vernachlässigbar ist. Es wird eine von uns entwickelte Strategie vorgestellt, welche eine vorgegebene Rechenlast so verteilt, dass die elektrische Leistungsaufnahme des heterogenen Zielsystems minimiert wird. Dabei werden Leistungsmessungen realer Serversysteme mit Hilfe des SPECpower_ssj2008 Benchmarks zugrunde gelegt. Anhand der Ergebnisse verschiedener Szenarien werden die Stärken und Schwächen des Verfahrens diskutiert.


 

Tuesday, 09. July 2013: Kolloquium der Professur Betriebssysteme und Verteilte Systeme

Referent:Prof. Dietmar Fey, Friedrich-Alexander-Universität Erlangen-Nürnberg
Titel:Transparenter Zugriff auf Heterogene Architekturen für Stencil-Applikationen im Embedded und HPC-Umfeld
Resümee:

Viele Berechnungen aus dem Bereich des wissenschaftlichen Rechnens basieren auf sog. Stencil-Algorithmen. Bekannte Bespiele sind u.a. die Lösung von Partiellen Differentialgleichungen mit der Methode der Finiten Differenzen oder auch die Vielzahl an Operatoren aus der Bildverarbeitung, z.B. zur Auswertung von CT-Daten, welche als Stencils formulierbar sind. Kennzeichen dieser Algorithmen ist die Daten-parallele Berechnung von Gitterpunkten in ein- oder mehr-dimensionalen Gitterstrukturen. In aufeinanderfolgenden diskreten Zeitschritten werden für alle Gitterpunkte neue Zustände berechnet, die vom Zustand des Gitterpunktes selbst und den Zuständen direkter Nachbarpunkte im unmittelbar vorherigen diskreten Zeitschritt abhängen. Da man häufig großen Datenmengen in sehr kurzer Zeit bearbeiten möchte, sind Parallelisierungen notwendig, für die im Bereich des High Performance Computing (HPC) GPUs, vereinzelt FPGAs, im Bereich der Embedded Anwendungen zumeist FPGAs als Hardware-Beschleuniger neben einer CPU in einer heterogenen Architektur eingesetzt werden. Eine effiziente Implementierung von Stencil-Algorithmen hängt entscheidend von der Optimierung der Speicherzugriffe ab, da Stencil-Algorithmen in der Regel Speicherbandbreiten-limitiert sind. Um die komplizierte und zeitraubende Implementierung für den Programmierer transparent zu gestalten, sind sowohl für das HPC-Umfeld als auch für die Embedded Domäne zahlreiche Frameworks, Bibliotheken, Domänen-spezifische Compiler, z.T. kombiniert mit Autotuning-Optimierungen, entstanden.

Im Vortrag werden sowohl aus der Literatur bekannte als auch an der FAU erzielte Ergebnisse zur Automatisierung von Stencil-Applikationen vorgestellt. Zu den eigenen Arbeiten zählen die Bibliothek LibGeoDecomp (Library for Geometric Decomposition Codes) für das HPC-Umfeld und VHDL-Templates für die Embedded Domäne. LibGeoDecomp unterstützt Computersimulationen von Stencil-Codes bis hin zu N-Body-Codes. Die Bibliothek übernimmt die Parallelisierung des Programms, der Nutzer kann sich so auf sein Simulationsmodell konzentrieren. Über Plug-ins kann die Bibliothek auf verschiedenste Hardwareplattformen portiert werden. Sie skaliert von Smart Phones bis hin zu mit Grafikkarten bestückten Supercomputern. VHDL-Templates berücksichtigen explizit die Bandbreiten-Limitierung von FPGA-Bausteinen, der durch Aufrollen der äußeren Schleife eines Stencil-Algorithmus und geeigneten Speicherpufferungen entgegengewirkt wird.


 

Friday, 05. July 2013: Kolloquium der Professur Betriebssysteme und Verteilte Systeme

Referent:Wilhelm Dolle,
Titel:Computer Forensik in Theorie und Praxis

 

Thursday, 27. June 2013: Kolloquium der Professur Theoretische Informatik

Referent:Benedikt Ahrens, IAS Princeton
Titel:Category theory in the Univalent Foundations
Resümee:

The Univalent Foundations is an extension of Intensional Martin-Löf Type Theory (MLTT) recently proposed by V. Voevodsky. Its novelty is the Univalence Axiom which provides "more equalities between types" by identifying equality of types with isomorphism of types. When formalizing category theory in traditional, set-theoretic foundations, a significant discrepancy between the foundational notion of "sameness" - equality - and its categorical notion arises: most category-theoretic concepts are invariant under weaker notions of sameness than equality, namely isomorphism in a category or equivalence of categories. We show that this discrepancy can be avoided when formalizing category theory in Univalent Foundations.

In this talk I first give an introduction to Voevodsky's Univalent Foundations. Afterwards I define categories and univalent categories within Univalent Foundations, and develop basic category theory. The two main results of our work are the following:
1) Two univalent categories are equivalent (in the category-theoretic sense) if and only if they are equal (in the type-theoretic sense).
2) Any category can be turned into a univalent category via a universal construction, which we call the Rezk completion.

--> slides

Benedikt Ahrens did his PhD studies at the Université Nice Sophia Antipolis under the supervision of André Hirschowitz. In his thesis "Initiality for Typed Syntax and Semantics" he formalized the semantics of functional programming languages in a categorical setting using the Coq proof assistant.

During the special year on "Univalent Foundations of Mathematics" at the Institute for Advanced Study in Princeton, together with Chris Kapulkin and Michael Shulman he developed category theory within Univalent Foundations, a foundational system for mathematics based on a homotopical interpretation of dependent type theory.


 

Thursday, 27. June 2013: Kolloquium der Professur Betriebssysteme und Verteilte Systeme

Referent:Dipl.-Inf. Alexander von Gernler, Technischer Botschafter, genua mbh
Titel:Aufbau und Funktion von Hochsicherheits-Firewalls
Resümee:

In diesem Gastvortrag wird am Beispiel einer real existierenden zweistufigen Firewall die Architektur und Wirkungsweise einer solchen Appliance im Hochsicherheitsumfeld vorgestellt. Es werden beispielhaft verschiedene Komponenten wie minimalistisches Betriebssystem, rekursiver Virenscanner oder Application Level Proxies sowie Ihr Einfluss auf das Gesamtsystem diskutiert. Der Zusammenhang zwischen eingesetzten Methoden der Softwaretechnik wie Peer Review, Test Driven Development oder Continuous Integration auf die Qualität des Entwicklungsprozesses wird beleuchtet. Kurze Ausblicke auf spezielle Einsatzszenarien, Zertifizierung, Vernetzung mit der OpenSource-Szene und die Pläne fuer die Zukunft runden den Vortrag ab.

Alexander von Gernler ist seit 2005 Mitarbeiter der genua mbh in Kirchheim bei München. Bei dem Firewallhersteller im Hochsicherheits- bereich war er zunächst als Software-Entwickler und später als Scrum-Master tätig. Inzwischen ist er stellvertretender Leiter der Gruppe "Forschung und Entwicklung" und dadurch ständig auf der Suche nach den Firewall-relevanten Themen für morgen. Er betreut die zahlreichen geförderten Forschungsprojekte der Firma und ist immer auf der Suche nach neuen interessanten Kooperationen und Kontakten.

Als Technischer Botschafter hält er Kontakt zu Universitiäten, Hochschulen und Forschungseinrichtungen und kümmert sich so um die Vernetzung der Firma genua im akademischen Umfeld. Unter anderem vermittelt er auch Themen für praxisnahe und technisch anspruchsvolle Bachelor- und Masterarbeiten im Hochsicherheitsumfeld.


 

Tuesday, 25. June 2013: Kolloquium der Professur Theoretische Informatik

Referent:Edwin Brady, University of St. Andrews
Titel:Dependently Typed Functional Programming with Idris
Resümee:

Idris is a general purpose pure functional programming language with dependent types. Its syntax is influenced by Haskell and its features include full dependent types and records, type classes, tactic based theorem proving, totality checking and an optimising compiler with a foreign function interface. One of the goals of the Idris project is to bring type-based program verification techniques to functional programmers while still supporting efficient systems programming via an optimising compiler and interaction with external libraries.

In this talk I will introduce dependently typed programming using Idris, and demonstrate its features using several examples including an interpreter for the simply typed lambda calculus, and a verified binary adder.

Edwin Brady is a Lecturer in Computer Science at the University of St Andrews, interested in type theory, dependently typed functional programming, compilers and domain specific languages (DSLs).

Prof. Brady designed and implemented Idris, a functional programming language with dependent types suitable for systems programming. Both Ivor, the tactic based theorem proving engine of Idris, and the compiler backend Epic are available as separate Haskell libraries. Epic is currently also used as an experimental back end for the dependently typed functional programming language Agda.

Using Idris, he currently works on the implementation of DSLs for stateful, resource-aware programming, especially for correct network protocol design and implementation.


 

Thursday, 18. April 2013: Auftaktveranstaltung Geomatik-Kolloquium

Referent:M. Hammitzsch, GFZ Potsdam
Titel:FOSSLAB - Free and Open Source Laboratory im GFZ
Resümee:

FOSSLAB bietet eine Plattform für die Entwicklung von Open Source Software Projekten, die einen Bezug zur Geoinformatik haben. Alle bisherigen Entwicklungen in FOSSLAB sind im Rahmen von Projekten des Deutschen GeoForschungsZentrums GFZ entstanden und basieren zum größten Teil auf FOSS-Komponenten und Industrie-Standards. Schwerpunkt war und ist die Nutzung von Open Source Technologien, die ausgereifte Modelle für Softwaresystemarchitekturen unterstützen. FOSSLAB soll sich zukünftig als Plattform für die Entwicklung von FOSS-Projekten etablieren, die mit Geodaten arbeiten. Ihre Mitglieder sollen nicht nur die Möglichkeit haben, Ergebnisse über FOSSLAB zu sichern und zur Nachnutzung anzubieten, sondern sollen auch auf Ergebnisse aus früheren und laufenden Projektaktivitäten zugreifen, diese wiederverwenden und weiterentwickeln.

Bereits erarbeitete Ergebnisse sollen so die weitere Entwicklung ermöglichen und die Zusammenarbeit einer heterogenen Gemeinschaft von Wissenschaftlern, Entwicklern, Anwendern und anderen Interessengruppen stärken. FOSSLAB bildet dabei einen Schirm für eine Reihe von in Beziehung stehenden Geoinformatikaktivitäten wie Softwaresystemdesign, Implementierung, Training und Dokumentation von Best Practices für Erfahrungen und Ergebnisse bei der Arbeit mit SDIs, GIS, der räumlichen Verarbeitung auf Clustern und in der Cloud, Geomatik und vielem mehr.

Der Fokus der Veranstaltung liegt dabei auf einem aktuellen Projekt, das unter anderem ein komponentenbasiertes Softwaresystem für die Tsunami-Frühwarnung implementiert und dessen Entwicklungsteam im Rahmen von FOSSLAB Ergebnisse sichert, weiterentwickelt und Interessengruppen zur Nachnutzung und Weiterentwicklung zur Verfügung stellt.


 

Tuesday, 15. January 2013: Kolloquium

Referent:Prof. Dr. Joachim Wächter, Deutsches GeoForschungsZentrum
Titel:Warnsysteme - von der Sensor-Integration zum System-of-Systems
Resümee:

Das Tsunami-Desaster Dezember 2004 im Indischen Ozean hat intensive internationale Anstrengungen initiiert, um die Risiken von geologischen Katastrophen zu reduzieren. Dazu gehört auch die Entwicklung von Krisen-Informationssystemen. Diese Systeme zeigen in ihrer Funktionalität und Architektur eine signifikante Weiterentwicklung.

Ein Schwerpunkt ist dabei die Integration von Sensorsystemen, Simulationskomponenten und anderen Ressourcen in standardisierte Service-Plattformen. Auf dieser Basis können relevante Prozesse, wie Erdbebenaktivität oder Veränderungen des Meeresspiegels beobachtet und Gefahren erkannt werden. Prognostische Simulationen liefern dann die Grundlagen, um die lokalen Auswirkungen von Ereignissen auf bestimmte Regionen zu analysieren und gezielt Warnmeldungen über verfügbare Disseminationskanäle an definierte Zielgruppen zu versenden.

Die Wirksamkeit von nationalen Warnsystemen ist immer stärker von ihrer Integration in internationale Warninfrastrukturen abhängig. Hier arbeiten Warnzentren als System-of-Systems zusammen. Aktivitäten und Reaktionen werden über den Austausch von Messages zwischen den Systemen synchronisiert und gesteuert.


 

Tuesday, 03. April 2012: Kolloquium der Arbeitsgruppe Operating Systems and Distributed Systems

Referent:Prof. Jürgen Schönwälder, Jacobs University Bremen gGmbH
Titel:Internet of Things: Standards for IPv6 enabled Sensor Networks
Resümee:

Since 2006, the IETF is working on a set of standards for the Internet of Things. The work originally focused on running IPv6 over IEEE 802.15.4 radios and has since then grown into a much larger project involving several IETF working groups. The goal of the presentation is to provide an overview of these protocol development and standardization efforts. The discussion starts from the IEEE 802.15.4 physical and MAC layer, covers the IPv6 adaptation layer (6LoWPAN), the tree routing layer (RPL), and finally a contrained application protocol (CoAP). The presentation will also explore how more traditional protocols such as SNMP, mDNS or (D)TLS can be ported to constrained devices. A demo with some blinking LEDs will be provided for those who love to see some hard- and software in action.

CV: Prof. Schönwälder is an associate professor of Computer Science at Jacobs University Bremen, where he leads the computer networks and distributed systems research group. He received his Diploma degree in 1990 and his doctoral degree in 1996 from the Technical University Braunschweig, Germany. His research interests are network management, distributed systems, wireless sensor networks, and network security.

Prof. Schönwälder is an active member of the Internet Engineering Task Force (IETF) where he has edited about 30 network management related specifications and standards. He is currently co-chairing the ISMS working group in the Security Area of the IETF and the NETMOD working group in the Operations and Management Area. He is the initiator and chair of the Network Management Research Group (NMRG) of the Internet Research Task Force (IRTF).

Jürgen Schönwälder urrently serves on the editorial boards of the IEEE Transactions on Network and Service Management, the Springer Journal of Network and Systems Management and the Wiley International Journal of Network Management. He served as a guest co-editor of special issues of the IEEE Communications Magazine, the IEEE Journal on Selected Areas in Communications, and the Springer Journal of Network and Systems Management. He has been technical program co-chair of IM 2003 and DSOM 2005. In 2007, he organized the first International Summer School on Network and Service Management (ISSNSM 2007) and a Dagstuhl seminar on Autonomic Management of Networks and Services. In 2008, he organized the 2nd conference on Autonomous Infrastructures, Management and Security (AIMS 2008) and in 2009 he co-organized a Dagstuhl seminar on Visualization and Monitoring of Network Traffic.


 

Wednesday, 13. July 2011: 12. Ringvorlesung "Medienkonsum im Wandel"

Referent:Mike Hinchey, Lero - Software Engineering Research Center, Ireland, University of Limerick
Titel:Evolving Critical Systems - ECS
Resümee:

Increasingly software can be considered to be critical, due to the business or other functionality which it supports. Upgrades or changes to such software are expensive and risky, primarily because the software has not been designed and built for ease of change. Expertise, tools and methodologies which support the design and implementation of software systems that evolve without risk (of failure or loss of quality) are essential. We address a research agenda for building software that (a) is highly reliable and (b) retains this reliability as it evolves, either over time or at run-time. We propose Evolving Critical Systems as an area for research to tackle the challenge and outline a number of scenarios to highlight some of the important research questions that should be asked of the community. Given that software evolution can be seen as a compromise between cost and risk, the most pressing question to ask is which processes, techniques and tools are most cost-effective for evolving critical systems?

Mike Hinchey is Director of Lero, the Irish Software Research Center, and Professor of Software Engineering at University of Limerick Ireland. Until January 2007, he was Director of the NASA Software Engineering Laboratory, located at NASA Goddard Space Flight Center in Greenbelt, MD.

He now serves as a NASA expert consultant. Prior to joining the US government, at various times he held positions at the level of full professor in the US, Australia, Sweden, Ireland and the UK. He received a B.Sc. in Computer Science from University of Limerick, Ireland, an M.Sc. in Computation from University of Oxford, UK, and a Ph.D. in Computer Science from University of Cambridge, UK.

He is Chair of the IEEE Technical Committee on Complexity in Computing, Vice Chair of the IEEE Technical Committee on Autonomous and Autonomic Systems, and is the IEEE Computer Society's representative to IFIP Technical Committee 1 (Foundations of Computer Science), which he currently chairs, and a member of the IFIP Board and Chair of its Technical Assembly.


 

Monday, 04. July 2011: Kolloquium der Arbeitsgruppe Fehlertolerantes Rechnen

Referent:Prof. Krishnendu Chakrabarty, Duke University, USA
Titel:Advances in Board-Level Functional-Mode Fault Diagnosis
Resümee:

Increasing integration densities and high operating speeds are leading to subtle manifestations of defects at the board level. Despite recent advances in structural test methods, the diagnosis of the root cause of board-level failures for functional tests remains a major challenge.

In this talk, the speaker will present two methods for rapid identification of faulty components on a board and modules within a component. In the first part, the speaker will present a new method based on dataflow analysis and Dempster-Shafer theory for ranking candidate faulty blocks. In the second part of the talk, the speaker will describe how machine learning methods such as artificial neural networks and support-vector machines, which can learn from repair history, can be used to increase the success rate for board-level functional fault diagnosis. Results will be presented for a large communication ASIC from industry and for fault diagnosis of a complex telecom board currently in high-volume production.


 

Tuesday, 28. June 2011: Kolloquium der Professur Theoretische Informatik

Referent:Prof. Thorsten Altenkirch, University of Nottingham
Titel:A Short History of Equality
Resümee:

Typtheorie à la Martin-Löf ist gleichzeitig eine Programmiersprache und eine Alternative zur klassischen Mengenlehre (Zermelo-Fraenkel), aufbauend auf der Analogie von Aussagen und Typen (Curry-Howard). Diese Tatsache wird in Systemen wie Agda und Coq ausgenutzt, die sich gleichzeitig als Programmeditoren und interaktive Beweissysteme eignen.

In dem Vortrag werde ich mich nach einer allgemeinen Einführung in die Typtheorie auf die Gleichheitstypen konzentrieren, die Menge der Beweise, dass zwei Ausdrücke gleich sind. Die Interpretation dieses Typen ist kontrovers: Sollen wir Werte nur dann identifizieren, wenn sie die gleiche Form haben (intensional) oder wenn sie dasselbe Verhalten haben (extensional)? Soll es immer nur einen Beweis der Gleichheit geben (Beweisirrelevanz), oder kann es auch mehrere geben? Ein neue Interpretation der Typtheorie durch topologische Modelle (Homotopien) des bekannten Mathematikers Vladimir Voevodsky wirft ein neues Licht auf diese Fragen.

--> Thorsten Altenkirch


 

Wednesday, 01. December 2010: Kolloquium

Referent:Prof. Dr. Wolfgang Karl, Karlsruhe Institute of Technology (KIT)
Titel:Heterogene parallele Rechnerstrukturen - Beherrschbarkeit durch Adaptivität und Virtualisierung
Resümee:

Zukünftige Systemstrukturen für Server in den Bereichen des Höchstleistungsrechnens und kommerzieller Anwendungen als auch für eingebettete Systeme werden mit Multi- oder Manycore-Prozessoren aufgebaut. Das Spektrum solcher Multicore-Prozessoren reicht von homogenen Strukturen mit wenigen komplexen Kernen bis zu heterogenen Strukturen, insbesondere im Bereich eingebetteter Systeme. Eine signifikante Erhöhung der Leistungsfähigkeit der Systeme wird auf diese Weise durch Ausnützung des Parallelismus auf allen Systemebenen als auch durch die Verlagerung rechenintensiver Teile eines Programms auf anwendungsspezifische Hardware-Komponenten erreicht. Heterogenität zeichnet auch Grid-Strukturen aus.

Die Herausforderung für die Rechnerarchitektur ist nicht nur, leistungsfähige Systemstrukturen bereitzustellen, sondern auch, die Komplexität vor dem Nutzer zu verbergen. Im Vortrag werden als wesentliche Merkmale zur Beherrschung der Komplexität hierzu Ansätze zur Adaptivität und Virtualisierung vorgestellt.


 

Tuesday, 20. July 2010: Kolloquium der Professur Technische Informatik

Referent:Dr. Dirk Koch, Universität Oslo
Titel:Advances in Component-based System Design and Partial Run-time Reconfiguration
Resümee:

With passing over the 1M LUT barrier, FPGA technology is heading into new challenges and opportunities. While the present ASIC-like design methodology and tools will struggle to scale with such huge devices, providing partial run-time reconfiguration will be become obligatory for dealing with long configuration times and the increasing vulnerability to single event upsets.

Within the COSRECOS project, we address these issues by developing methods and tools that allow to compose systems rapidly by plugging together fully physically implemented components. Moreover, by allowing a hot-swapping of such components, the tremendous advantages of partial run-time reconfiguration can be utilized.

This talk will give an overview of recent trends, our present research activities, and will discuss open issues.


 

Friday, 04. June 2010: Kolloquium

Referent:Distinguished Prof. Dr. Jack Dongarra, University of Tennessee Oak Ridge National Laboratory
Titel:Impact of Architecture and Technology for Extreme Scale on Software and Algorithm Design
Resümee:

In this talk we examine how high performance computing has changed over the last 10-year and look toward the future in terms of trends. These changes have had and will continue to have a major impact on our software. Some of the software and algorithm challenges have already been encountered, such as management of communication and memory hierarchies through a combination of compile--time and run--time techniques, but the increased scale of computation, depth of memory hierarchies, range of latencies, and increased run--time environment variability will make these problems much harder.

We will look at five areas of research that will have an importance impact in the development of software and algorithms:

  • Redesign of software to fit multicore architectures
  • Automatically tuned application software
  • Exploiting mixed precision for performance
  • The importance of fault tolerance
  • Communication avoiding algorithms

CV:

Jack Dongarra received a Bachelor of Science in Mathematics from Chicago State University in 1972 and a Master of Science in Computer Science from the Illinois Institute of Technology in 1973. He received his Ph.D. in Applied Mathematics from the University of New Mexico in 1980. He worked at the Argonne National Laboratory until 1989, becoming a senior scientist. He now holds an appointment as University Distinguished Professor of Computer Science in the Computer Science Department at the University of Tennessee and holds the title of Distinguished Research Staff in the Computer Science and Mathematics Division at Oak Ridge National Laboratory (ORNL), Turing Fellow at Manchester University, and an Adjunct Professor in the Computer Science Department at Rice University.

He specializes in numerical algorithms in linear algebra, parallel computing, the use of advanced-computer architectures, programming methodology, and tools for parallel computers. He has contributed to the design and implementation of the following open source software packages and systems: EISPACK, LINPACK, the BLAS, LAPACK, ScaLAPACK, Netlib, PVM, MPI, NetSolve, Top500, ATLAS, and PAPI. He has published approximately 200 articles, papers, reports and technical memoranda and he is coauthor of several books. He was awarded the IEEE Sid Fernbach Award in 2004 for his contributions in the application of high performance computers using innovative approaches and in 2008 he was the recipient of the first IEEE Medal of Excellence in Scalable Computing.


 

Monday, 19. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimediaprofessur

Referent:Prof. Dr. Karsten Morisse, Fachhochschule Osnabrueck
Titel:Verteilte Video-Annotation und personalisierte Fernsehdienste
Resümee:

Anhand zweier konkret durchgeführter Forschungsprojekte werden Fragestellungen und Lösungsansätze im vielfältigen Bereich der komplexen multimedialen Anwendungssysteme vorgestellt.

In Video-Produktionsumgebungen werden Werkzeuge zur Organisation und Unterstützung eines verteilten Produktionsprozesses immer wichtiger. Eine Klasse derartiger Werkzeuge sind Tools zur Auszeichnung oder Annotation von audiovisuellen Inhalten. Auszeichnungen können dabei sprachlich als Audioelement oder textuell/grafisch erfolgen. Wichtige Hilfsmittel in einem solchen Werkzeug sind Techniken zur automatischen Schnitterkennung, die inhaltsbasiert Szenenwechsel im Video identifizieren, oder die Möglichkeit einer integrierten Audio-Konferenz, um Auszüge von Gesprächen aufzunehmen und einer bestimmten Szene zuzuordnen. Ein möglicher Lösungsansatz wird im Rahmen des Vortrages präsentiert.

Im zweiten Teil geht es um die Entwicklung interaktiver und personalisierter Fernsehdienste auf Basis von Set-Top-Boxen. Grundlage eines solchen Ansatzes sind Matching-Algorithmen, die als Kern eines adaptiven Empfehlungsdienstes (Recommender System) entwickelt werden. Ein derartiger Empfehlungsdienst wird auf der Grundlage von Nutzerprofilen, dem beobachteten Mediennutzungsverhalten und durch bereitgestellte EPG-Metadaten entwickelt, so dass eine automatisierte Planung von Aufnahmen und deren Löschung auf der STB vorgenommen werden kann. In Kombination mit der Anbindung an soziale Netzwerke wie Twitter oder Facebook, über die Nutzerempfehlungen in einer Community ausgetauscht werden, kann damit eine Personalisierung des Massenmediums Fernsehens erreicht werden.


 

Monday, 19. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimediaprofessur

Referent:Prof. Dr. Juergen Sieck, Hochschule fuer Technik und Wirtschaft Berlin
Titel:Multimedia und drahtlose Kommunikation in Museen

 

Wednesday, 14. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimediaprofessur

Referent:Prof. Dr. Niels Pinkwart, Technische Universitaet Clausthal
Titel:Kooperatives Lernen und Arbeiten in multimedialen Umgebungen
Resümee:

Werden multimediale Anwendungssysteme für komplexe Aufgabenstellungen eingesetzt, so ist oft die Art und Weise der Mehrbenutzerunterstützung durch die Anwendung ein kritischer Erfolgsfaktor: je komplexer das Anwendungsgebiet, desto wichtiger ist typischerweise die Beteiligung und Zusammenarbeit mehrerer Benutzer. Gerade in universitären Anwendungskontexten - von der Lehre über die Verwaltung bis hin zu Forschung, Alumnimanagement, Öffentlichkeitsarbeit und der Pflege von Industriekontakten - spielen Kommunikation und Kooperation in heterogenen Formen eine zentrale Rolle und sollten daher durch eine moderne IT-Hochschulinfrastruktur unterstützt werden.

Die Art und Weise, in der multimediale Anwendungssysteme Kooperation unterstützen können und sollten, variiert dabei jedoch beträchtlich und hängt von einer Reihe von Faktoren ab. Im Vortrag werden an Hand dreier Fallbeispiele systemtechnische Realisierungsmöglichkeiten, algorithmische Entwurfsprinzipien, intelligente Unterstützungsmöglichkeiten und empirische Ergebnisse dazu vorgestellt, wie moderne Kooperationstechnologien in Anwendungssysteme integriert werden können und einen Mehrwert für die Benutzer bieten.

Die vorgestellten Beispiele reichen von der IT-Unterstützung für gemeinsame Modellierungs- und Simulationsaktivitäten über virtuelle 3D-Welten zur Teamarbeitsunterstützung bis hin zur Verwendung von Portal- und Hörsaaltechnologien zur effektiven Lernerunterstützung in der Hochschullehre.


 

Wednesday, 14. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimedia-Professur

Referent:Dr.-Ing. Ulrike Lucke, Universität Rostock
Titel:Moderne IT-Infrastrukturen für die Hochschule der Zukunft
Resümee:

Der Fortschritt von Informations- und Kommunikationstechnologien hat in den vergangenen Jahrzehnten zu Neuerungen in der Infrastruktur nicht nur unserer Hochschulen geführt. Beispielhaft seien multimediale Systeme, das Internet oder drahtlose Netze genannt. Auch Lernplattformen und Campus Management Systeme sind aus dem Hochschulalltag nicht mehr wegzudenken. Kontinuierlich finden neue Ergebnisse der aktuellen Forschung ihren Weg in die universitäre Praxis. Der Vortrag geht exemplarisch auf zwei besonders vielversprechende Entwicklungen ein:

  • Mit dem Pervasive Computing dringen intelligente Systeme unsichtbar in viele Lebensbereiche vor und unterstützen uns im Alltag. Forschung, Lehre und Verwaltung einer Hochschule können von individualisierten, pro-aktiv bereitgestellten Materialien oder von einer kontextabhängigen Ausrichtung der Arbeitsumgebung profitieren.
  • Mit einer Service-Orientierten Architektur lassen sich IT-Elemente auf vielfältige Weise in ein heterogenes Gesamtsystem fügen. Ausgehend von den Anforderungen einzelner Institutionen und Prozesse können wiederverwendbare Dienste angeboten werden. Dies beginnt auf den Notebooks der Studierenden und hört an den Grenzen einer Hochschule nicht auf.

Erst die Verbindung beider Lösungen entfaltet deren volles Potential. Dafür werden innovative Konzepte und ausgewählte Realisierungen vorgestellt. Das primäre Ziel derartiger Entwicklungen ist eine bessere Ausrichtung der IT-Infrastruktur auf die Bedürfnisse des Nutzers, verbunden mit einer Vereinfachung seiner Aktivitäten. Die Hochschule ist gerade deshalb ein lohnendes Anwendungsfeld für diese Forschungsarbeiten, weil sie uns aus der täglichen Arbeit eng vertraut ist und ihre Strukturen durch uns selbst zukunftsweisend gestaltbar sind.


 

Monday, 12. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimedia-Professur

Referent:Dr. Soeren Auer, Universität Leipzig
Titel:Towards the Linked Data Web
Resümee:

In the Internet age we face the challenge to efficiently support (multimedia) data, information and knowledge integration on the Web. For example, Web and multimedia applications have to efficiently handle information represented adhering to the RDF data model, deal with the implicit semantics encoded in ontologies and be able to semi-automatically interlink knowledge bases. In this talk we will give an overview on research approaches tackling these challenges (such as DL-Learner and Triplify) and applications (such as DBpedia and Semantic Wikis) aiming at enriching the current Web of documents with a Web of linked (multimedia) data.


 

Monday, 12. April 2010: Vortrag im Rahmen des Berufungsverfahrens zur Multimedia-Professur

Referent:Dr. Dirk Draheim, University of Innsbruck
Titel:Ubiquitous Computing - kein neues Paradigma. Aber Informatik pur!
Resümee:

Durchdringung aller Lebensbereiche mit Informations- und Kommunikationstechnologie. So oder ähnlich könnte eine ad hoc Definition von Ubiquitous Computing lauten. Haben wir aber derart nicht eigentlich schon immer die Wichtigkeit der Informatik in ihrer Rolle als Schlüsseldisziplin motiviert? Was ist also neu an Ubiquitous Computing?

Konzeptionell gesehen ist es eine Kombination aus offener Verteilung, Kontextsensitivität, integriertem HCI und künstlicher Intelligenz im Systementwurf. Konkreter gesagt ist aber sicherlich einfach der Einsatz aktuellster Kommunikationstechnologien und - komponenten (Sensoren/Aktoren/Medien). Es ist wichtig, dass die Informatik den Einsatz aktuellster Kommunikationstechnologien systematisch untersucht.

Mich interessiert dabei die Beherrschung der Informationsflut, die der Einsatz neuster Technologien bringt, und die Beherrschung der Komplexität der entstehenden Applikationen. In modernen Organisationen und Unternehmen sehen wir derzeit drei Managementfelder, nämlich Geschäftsprozessmanagement, Projektmanagement und Wissensmanagement. Die systematische wechselseitige Durchdringung dieser Managementfelder und der entsprechenden Tätigkeitsfelder unter Ausnutzung aktuellster Technologie - ich nenne es Ubiquitous Enterprise Computing - birgt ein großes Potential an Agilität, Flexibilität, Kreativität und Effektivität im Arbeitsleben.

Als Beispiele für dieses Prinzip gebe ich zwei aktuelle Forschungsprojekte, und zwar den Entwurf einer multi-agentenorientierten IT Service-Management-Plattform und den Entwurf einer vertikalen Modellintegration für den industriellen Fertigungsprozess.


 

Thursday, 03. December 2009: Vortrag im Rahmen des Seminars "Patente in der Digitaltechnik"

Referent:Dr. Th. Bittner, Patentanwalt der Kanzlei Boehmert & Boehmert, Berlin/Potsdam
Titel:Software-Patente - Patentschutz für computerimplementierte Erfindungen
Resümee:

Der Vortrag findet im Rahmen des Seminars "Patente in der Digitaltechnik" statt.

Gäste sind herzlich willkommen. Bitte melden Sie Ihre Teilnahme durch eine kurze mail an vortrag_bittner@cs.uni-potsdam.de an!


 

Monday, 26. October 2009: Vortrag im Rahmen der gemeinsamen Graduiertenschule DEDIS-Nano
mit der BTU Cottbus und dem IHP Frankfurt/Oder

Referent:Herr Prof. Chakrabarty, Duke University, Durham, USA
Titel:Delay-Fault Testing Techniques for Nanoscale Integrated Circuits: From Gross-Delay Defects to Small-Delay Defects

 

Thursday, 03. September 2009: Kolloquium

Referent:David Andrews, PhD, University of Arkansas
Titel:Hardware Microkernels for Heterogeneous Manycore Systems
Resümee:

The migration away from power-hungry, speculative execution processors towards manycore architectures is good news for the embedded and real-time systems community. Commodity platforms with large numbers of heterogeneous processors can be leveraged to meet the stringent real-time requirements of next-generation embedded systems. Although promising, the large numbers of heterogeneous cores that can bring about new levels of performance also bring with them new challenges for designers of real-time operating systems. Researchers are already conjecturing that the scalability and heterogeneity of manycores will result in the retirement of our existing monolithic operating system structure.

In this talk we first discuss some of the challenges that these manycore chips will present. We then discuss how hardware-based microkernels can provide the low latency, low jitter performance envelopes that are needed within real-time systems. We show how our hthreads hardware microkernel provides these characteristics for scalable numbers of threads and processors. Importantly the hthreads hardware microkernel provides ISA-neutral OS services, such as basic atomic operations, upon which higher-level programming models can be built.
Vita David Andrews


 

Friday, 10. July 2009: Gastvortrag zur LV Modellierung von Regeln und Regulierungen

Referent:Michael Fairweather, Oracle, London
Titel:Oracle Policy Automation: Demo and Discussion
Resümee:

Oracle Policy Automation is a suite of software tools for modeling and implementing rules and regulations. It was specifically developed for modeling legislation using natural language and has been used by many public agencies in Europe, North America and Australia to improve the quality, efficiency and transparency of social services. In his lecture, Michael Fairweather will provide an overview and demonstration the Oracle Policy Automation tools, along with some examples of some deployed applications.


 

Monday, 06. July 2009: Kolloquium

Referent:Shinnosuke Seki, The University of Western Ontario
Titel:An Extension of Fundamental Notions in Combinatorics on Words Inspired by DNA Information Encoding
Resümee:

DNA is a medium for organisms to store their genetic information and transmit the information to the next generation. Such information is encoded over an alphabet {A,C,G,T} of four kinds of nucleotide and stored in the form of double helix. The DNA double helix consists of two DNA strands with opposite orientation (called Watson strand and Crick strand), which are bonded according to the Watson-Crick complementarity A-T, C-G. In the course of DNA semiconservative replication, each of these strands serves as template for the reproduction of the complementary strand, resulting in two copies of the double helix. Thus we can say that Watson and Crick strands are "equivalent" with respect to the information they encode.

The antimorphic involution being a proper mathematical model of Watson-Crick complementarity, it seems valid to consider a word to be equivalent to its image under an arbitrary antimorphic involution ϑ. A number of interesting problems arise once this equivalence is taken into account. One representative is the weak defect effect, which asks whether a given system of word equations forces two words u, v to be in { t, ϑ(t) }* for some word t. This talk is mainly on two systems of equations with weak defect effect, which are extensions of the most well-known two results in combinatorics on words: i.e., the Fine and Wilf theorem and the Lyndon-Schützenberger equation.

Einladender: Prof.Dr.H.Jürgensen


 

Friday, 19. June 2009: Vortrag im Rahmenprogramm des Instituts für Informatik zum Hochschulinformationstag 2009

Referent:Prof. Dr. Helmut Jürgensen, Universität Potsdam und University of Western Ontario
Titel:Schwellen überwinden - Computer für Blinde
Resümee:

Information wird vorwiegend visuell vermittelt und bearbeitet; andere Sinne als der Gesichtssinn spielen bei der Informationsverarbeitung eine eher subsidiäre Rolle. Andererseits sind die menschlichen Fähigkeiten, die Sinne einzusetzen, sehr unterschiedlich. Wenn ein Sinn beeinträchtigt ist; muß Ersatz gefunden werden. Ist der Gesichtssinn geschädigt, werden Tast- und Gehörsinn als Ersatz verwendet.

Wir analysieren die besondere Situation Blinder bei der Benutzung von Computern: Standardanwendungen wie das Internet oder Textverarbeitungssysteme und selbst Bedienungsgeräte wie Maus oder Tastatur sind ohne visuelle Wahrnehmbarkeit nutzlos; der größte Teil der Computerperipherie ist nicht verwendbar. Es werden Sondergeräte, besondere Bedienungsmethoden und besondere Methoden der Informationsvermittlung benötigt, um Blinden angemessene Arbeitsbedingungen zu schaffen; analoges gilt für andere Arten von speziellen sensorischen oder motorischen Situationen.

An Beispielen zeigen wir den derzeitigen Stand der Forschung und Technik der computervermittelten Informationsverarbeitung für Blinde. Wir stellen eine allgemeines Konzept für den Entwurf von Computersystemen dar, welches die Einbeziehung der Charakteristiken von Benutzern zum Grundprinzip hat, um Schwellen gar nicht erst entstehen zu lassen.

Schlagwörter: Mensch-Maschine-Kommunikation, Kommunikation und Graphik für Blinde, haptische Informationsvermittlung, Gestik zur Computersteurung, multimodale Kommunikation


 

Friday, 29. May 2009: Kolloquium

Referent:Prof. Michael G. Hinchey, PhD, Co Director LERO International Science Centre, University of Limerick, Limerick (Ireland)
Titel:Evolving Critical Systems: A Research Agenda for Software Engineering
Resümee:

Der Vortragende kann wegen eines Softwarefehlers im Flugzeug leider nicht anreisen. Der Vortrag fällt aus.

Increasingly software can be considered to be critical, due to the business or other functionality which it supports. Upgrades or changes to such software are expensive and risky, primarily because the software has not been designed and built for ease of change. Expertise, tools and methodologies which support the design and implementation of software systems that evolve without risk (of failure or loss of quality) are essential. We address a research agenda for building software that (a) is highly reliable and (b) retains this reliability as it evolves, either over time or at run-time.

Portrait Prof. M. Hinchey

Mike Hinchey is Co-Director of Lero-the Irish Software Engineering Research Centre and Professor of Software Engineering at University of Limerick and will be presenting three seminars on what lies ahead for software engineering.

Prior to joining Lero, Dr. Hinchey was Director of the NASA Software Engineering Laboratory and continues to serve as a NASA Expert. Hinchey holds a B.Sc. in Computer Systems from University of Limerick, an M.Sc. in Computation from University of Oxford and a PhD in Computer Science from University of Cambridge. He is author/editor of several books on various aspects of Software Engineering, at various times Hinchey previously held positions as Professor in Australia, UK, Sweden and USA. He is currently Chair of the IFIP Technical Assembly and Chair of IFIP Technical Committee 1 (Foundations of Computer Science) as well as Editor-in-Chief of Innovations in Systems and Software Engineering: a NASA Journal (Springer).


 

Tuesday, 10. February 2009: Kolloquium

Referent:PD Dr. Hardi Hungar, OFFIS, Oldenburg
Titel:Safe-UML -- UML-Modellierung und Safety-Normen
Resümee:

Möchte man die UML in der Entwicklung sicherheitskritischer System einsetzen, müssen ihre Ausdrucksmittel unter dem sonst selten betrachteten Gesichtspunkt der Normkonformität neu bewertet werden. Dabei erweisen viele der Sprachmittel als unzureichend präzise, so dass sowohl eine Auswahl der verwendbaren Konstrukte wie auch eine Modifikation ihrer Bedeutung vonnöten sind.

Der Vortrag stellt zwei entsprechend zusammengestellte Varianten von UML vor. Safe-UML (S) - S für Spezifikation - ist eine Spezifikationssprache mit operationeller Semantik, die Regeln für die Verwendung von Klassen- und Zustandsdiagrammen setzt. Safe-UML(P) - P für Programmierung - geht darüber hinaus, indem eine spezielle Realisierung einer Programmierung in UML, nämlich die Generierung von Cpp-Programmen mithilfe von Rhapsody, betrachtet wird. Safe-UML(P) stellt weitere Bedingungen und beschreibt Maßnahmen, die erforderlich sind, um Anforderungen - etwa denen aus der Mü 8004 des Eisenbahnbundesamtes - an die Verwendung von Cpp-Programmen in sicherheitskritischen Systemen zu genügen.


 

Tuesday, 20. January 2009: Kolloquium des Lehrstuhls "Betriebssysteme und Verteilte Systeme"

Referent:Dr. Rolf Rabenseifner, High Performance Computing Center (HLRS), University of Stuttgart
Titel:Message Passing and Hybrid Parallelization on Clusters of Multi-Core SMP Nodes
Resümee:

In the future, most systems in high-performance computing (HPC) will have a hierarchical hardware design, e.g., a cluster of ccNUMA or shared memory nodes with each node having several multi-core CPUs. Parallel programming must combine the distributed memory parallelization on the node inter-connect with the shared memory parallelization inside each node. There are many mismatch problems between hybrid hardware topology and the hybrid or homogeneous parallel programming models on such hardware. Hybrid programming with a combination of MPI and OpenMP is often slower than pure MPI programming. There are also several opportunities where hybrid programming has significant advantages. The talk also addresses weaknesses of the current MPI and OpenMP standards on clusters of SMP nodes.

CV: Rolf Rabenseifner studied mathematics and physics at the University of Stuttgart. Since 1984, he has worked at the High-Performance Computing-Center Stuttgart (HLRS). In 1999 (Jan-April), he was an invited researcher at ZIH, Dresden. Currently, he is head of Parallel Computing - Training and Application Services at HLRS.

In his dissertation, he developed a controlled logical clock as global time for trace-based profiling of parallel and distributed applications. Since 1996, he has been a member of the MPI-2 Forum and since Dec. 2007, he is in the steering committee of the MPI-3 Forum. He is involved in MPI profiling and benchmarking, e.g., in the HPC Challenge Benchmark Suite. In recent projects, he studied parallel I/O, parallel programming models for clusters of SMP nodes, and optimization of MPI collective routines. In workshops and summer schools, he teaches parallel programming models in many universities and labs in Germany.
http://www.hlrs.de/people/rabenseifner/
http://www.hlrs.de/people/rabenseifner/publ/publications.html


 

Wednesday, 03. December 2008: PALIW 2008 Kolloquium

Referent:Prof. Friedemann Mattern, ETH Zürich
Titel:Auf dem Weg zum Internet der Dinge - Herausforderungen, Lösungsansätze und Anwendungen
Resümee:

Der informationstechnische Trend ist eindeutig: Prozessoren, Sensoren und drahtlose Kommunikationsmodule werden laufend kleiner und billiger. Zunehmend wird es daher möglich, IuK-Technologie in Alltagsgegenstände zu integrieren. Gewöhnliche Dinge können so ihre Umgebung erfassen, Daten untereinander austauschen und auf externe Informationsdienste zugreifen. Das Internet wird damit bis in die Alltagswelt hinein verlängert, es entsteht gewissermaßen ein "Internet der Dinge" mit sehr spannenden Anwendungsmöglichkeiten.

Im Vortrag werden nicht nur die Perspektiven sowie die wirtschaftlichen und gesellschaftlichen Konsequenzen dieser Entwicklung aufgezeigt, sondern es werden vor allem auch einige Forschungsprototypen der ETH Zürich vorgestellt, die das Potenzial der "Vernetzung aller Dinge" demonstrieren. Dazu gehören physische Produkte, die virtuelle Dienstleistungen mitbringen, smarte Edutainment-Umgebungen, kooperierende Alltagsdinge, die die Sicherheit des Nutzers erhöhen, neuartige Interaktionsmöglichkeiten mit intelligenten Objekten sowie Infrastrukturen, welche die Lokalisierung verlorener Gegenstände ermöglichen. In einem Ausblick spekulieren wir schließlich noch über die langfristigen Auswirkungen einer total vernetzten, von unsichtbaren Computern durchdrungenen Welt, in der der Mensch mehr denn je im Zentrum stehen soll.

see PALIW 2008 Kolloquium


 

Tuesday, 02. December 2008: PALIW 2008 Kolloquium

Referent:Prof. Dr. Peter Langendörfer, IHP und BTU Cottbus
Titel:A Lego Like Approach for Designing Sensor Nodes for Pervasive Systems
Resümee:

Wireless sensor networks are becoming more and more mature and will be used in a plethora of application areas ranging from Homeland security via automation control to telemedicine and ambient assisted living. The different and somewhat diverging requirements will not be satisfied by a single sensor node. This holds true for the hardware of such a sensor node as well as for its software.

Designing sensor nodes from scratch for each individual application is a tedious task. In order to tackle this challenge the TANDEM project develops a set of hardware and software modules which can be combined to a working system with reasonable effort. In this presentation different settings of sensor nodes for ambient assisted living will be presented. Ways to combine the hardware modules will be highlighted, and a tool for combining software modules will be introduced.

see PALIW 2008 Kolloquium


 

Tuesday, 24. June 2008: Gastvortrag der Professur "Betriebssysteme und Verteilte Systeme"

Referent:Prof. Glenn Luecke, Iowa State University
Titel:History and Current Trends in High Performance Computing
Resümee:

Glenn Luecke received his PhD from the California Institute of Technology and is currently Professor of Mathematics, adjunct Professor of Computer Engineering and Director of Iowa State University's High Performance Computing Group. For additional information, see his web site at http://grl.public.iastate.edu/.

This talk will present an overview of high performance computing technology being used today and how this technology has evolved since it inception in the 1970's. The revolutionary impact of high performance computing on scientific research, commercial engineering design and financial applications will also be discussed. Examples contrasting shared memory and distributed memory parallelization will also be presented.


 

Tuesday, 17. June 2008: Vortrag im Lehrstuhlkolloquium "Service und Software Engineering"

Referent:Prof. Barry Jay, University of Technology, Sydney, Australien
Titel:Programming with patterns
Resümee:

Why are there so many programming styles?

Pattern calculus provides a common foundation for the most popular programming styles, including functional, imperative, query-based and object-oriented styles, and also some new ones. This is being realised in the programming language bondi developed in Sydney.

This talk will use bondi to introduce pattern calculus, and illustrate its expressive power. The running example will be to solve the following problem. Update the salaries of all employees of an organisation by applying a completely generic function to parameters for the company, the representation of employees and the formula for updating their salaries.


 

Wednesday, 11. June 2008: Vortrag

Referent:Dr. Dagmar Krefting, Charité - Universitätsmedizin Berlin
Titel:MediGRID: Resourcenfusion für Medizin und Lebenswissenschaften
Resümee:

Viele Anwendungen aus der biomedizinischen Forschung können vom Grid profitieren. Auf der anderen Seite stellen medizinische - oder HealthGrids - besondere Ansprüche an Datenschutz und Usability.

Ziele und Ansätze des MediGrid, Erreichtes nach nun fast 3 Jahren Laufzeit des Projektes, sowie noch offene Probleme und Fragestellungen werden vorgestellt und können anschließend in offener Runde disktutiert werden.
Links: Dr. Krefting, MediGRID, Operating Systems & Distributed Systems, Uni Potsdam
Interessierte sind herzlich eingeladen!


 

Wednesday, 11. June 2008: Vortrag im Rahmen der Lehrveranstaltung "Service Oriented Architecture"

Referent:Dr. Charles Petrie, Standford University, CA, USA
Titel:Service based Process Synthesis
Resümee:

The concept of synthesis of a process by automatically composing web services has generated great interest in this century. As opposed to systems that attempt to generate general processes for a large class of cases, we experiment with the easier problem of dynamic automatic generation of a process instance. For each new goal, we generate a new process. This has not only the potential to generate new use cases to facilitate today's manual process programming, but also to become a revolutionary software engineering technique.

Our approach is to reuse last century configuration style planning technologies, as action interaction does not yet seem critical. We provide incremental replanning in order to account for service failure at execution time.

We do not address the semantic problems of discovery and unification, instead targeting single enterprise service communities where these problems have been solved by fiat. There remain significant semantic annotation and planning problems peculiar to web services: most notably, the propagation of instance data to web service input and output values while planning for pre and postcondition annotations, and the fundamental need for additional service annotations not usually considered.


 

Sunday, 11. May 2008: Vortrag im Lehrstuhlkolloquium "Service und Software Engineering"

Referent:Marsha Chechik, University of Toronto
Titel:Runtime Monitoring of Web Service Conversations
Resümee:

For a system of distributed processes, correctness can be ensured by (statically) checking whether their composition satisfies properties of interest. However, web services are distributed processes that dynamically discover properties of other web services. Since the overall system may not be available statically and since each business process is supposed to be relatively simple, we propose to use runtime monitoring of conversations between partners as a means of checking behavioural correctness of the entire web service system.

Specifically, we identify a subset of UML 2.0 Sequence Diagrams as a property specification language and show that it is sufficiently expressive for capturing safety and liveness properties. By transforming these diagrams to automata, we enable conformance checking of finite execution traces against the specification. We show how our language can be used to specify the Specification Property System (SPS).

We give an overview of an implementation of our approach as part of an industrial system and discuss our experience.


 

Wednesday, 02. April 2008: Vortrag im Lehrstuhlkolloquium "Service und Software Engineering"

Referent:Dr. Asuman Sünbül, SAP Research
Titel:Concurrency in Enterprise Systems
Resümee:

We explore the role of concurrency in enterprise systems, such as an SAP system, using a real world industry scenario.

Concurrency is an essential technology to make applications run much more efficiently and scaleably. In particular, the most promising technology to speed up and scale applications is their parallel execution on multi-core systems. In order to leverage these kinds of systems, concurrency must be introduced on different levels of the hard- and software stack. This applies in particular to *enterprise systems*, since it is not obvious how concurrency plays into the different aspects that are specific to enterprise systems.

We intend to examine the following aspects and evaluate possible solutions:

  • How does concurrency influence the design and realization of large-scale enterprise systems?
  • Can we provide an abstract language for developers, which makes applications concurrent, abstracting away thread management and allowing straightforward parallel programming? A language that will enable developers to specify parallelism far more conveniently than using raw threads, while improving performance, portability, and scalability.
  • In a more advanced step we can look into debugging, thread safety, mixing with other threading models.


 

Thursday, 14. February 2008: Kolloquium

Referent:Dr. Benno Stabernack, Fraunhofer Institut für Nachrichtentechnik
Titel:Processor Architectures for Multimedia Signal Processing
Resümee:

Mobile Endgeräte basieren z. Zt. auf Systemen (System on a Chip), deren Hauptfunktionalität durch den Einsatz entsprechender Software auf eingebetteten Prozessoren gebildet wird. Aufgrund der immer kürzeren Innovationszyklen kommt der softwarebasierten Umsetzung von Applikationen für eingebettete Systeme damit eine steigende Bedeutung zu. Im Bereich der mobilfunkgestützten Anwendungen sind in zunehmendem Maße auch Multimediaapplikationen vorzufinden, die bis vor kurzem noch leistungsfähigen Systemen, wie z.B. Desktop-PCs oder dedizierten Implementierungen in Form spezieller ASICs, vorbehalten waren. Hierzu zählen auch Codierungsverfahren, die auf entsprechenden Standards basierend, die echtzeitfähige Übertragung von Bewegtbilddaten unterstützen, wie z.B. Videotelefonie oder Broadcastdienste (DVB-H, DMB). Dem hohen Rechenleistungsbedarf echtzeitkritischer Multimediaapplikationen stehen hierbei jedoch die relativ leistungsschwachen Prozessoren eingebetteter Systeme gegenüber.

Um dem gestiegenen Rechenleistungsbedarf gerecht zu werden, stehen verschiedene Ansätze zur Verfügung. Neben der Steigerung der Taktfrequenz, die in der Regel auch eine Erhöhung der Verlustleistung nach sich zieht, bietet sich eine Erhöhung der spezifischen Rechenleistung des eingesetzten Prozessors an.

Mobile Endgeräte stehen dabei stellvertretend für eine immer weiter steigende Zahl von eingebetteten Systemen, wo eine hohe spezifische Rechenleistung gepaart mit der Flexibilität eines Prozessors erforderlich ist, wie z.B. auch im Automobilbereich und der Medizintechnik Der Vortrag befasst sich im Kern mit dem Entwurf anwendungsspezifischer Prozessoren für den Bereich der Bildsignalverarbeitung. Dabei wird auf die unterschiedlichen Architekturkonzepte, wie auch auf die algorithmischen Grundlagen der Bildsignalverarbeitung eingegangen.

Neben den architekturspezifischen Aspekten geht der Vortrag auch auf die entsprechende Unterstützung durch spezielle Multimedia Middleware, wie z.B. OpenMAX.AL und weitere typische Anwendungsgebiete für applikationsspezifische Prozessoren ein.


 

Thursday, 31. January 2008: Vortrag zur Vorlesung "Service Oriented Computing"

Referent:Peter Emmel, SAP AG
Titel:Definition, Modeling, Implementation, and Governance of Enterprise Services
Resümee:

The speaker will talk about how SAP service-enabled the SAP Business Suite by providing enterprise services that bring the most business benefits to customer. In the course of the presentation, the speaker covers the definition process and portfolio management of the enterprise services shipped by SAP (including how partners and customers can request and/or influence their definition), an anatomy of an enterprise service, and the rules and governance processes that SAP applies to model and implement enterprise services for the SAP Business Suite in order to achieve harmonized semantics and behavior of all enterprise services across the suite. A proposal outlining how customers and partners can apply these rules and processes rounds off this session.


 

Thursday, 17. January 2008: Vortrag zur Vorlesung "Service Oriented Computing"

Referent:Laura Bocchi, University of Leicester, UK
Titel:From BPEL to SRML: a Formal Transformational Approach
Resümee:

The SENSORIA Reference Modelling Language (SRML) provides primitives for modelling business processes in a technology agnostic way. At the core of SRML is the notion of module as a composition of tightly coupled components and loosely coupled, dynamically discovered services. I will present the state of the art of SRML and an encoding of BPEL processes into SRML modules using model transformation techniques. The encoding provides the means to create high-level declarative descriptions of BPEL processes that can be reused to build more complex modules, possibly including components implemented in other languages. The composition can be modelled and analysed as an ensemble, relying on the rich formal framework that is being developed within SENSORIA.


 

Wednesday, 24. October 2007: Kolloquium

Referent:Maia Hoeberechts, University of Western Ontario, London, Canada
Titel:A prototype system for adaptive music composition
Resümee:

The idea of creating an automatic music composition system has existed since the advent of the first electronic computers. Today, the newest systems perform what is known as adaptive composition, in which the character of the generated music can be changed on the fly according to user input or contextual information. Such systems are in increasing demand for use in diverse areas such as video game music generation, film score composition, and the development of interactive composition tools.

This talk will describe AMEE(TM) (Algorithmic Music Evolution Engine), a prototype system for adaptive music generation developed at the University of Western Ontario, in London, Canada. The features which distinguish AMEE(TM) from other composition systems are the use of a pipelined architecture in the generation process to allow a structured, yet flexible approach to composition, the inclusion of pattern libraries for storing and accessing musical elements, and the addition of an emotion mapper which allows music to be altered according to emotional characteristics.


 

Thursday, 19. July 2007: Kolloquium

Referent:Prof. Dr. Ernst-Rüdiger Olderog, Universität Oldenburg
Titel:Automatische Verifikation kombinierter Spezifikationen
Resümee:

Wir berichten über Forschungen im Projekt "Beyond Timed Automata" des Transregio-SFB "Automatic Verification and Analysis of Complex Systems" (AVACS), an dem die Universitäten Oldenburg, Freiburg und Saarbrücken beteiligt sind.

In diesem Projekt geht es darum, automatisch Sicherheitseigenschaften höherer System-Spezifikationen mit den Dimensionen Prozessverhalten, Daten und Realzeit nachzuweisen. Dabei liegt das Augenmerk darauf, Systeme mit unendlichen Datenbereichen und Realzeit-Bedingungen automatisch behandeln zu können und somit über die Möglichkeiten von Realzeitautomaten (Timed Automata) hinauszugehen. Als Spezifikationssprache wird CSP-OZ-DC betrachtet, eine Kombination von Konzepten aus Communicating Sequential Processes (CSP), Object-Z (OZ) und dem Duration Calculus (DC). Diese Kombination hat eine kompositionelle Semantik als Parallelkombination von Phasen-Event-Automaten, die sich sehr gut als Zwischendarstellung bei der Übersetzung von CSP-OZ-DC in die Eingabesprache eines Abstraction Refinement Model Checkers (ARMC) eignen. Mit ARMC lässt sich die Erreichbarkeit von Zustandsmengen automatisch überprüfen.

Wir illustrieren den Ansatz an Hand von zwei Fallstudien: einem parametrischen Fahrstuhl und einer Steuerung aus der Anwendungsdomäne von AVACS, dem European Train Control System (ETCS).


 

Thursday, 05. July 2007: Kolloquium

Referent:Dr. Thomas F. Gordon, Fraunhofer FOKUS
Titel:The Carneades Model of Argument and Burden of Proof
Resümee:

We present a formal, mathematical model of argument structure and evaluation, taking seriously the procedural and dialogical aspects of argumentation. The model applies proof standards to determine the acceptability of statements on an issue-by- issue basis. The model uses different types of premises (ordinary premises, assumptions and exceptions) and information about the dialectical status of statements (stated, questioned, accepted or rejected) to allow the burden of proof to be allocated to the proponent or the respondent, as appropriate, for each premise separately.

Our approach allows the burden of proof for a premise to be assigned to a different party than the one who has the burden of proving the conclusion of the argument, and also to change the burden of proof or applicable proof standard as the dialogue progresses from stage to stage. Useful for modeling legal dialogues, the burden of production and burden of persuasion can be handled separately, with a different responsible party and applicable proof standard for each. Carneades enables critical questions of argumentation schemes to be modeled as additional premises, using premise types to capture the varying effect on the burden of proof of different kinds of questions.


 

Wednesday, 27. June 2007: Vortrag zur Ringvorlesung "Webservices"

Referent:Dr. Charles Petrie, Univ. Stanford, CA, USA
Titel:The World Wide Wizard of Open Source Services
Resümee:

We envision a near-future in which people able now to browse the web in order to get information and run single web-based applications will also be able to instruct the web to make complex actions happen in the world. We call this functionality, which may seem like magic today, the "World Wide Wizard". It is in turn based upon the existence of open source services in which not only can anyone consume but can also provide (semantic) web services.

Further, we suggest that mere engineering rather than fundamental science is needed for the realization of this vision, so that it is really a near future vision. We suggest roles for industry and government to play in facilitating this future, motivated by economic benefits.

The Stanford Logic Group has a research project with SAP to create a prototype of pieces of the World Wide Wizard functionality and this is briefly described.


 

Thursday, 21. June 2007: Kolloquium

Referent:Dr. Armin Wolf, Fraunhofer-Institut für Rechnerarchitektur und Softwaretechnik FIRST, Berlin
Titel:Adaptive Constraint-Handling-Rules: Grundlagen, Implementierung, Anwendungen, Erweiterungen
Resümee:

Das Programmierparadigma "Constraint-Handling-Rules" (CHR) ist ein universeller regelbasierter Formalismus zur Beschreibung der Constraint-Verarbeitung auf einem hohen Abstraktionsniveau. Damit lassen sich insbesondere Constraint-Löser für unterschiedliche Domänen recht einfach realisieren, was durch vielfältige Anwendungen der CHR belegt ist.

Zu den zahlreichen Erweiterungen der CHR zählen adaptive CHR, die eine Anpassung von Regelableitungen bei beliebigen Änderungen der Ausgangssituation durch eine Begründungsverwaltung zulassen und damit bestens für reaktive Systeme in dynamischen Umgebungen geeignet sind. Darüber hinaus lassen sich aufgrund der Begründung der Ursachen von Inkonsistenzen "intelligente" Suchverfahren realisieren, die eine im Allgemeinen meist unvollständige Constraint- Verarbeitung (auch mit CHR) vervollständigen.

Neben den Grundlagen der adaptiven Constraint-Verarbeitung mit CHR wird das System DJCHR vorgestellt, das adaptive CHR in Java übersetzt und somit im einen objektorientierten Kontext nutzbar macht. Es wird gezeigt, dass damit Suchverfahren wie Conflict-Directed Backjumping, Dynamic Backtracking u.a. einfach implementierbar sind. Mit Hilfe dieser Implementierungen wird DJCHR mit einer anderen CHR-Implementierung anhand von SAT-Benchmark-Problemen verglichen. Weitere Anwendungen zeigen das große Potenzial der Adaption von CHR-Ableitungen bei praktischen Anwendungen wie bei der Personaleinsatzplanung aber auch bei der Umsetzung lokaler Suchverfahren wie das Simulated Annealing. Abschließend werden aktuelle Forschungsarbeiten zur Verschmelzung adaptiver und disjunktiver CHR vorgestellt. Erstes Ergebnis ist eine operationale Semantik für disjunktive CHR, die Conflict-Directed Backjumping auf Basis adaptiver CHR nutzt, um die Suche nach erfolgreichen Ableitungen zu steuern.


 

Wednesday, 20. June 2007: Vortrag zur Ringvorlesung "Webservices"

Referent:Prof. Thomas Magedanz und Niklas Blum, TU Berlin und Leiter CC NGNI Fraunhofer Institut FOKUS /
Stellvertretender Leiter CC NGNI
Titel:Evolution von Telekomdienstplattformen in Hinblick auf Netzkonvergenz und SOA Prinzipien - Ein Deja Vu?
Resümee:

Im Rahmen dieses Gastvortrages soll die Evolution von Telekommunikationsdienstplattformen in den letzten 30 Jahren beleuchtet werden. Dabei soll insbesondere die Dienstorientierung in der Telekommunikationswelt genauer betrachtet werden. Ausgehend von dem Konzept der Intelligenten Netze aus den achtziger Jahren, werden object-orientierte Application Programming Interface (API) Plattformen, wie beispielsweise die JAIN, Parlay und Open Service Architecture APIs betrachtet, die in den neunziger Jahren an Bedeutung gewonnen haben. Die Ende der Neunziger Jahre einsetzende Etablierung von Web Service Technologien im Telekommunikationsumfeld, insbesondere die Parlay X APIs werden ebenfalls reflektiert.

Im Zentrum des Vortrags steht jedoch eine Einführung des IP Multmediasystems (IMS), das derzeit von vielen Standardisierungsgremien als Dienstplattform für beliebige Multimedia Kommunikations und Informationsdienste ueber konvergierende Netze angesehen wird. Dieses maßgeblich auf IP Protokollen basierende System erlaubt dabei die synergetische Einbindung der vorgenannten Dienstplattformen. Im Vortrag wird nach der Vorstellung der IMS Architektur und Prinzipien insbesondere die Realisierung von IMS Diensten auf der Basis von SOA Prinzipien und sogenannten IMS Enablern betrachtet.

Ein abschliessender Ausblick auf das mögliche Zusammenspiel von IMS und Web 2.0 Diensten soll zukünftige Forschungsaspekte aufzeigen.


 

Wednesday, 30. May 2007: Vortrag zur Ringvorlesung "Webservices"

Referent:Prof. Jakob Rehof, Universität Dortmund und Direktor Fraunhofer ISST
Titel:Conformance Checking for Web Services

 

Thursday, 26. April 2007:
Seminar "Datenkompression für Test und Diagnose" der AG Fehlertolerantes Rechnen

Referent:Dipl. Ing. U. Bass, ZAB Brainshell
Titel:Wie patentiere ich selbst

 

Thursday, 26. April 2007: Vortrag zur Ringvorlesung "Webservices"

Referent:Prof. Bernhard Steffen, Lehrstuhl für Programmiersysteme - Universität Dortmund
Titel:Was sind eigentlich Services?

 

Thursday, 16. November 2006: Kolloquium

Referent:Dr. Markus Holzer, TU München
Titel:Finding Lower Bounds for Nondeterministic State Complexity is Hard
Resümee:

We investigate the following lower bound methods for regular languages: The fooling set technique, the extended fooling set technique, and the biclique edge cover technique. It is shown that the maximal attainable lower bound for each of the above mentioned techniques can be algorithmically deduced from a canonical finite graph, the so called dependency graph of a regular language. This graph is very helpful when comparing the techniques with each other and with nondeterministic state complexity. In most cases it is shown that for any two techniques the gap between the best bounds can be arbitrarily large. The only exception is the biclique edge cover technique which is always as good as the logarithm of the deterministic or nondeterministic state complexity. Moreover, we show that deciding whether a certain lower bound w.r.t. one of the investigated techniques can be achieved is in most cases computationally hard, i.e., PSPACE-complete and hence are as hard as minimizing nondeterministic finite automata. This is a joint work with H. Gruber (LMU München).


 

Friday, 20. October 2006: Kolloquium

Referent:M. Hoeberechts, University of Western Ontario, Kanada
Titel:Some Thoughts on the Definition of Computability

 

Thursday, 19. October 2006: Kolloquium

Referent:Prof. Dr. C. Calude, University of Auckland, Neuseeland
Titel:Natural Complexity, Partial Randomness and Zeta Functions
Resümee:

We introduce the zeta number, natural halting probability and natural complexity of a Turing machine and we relate them to Chaitin’s Omega number, halting probability, and program-size complexity. A classification of Turing machines according to their zeta numbers is proposed: divergent, convergent and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on (algorithmic) randomness and partial randomness are proved. For example, we show that the zeta number of a universal tuatara machine is computably enumerable and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness—which cannot be naturally characterised in terms of plain complexity—various types of partial randomness admit such characterisations.


 

Monday, 04. September 2006: Wissenschaftliches Kolloquium

Referent:Dr. Dominik Stoffel, Universität Stuttgart
Titel:Formale Verifikation von System-on-Chip-Entwürfen
Resümee:

Heutige Systems-on-Chip (SoCs) sind aus einer Vielzahl von oft hoch komplexen, nebenläufig arbeitenden Komponenten zusammengesetzt, die miteinander über leistungsfähige Kommuni-kationsstrukturen vernetzt sind. Der Entwurf solcher SoCs ist trotz des inzwischen hohen Automatisierungsgrades sehr teuer. Den größten Anteil an den Entwurfskosten stellen mit 60 bis 80 Prozent die Kosten für die Verifikation dar.

In diesem Vortrag geben wir zunächst einen Überblick über die im industriellen Alltag einge-setzten Methoden und Verfahren zur Verifikation von System-on-Chip-Entwürfen. Neben den klassischen Verifikationsverfahren basierend auf Simulation kommen immer stärker formale Verifikationstechniken zum Einsatz. Wir diskutieren Stärken und Schwächen dieser Verfahren und vergleichen sie mit den herkömmlichen Ansätzen hinsichtlich Qualität und Produktivität.

Auf Block- oder Modulebene sind formale Techniken heutzutage bereits sehr leistungsfähig. Die Weiterentwicklung dieser viel versprechenden Technologie auch für die Systemintegra-tion ist Gegenstand intensiver internationaler Forschung. Wir stellen ein neues, von uns ent-wickeltes Verfahren für die Verifikation der Kommunikationsschnittstellen zwischen den Systemkomponenten vor. Das Verfahren basiert auf einer partitionierten Automatentraver-sierung. Die Partitionierung orientiert sich an der Schaltungsstruktur der Kommunikations-schnittstelle und erlaubt es, effizient Informationen über die Erreichbarkeit von Systemzu-ständen zu berechnen. Wir erklären, warum die gewählte Art der Partitionierung geeigneter ist als bisherige Techniken und berichten von der erfolgreichen Anwendung des Verfahrens auf komplexe SoC-Entwürfe, die bei unseren Forschungspartnern in der Industrie entwickelt werden.


 

Monday, 04. September 2006: Wissenschaftliches Kolloquium

Referent:Prof. Alex Orailoglu, University of California, San Diego, USA
Titel:Effective Self-Test for State-of-the-art VLSI Designs
Resümee:

Design for test methodologies, particularly Built-in Self-test (BIST), are playing an increasingly significant role in managing the test cost of current designs. To reap the significant cost reduction benefits of BIST in test generation and test application, possible deterioration in terms of fault coverage levels and diagnostic capabilities, due to random resistant faults and limited response information, needs to be averted.

The talk is composed of two major components. On the fault diagnosis side, efficient fault diagnosis approaches are proposed for scan-based BIST designs. Improvements in information extraction from the BIST signature are attained through utilization of both superior deterministic partitioning schemes and enhanced analysis procedures. The talk continues with an investigation of concurrent test for linear digital systems. A low-cost, accumulation based concurrent error detection scheme provides considerable benefits through observation of the average behavior of the system and through careful gate level fault effect consideration. The significant benefits provided by the techniques proposed are attained at negligible hardware costs, ensuring the continued dominance of on-chip test techniques for state-of-the-art VLSI designs.


 

Wednesday, 28. June 2006: Kolloquium

Referent:Dexter Kozen, Joseph Newton Pew, Jr. Professor in Engineering, Department of Computer Science, Cornell University
Titel:Coinductive Proof Principles for Stochastic Processes
Resümee:

Coinduction (or "baseless induction") has been shown to be a useful tool in functional programming. Streams, automata, concurrent and stochastic processes, and recursive types have been successfully analyzed using coinductive methods.

Most approaches emphasize the relationship between coinduction and bisimulation. There is a coinduction principle that states that under certain conditions, two bisimilar processes must be equal. For example, to prove the equality of infinite streams

s=merge(split(s)),
where merge and split satisfy the familiar coinductive definitions

merge(a::s,t) = a::merge(t,s)
#1(split(a::b::r)) = a::#1(split(r))
#2(split(a::b::r)) = b::#2(split(r)),

it suffices to show that the two streams are bisimilar. An alternative view is that certain systems of recursive equations over a certain algebraic structure have unique solutions.

Desharnais et al. (2002,2004) study bisimulation in a probabilistic context. They are primarily interested in the approximation of one process with another. Again, they focus on bisimulation, but do not formulate an explicit coinduction rule.

In this talk I will describe an explicit coinduction principle for recursively-defined stochastic processes and dynamical systems. I will illustrate the use of the rule in deriving some properties of a simple coin-flip process.


 

Friday, 02. June 2006:
Kolloquium der Arbeitsgruppe Fehlertolerantes Rechnen, Gäste sind herzlich willkommen

Referent:Dr.-Ing. Armin Zimmermann, Hasso-Plattner-Institut für IT Systems Engineering
(vorher TU Berlin, Institut für Technische Informatik und Mikroelektronik)
Titel:Modellierung und Untersuchung Stochastischer Ereignisdiskreter Systeme
Resümee:

Das Verhalten vieler technischer Systeme lässt sich durch diskrete Zustände sowie Übergänge zwischen ihnen beschreiben. Fragen der Leistungsfähigkeit und Zuverlässigkeit können mit Hilfe eines entsprechenden stochastischen ereignisdiskreten Modells effizient beantwortet werden.

Der Vortrag gibt einen Überblick über verschiedene Arbeiten im Bereich des modellbasierten Entwurfs diskreter Systeme sowie der Umsetzung der Forschungsergebnisse im Softwarewerkzeug TimeNET. Dazu gehören neben verschiedenen Petri-Netz-Klassen quantitative Bewertungsverfahren für Modelle mit großem Zustandsraum, effiziente Simulationsmethoden für komplexe Modelle und solche mit seltenen Ereignissen, sowie ein Optimierungsverfahren und eine modellbasierte Steuerungsmethode.

Die Anwendung der Verfahren wird an industriellen Beispielen aus dem Bereich der Technischen Informatik dargestellt. Außerdem wird ein Ausblick auf zukünftige Forschungsarbeiten gegeben.


 

Thursday, 18. May 2006: Kolloquium

Referent:Prof. Erik Larsson, Universitaet Linkoping, Schweden, Gast der Arbeitsgruppe Fehlertolerantes Rechnen
Titel:Test Preparation and Application for System Chips
Resümee:

Technology development has made it possible to design and manufacture Integrated circuits (ICs) where a complete system is placed on a single chip; so called system chip. The complex manufacturing process makes system chip highly vulnerable to faults and testing is required to ensure the manufacturing of fault-free ICs. However, the test cost is a major and increasing part of the manufacturing cost. The ITRS 2001 predicts that for some products "test may account for more than 70% of the total manufacturing cost - test cost does not directly scale with transistor count, dies size, device pin count, or process technology". In order to keep test cost minimal, the testing process must be considered both test preparation as well as during test application. It is important to make sure that a test scheme handles the high test data volume and allows flexibility to adjust the testing during test application.

This talk will give an overview of research activities at test preparation and test application for system chip, and the focus will be on a flexible test architecture to integrate test data compression and abort-on-fail testing.


 

Thursday, 17. November 2005: Kolloquium

Referent:Dr. Dominik Stoffel, Universität Kaiserslautern
Titel:Partitionierte Automatentraversierung für Anwendungen in der Systemintegration
Resümee:

Die Kosten für den Entwurf komplexer informationsverarbeitender Systeme sind trotz weitgehender Automatisierung sehr hoch. Den größten Anteil an den Entwurfskosten eines System-on-Chip (SoC) oder eines eingebetteten Systems stellen heute mit 60 bis 80 Prozent die Kosten für die Verifikation dar. Klassische Verifikationsverfahren wie Simulation können bei Systemen heutiger Größe nicht mehr die erforderliche Qualität liefern. Formale Verifikationstechniken leisten bereits viel, stoßen aber in verschiedenen Bereichen ebenfalls an ihre Grenzen. Dies gilt insbesondere, wenn die Korrektheit der Strukturen zur Systemintegration geprüft werden soll.

In diesem Vortrag behandeln wir das Problem, Kommunikationsschnittstellen zwischen den Modulen eines Systems formal zu verifizieren. Implementierungen von Kommunikationsprotokollen enthalten oft mehrere Tausend Zustandsvariable, die astronomisch große Zustandsräume aufspannen. Mit klassischen Methoden der formalen Verifikation wie etwa symbolischer Automatentraversierung lassen sich diese Zustandsräume nicht mehr behandeln.

In diesem Vortrag stellen wir ein neues Verfahren zur Traversierung endlicher Automaten dar, das auf die Verifikation solcher Kommunikationsblöcke zugeschnitten ist. Ein wesentliches Merkmal der Struktur dieser Systeme ist, dass sie häufig ein zentrales Haupt-Steuerwerk (engl.: "main finite state machine") enthalten, das mit den übrigen Steuerwerken kommuniziert. Die Kenntnis dieser Struktur erlaubt es, ein Verfahren für eine partitionierte Automatentraversierung zu formulieren, die den Gesamtzustandsraum anhand der Zustandsübergänge des Haupt-Steuerwerkes zerlegt. In diesem Vortrag erklären wir, warum diese Art der Partitionierung erfolgreicher ist als bisherige Techniken und berichten von der erfolgreichen Anwendung der neuen Technik auf komplexe SoC-Entwürfe, die bei unseren Forschungspartnern in der Industrie entwickelt werden.


 

Monday, 11. July 2005: Kolloquium

Referent:Prof. Dr.-Ing. E. Mähle, Institut für Technische Informatik, Universität zu Lübeck
Titel:Paralleles Rechnen mit rekonfigurierbarer Hardware: Nische oder Megatrend?
Resümee:

Rekonfigurierbare Hardware, insbesondere in Form von FPGAs (Field Programmable Gate Arrays), wird schon seit mehr als einem Jahrzehnt erfolgreich für Spezialanwendungen, als Ersatz für niedrig integrierte Zusatzhardware oder zum Rapid Prototyping eingesetzt, fristete aber aus Sicht des parallelen Rechnens bisher eher ein Nischendasein. Die neue Generation rekonfigurierbarer Chips erreicht freilich sowohl Taktraten als auch Gatterdichten, die sie für paralleles Hochleistungsrechnen so attraktiv werden lassen, dass man von einem neuen Trend sprechen kann. Es existieren auch bereits Hardcores und Softcores für Prozessoren sowie IP(Intellectual Property)-Cores für zahlreiche rechenintensive Anwendungen, aus denen sich komplette SoCs (System on Chip) aufbauen lassen. Eine weitere neuartige Eigenschaft ist die Fähigkeit zur partiellen dynamischen Rekonfiguration, d. h. das Chip kann zur Laufzeit teilweise neu konfiguriert werden, während der Rest weiterarbeitet.

Der Vortrag gibt zunächst einen Überblick über die aktuellen Ansätze für rekonfigurierbare Hardware sowie die zugehörigen Entwicklungsumgebungen für parallele Anwendungen. Exemplarisch wird das Lübecker Projekt DynaCORE näher vorgestellt, das die Entwicklung eines dynamisch rekonfigurierbaren Coprozessors für Netzwerkprozessoren zum Ziel hat.


 

Thursday, 16. June 2005: Forschungs-Kolloquium

Referent:Prof. Dr. Katrin Tent, Universität Bielefeld
Titel:Stabile pseudoendliche Gruppen
Resümee:

Pseudoendliche Strukturen können als asymptotische Klassen von endlichen Strukturen betrachtet werden. In diesem Vortrag werde ich einige Beispiele pseudoendlicher Strukturen geben und erklären, warum stabile pseudoendliche Gruppen eine auflösbare Untergruppe von endlichem Index haben.


 

Monday, 05. April 2004: Kolloquium

Referent:Bettina Sunckel, Johann Wolfgang Goethe-Universität, Frankfurt am Main
Titel:Metalineare CD Grammatiksysteme
Resümee:

Der zentrale Punkt in der klassischen Theorie der formalen Sprachen ist die Erzeugung von Sprachen durch Grammatiken oder Automaten. In der Informatik beschäftigt man sich heute aber immer häufiger mit komplexen verteilten Systemen, deren Komponenten auf verschiedene Art und Weise miteinander kooperieren. Verteilte Systeme werden auch von der Psychologie zur Beschreibung von Problemlösungsstrategien und von der Linguistik betrachtet. Die Tatasache, daß die Theorie der formale Sprachen alle erwähnten Themengebiete berührt führte zur Definition von Grammatiksystemen. Ein Grammatiksystem besteht aus mehereren Grammatiken, die nach bestimmten Regeln zusammenarbeiten. Hauptsächlich unterscheidet man dabei zwischen sequentieller und paralleler Kooperation.

In diesem Vortrag werden kontextfreie cooperating distributed (CD) Grammatiksysteme, das Modell mit sequentieller Kooperation, vorgestellt. Ein kontextfreies CD Grammatiksystem besteht aus mehreren kontextfreien Grammatiken, den Komponenten. Der Ableitungsmodus bestimmt, wie die Komponenten zusammenarbeiten. Dieses Modell wird unterformalsprachlichen Aspekten wie generative Mächtigkeit, die Einordnung in der Chomsky-Hierarchie und Beschreibungskomplexität betrachtet.

Im zweiten Teil des Vortrags werden kontextfreie CD Grammatiksysteme in der Form der Produktionen beschränkt wie metalinearen Grammatiken. Metalineare CD Grammatiksysteme zeichnen sich dadurch aus, daß sie leichter zu handhaben sind als das uneingeschränkte Modell. Auch hier werden formalsprachliche Aspekte behandelt.


 

Thursday, 20. November 2003: Kolloquium

Referent:Dr. Adi Palm, Universität Passau
Titel:Parsing mit modalen Baumlogiken für natürliche Sprachen
Resümee:

Den Ausgangspunkt dieses Vortrages bildet die so genannte modelltheoretische Syntax, bei der syntaktische Strukturen von natürlichen Sprachen mit Hilfe logischer Formeln charakterisiert werden. Die Modelle dieser Formeln entsprechen dann den wohlgeformten Syntaxbäumen einer natürlichen Sprache, d.h. diese Formeln repräsentieren die Grammatik dieser Sprache. Damit lassen sich mit vergleichsweise einfachen Formeln komplexe, nichttriviale Fragmente einer natürlichen Sprache beschreiben, andererseits ermöglicht dies eine formale Charakterisierung typischer struktureller Eigenschaften.

Leider machen modelltheoretische Beschreibungen in der Regel keine Aussagen über operationelle Aspekte, insbesondere darüber, wie sich für eine gegebene Phrase eine passende syntaktische Struktur ermitteln lässt, die gleichzeitig Modell der grammatikalischen Beschreibung ist. In diesem Vortrag soll deshalb zum einen motiviert werden, warum gerade modale Baumlogiken eine sinnvolle formale Basis für die logische Beschreibung von Syntaxbäumen bilden, und zum anderen, wie diese Formeln zum Aufbau von Strukturen während des Parsens eines Eingabesatzes verwendet werden können. Das Kernstück bildet ein Tableau-basiertes Konstruktionsverfahren für Baummodelle, das mit einem Earley-Parser für kontextfreie Grammatiken kombiniert wird. Weiterhin stellen wir einige Erweiterungen vor, die bestimmte syntaktische Besonderheiten von natürlichen Sprachen berücksichtigen, um die Komplexität des vorgestellten Verfahrens zu verbessern.


 

Wednesday, 10. September 2003: Kolloquium

Referent:Dr. Michael Gruninger, University of Maryland and National Institute for Standards and Technology
Titel:The Process Specification Language: Around the World in 80 Axioms
Resümee:

The Process Specification Language has been designed to facilitate correct and complete exchange of process information among manufacturing systems, including scheduling, process modeling, process planning, production planning, simulation, project management, workflow, and business process reengineering.

This talk will give an overview of the first-order theories within the PSL Ontology and discuss some of the design principles used to construct the ontology.


 

Thursday, 19. June 2003: Kolloquium

Referent:Dirk Draheim, Institut für Informatik, Freie Universität Berlin
Titel:Das Software-Projekt im Hochschulunterricht - Lernziele, Einflußgrößen, Vorschläge
Resümee:

Software-Projekte bzw. Software-Praktika haben einen festen Platz sowohl im Grundstudium als auch im Hauptstudium der Informatik. Studentische Software-Projekte haben andere Ziele und andere Einflußgrößen als professionelle Software-Projekte. Der zentrale Erfolgsfaktor einer professionellen Software-Entwicklung ist ein konsequent produktorientiertes Risiko-Management. Dabei sind die zu betrachtenden Faktoren Produktqualität, Produktquantität, Zeit und Kosten.

Es ist wichtig, daß ein studentisches Software-Projekt zunächst frei ist von den daraus resultierenden Streßfaktoren Qualitätsdruck, Quantitätsdruck, Zeitdruck und Kostendruck. Alleiniges Ziel ist die Maximierung des Lernerfolgs. Dabei gibt es in der Ausbildung Erwachsener spezifische Risiken und Chancen. Allerdings wird in studentischen Software-Projekten üblicherweise in unterschiedlichem Grad versucht, möglichst realistische Projektbedingungen zu simulieren. Das ist auch erst einmal plausibel, erfüllt doch ein Softwarepraktikum im Rahmen eines Informatik-Curriculums typischerweise den Zweck, die Teilnehmer mit den Problemen in realistischen Projekten und deren Lösungsansätzen vertraut zu machen.

Mit dem Software-Prozeß EASE (Education for Actual Software Engineering) wird hingegen die These vertreten, daß es sich lohnt, einen Software-Prozeß vorzuschlagen, der auf die Eindämmung der speziellen Risiken in der Ausbildung Erwachsener zielt und deren spezielle Chancen nutzt, selbst wenn die dabei resultierenden Konzepte aus professioneller Sichtweise kontraproduktiv sein sollten. Die EASE-Konzepte sollen das Erwerben funktionaler Qualifikationen auf hohem Niveau und das Erwerben extrafunktionaler Qualifikationen fördern. EASE ist ein leichtgewichtiger, stark iterativer Software-Prozeß, der Konzepte ausgereifter Lernmethoden aufgreift und mit aktuellen Projektmanagement-Konzepten und eigenen Konzepten kombiniert. EASE beabsichtigt, Gruppenarbeit, gemeinschaftliches Lernen und Selbstorganisation zu fördern.


 

Wednesday, 18. June 2003: Kolloquium

Referent:Dieter Engbring, Universität Paderborn
Titel:Informatik im Kontext. Ein Zugang für die fächerübergreifende Lehre in der Informatik
Resümee:

Für die Informatik ist der Bezug auf den gesellschaftlichen Kontext von entscheidender Bedeutung, um brauchbare und vor allem qualitativ gute Produkte herzustellen. Um dieses Ziel zu erreichen, ist es aber nicht ausreichend, lediglich den Kontext der Informatik zu analysieren (dies ist gängige Praxis im Bereich Informatik und Gesellschaft). Es müssen Konsequenzen für die Gestaltung von Informatiksystemen erkennbar werden. Dies nenne ich Informatik im Kontext.

Die Verbindung von Informatik im Kontext und Kontext der Informatik und damit die Verbindung von Gestaltungs- und Wirkungsforschung haben wir im Projekt Kontextuelle Informatik etabliert. Ich kann zudem zeigen, dass der Zugang der Kontextuellen Informatik geeignet ist, eine Verbindung von Kerninformatik und Angewandter Informatik zu erhalten. Dabei möchte ich vor allem die Frage diskutieren, ob dies auch ein Zugang für die Informatische Bildung sein kann.


 

Tuesday, 17. June 2003: Kolloquium

Referent:Maurice Pagnucco, School of Computer Science and Engineering, The University of New South Wales, Australia
Titel:Causality and minimal change in reasoning about action
Resümee:

Many traditional approaches to reasoning about action and change can be characterised by placing states in a preferential ordering. The potential states after performing an action are predicted to be those satisfying the postconditions of the action that are minimal in this ordering. This is often referred to as preferential entailment and gives rise to a number of solutions to the frame and ramification problems.

Recent literature in this area has seen the appearance of a number of logic-based approaches that employ an explicit notion of causality. In a number of these, the role of causality has been promoted as necessary for solving the frame and ramification problems as well as permitting concise solutions to these problems. However, this has only been demonstrated through representative examples. We attempt to investigate what, if anything, an explicit notion of causality provides. We focus in particular on the causal theory due to McCain and Turner (IJCAI'1995).


 

Friday, 06. June 2003: Kolloquium

Referent:Prof. Dr. Thomas Eiter, Technische Universität Wien, Österreich
Titel:Planen durch Answer Set Programmierung: Das DLV^K System
Resümee:

Planen hat in der Künstlichen Intelligenz seit jeher grosse Beachtung gefunden, und zu dieser Problemstellung sind ueber die letzten Jahrzehnte kontinuierlich neue Beiträge geleistet worden. Logik-basierte Planungsansätze haben dabei von den Anfängen weg eine besondere Rolle gespielt. Das Interesse an logik-basierten Methoden zur Plangenerierung hat insbesonders durch gute Erfolge bei der Transformation in logische Erfüllbarkeitsprobleme zugenommen, die vor einigen Jahren erzielt worden sind.

Dadurch ermutigt sind in der letzten Zeit wiederholt Vorschläge präsentiert worden, wie Planungsprobleme durch die sogenannte Answer Set Programmierung, die ein Zweig der nichtmonotonen logischen Programmierung ist, deklarativ formuliert und gelöst werden können. In Weiterverfolgung dieser Idee, nach der Pläne als Modelle eines logischen Programms generiert werden, ist das Planungssystem DLV^K entwickelt worden. Dieses erlaubt in der genuinen Planungssprache K eine regel-basierte Beschreibung des Planungsproblems unter Zuhilfenenahme von Default-Negation und bietet Möglichkeiten wie parallele Aktionsausführung, nichtdeterministische Effekte der Aktionen und die Berechnung optimaler Pläne. Damit lassen sich auch teils vertrackte Planungsprobleme verhältnismässig einfach erfassen und lösen.

Neben dem prinzipiellen Systemansatz, der auf Answer Set Programmierung aufbaut, werden Beispiele und einige Resultate vorgestellt, die im Rahmen des Forschungsprojekts zur Systementwicklung erzielt worden sind.


 

Tuesday, 03. June 2003: Kolloquium

Referent:Dr. Anatoli Strigin, Zentrum für allgemeine Sprachwissenschaft, Typologie und Universalienforschung
Titel:Genetische Algorithmen und die abduktive Bedeutungstheorie
Resümee:

Genetic algorithms are a species of stochastic algorithms, i. e. algorithms which make use of probability concepts. Genetic algorithms are modeled on our conceptions of evolution in nature.They let a population of possible candidate solutions to some problem evolve in the direction of better solutions. Abductive reasoning is a kind of hypothetical reasoning, encompassing also reasoning by default. For some time there has been linguistic research going on which assumes that understanding utterances employs hypothetical reasoning.

Two major difficulties with which this research direction is confronted are:

  • it is not clear that abductive reasoning is a good candidate for computing meanings. Understanding is fast, abduction is computationally complex in the general case, and therefore as a rule slow, if possible at all;
  • it is not clear how abductive theories are learned which are postulated to be used in interpreting an utterance. Such theories are never directly connected with the outer world (they mostly consist of ``hidden'' predicates which have no obvious extensions like ``bird'' or ``word'').

Genetic algorithms could escape the first difficulty, since they can provide a solution at any time, although it could be not the unique or the best solution in absolute terms.

They could also be of use in learning theories with hidden predicates, if applied to classifier systems.

The talk will illustrate the two uses of genetic algorithms and sketch their potential application areas in a theory of abductive utterance interpretation.


 

Thursday, 24. April 2003: Kolloquium

Referent:Prof. Marc Denecker, Department of Computer Science,
K.U.Leuven and Département d'Informatique, U.L.Bruxelles
Titel:Nonmonotone inductive definitions: the logic underlying Logic Programming
Resümee:

Logic programming has been introduced as programming in the Horn clause subset of first order logic. This view breaks down for the negation as failure inference rule. In this seminar, we investigate an alternative declarative reading of logic programming. It is well-known that Horn Logic Programming is suitable for representing positive inductive definitions. In fact, many prototypical Prolog programs (member, append, ..) are simple inductive definitions. The question is whether this view can be extended to the case of recursive logic programs with negation. A problem here is that currently, there is no standard universally accepted theory of non-monotone induction in mathematical logic.

I will discuss two different forms of non-monotone induction and argue that the well-founded semantics of logic programming correspond to one of these, namely iterated induction. I will compare logic programming under the well-founded semantics with an existing logic of iterated induction and argue that the first provides a superior formalisation of iterated induction. So, this study provides new insight on the declarative reading of logic programming, and it provides also new insight in the nature of inductive definitions.


 

Thursday, 30. January 2003: Kolloquium

Referent:Ludger Humbert, Uni Dortmund
Titel:Das Modulkonzept als wissenschaftlich fundierte Grundlage für die Schulinformatik
Resümee:

Mit dem Modulkonzept wird eine Grundlage für die Schulinformatik vorgestellt und einer mehrdimensionalen Evaluation unterzogen. Das Konzept stellt einen konstruktiven Vorschlag für den Informatikunterricht für die allgemeinbildende Sekundarstufe II dar und umfaßt die Module

  • Informatiksysteme verantwortlich nutzen,
  • Elemente der theoretischen Informatik,
  • informatische Modellierung.

Die Prüfung des Konzepts erfolgt in drei Richtungen:

  1. Durch exemplarische Studien bezüglich des Bildes der Informatik bei Schülerinnen wird eine Facette des Forschungsgegenstandes näher ausgeleuchtet.
  2. Das Konzept wird darüber hinaus durch die Anwendung zur Analyse verpflichtenden Informatikunterrichts in der Sekundarstufe I herangezogen und
  3. als gestaltungsleitender Konstruktionshintergrund zur Erstellung von Informatiksystemen als Lernhilfen für den Informatikunterricht geprüft.

Es wird gezeigt, daß die entwickelte Grundlage nicht nur als konstruktionsleitender Hintergrund für den Informatikunterricht geeignet ist, sondern darüber hinaus sowohl zur Analyse des Informatikunterrichts beitragen und nicht zuletzt Hilfestellung bei den Anforderungen zur Gestaltung von Informatiksystemen für den Einsatz im Unterricht bieten kann. Als Folgerung aus der erfolgreichen Prüfung des vorgestellten Konzepts wird eine Reihe von offenen Fragestellungen ausgewiesen, die über den Informatikunterricht in der allgemein bildenden Sekundarstufe II hinausweisen.


 

Thursday, 04. July 2002: Kolloquium

Referent:Prof. Klaus-Peter Löhr, FU Berlin
Titel:Automatische Vermittlung zwischen unverträglichen Komponenten
Resümee:

Komponentenbasierte Entwicklung wird in der Praxis oft dadurch erschwert, daß es keinen universell gültigen Komponentenbegriff gibt. Somit muß man sich entweder auf ein bestimmtes Komponentenmodell festlegen (z.B. EJB, COM+, ...) oder man muß Software-Brücken oder -Hüllen ("wrappers") schaffen, die zwischen den heterogenen Modellen vermitteln.

Zwischen unverträglichen Interaktionsstilen heterogener Komponenten (Aufruf, Nachrichten, Ereignisse,...) kann durch automatisch generierten Code vermittelt werden. Die konkrete Schnittstelle einer Komponente (z.B. aufrufbasiert) wird hinter einer abstrakten Schnittstelle verborgen, die sich lediglich auf abstrakte Ein/Ausgabeereignisse der Komponente bezieht und mit einer Sprache AID (Abstract Interface Definition) beschrieben wird. Aus dem AID-Text wird automatisch Vertreter-Code erzeugt, der die Komponente gegenüber der Umgebung gemäß dem dort praktizierten Interaktionsstil vertritt, ferner Treiber-Code, der mit der Komponente in deren Stil interagiert. Verteter und Treiber können als Verallgemeinerung der bei Fernaufrufen verwendeten Stubs gesehen werden; sie kommunizieren über ein spezielles Ereignis-Protokoll.

Einfache Komponenten, für die bereits experimentelle Generatoren vorliegen, sind Java-Klassen, Unix-Filter und stromverarbeitende Haskell-Funktionen. Aufwendiger zu behandeln sind CORBA-Komponenten und EJB 2.0 Message-Driven Beans.


 

Thursday, 06. June 2002: Kolloquium

Referent:Prof. Michael Thielscher, TU Dresden
Titel:Kognitive Agenten
Resümee:

Die Informatik versteht unter Agenten Systeme, die in ein größeres Umfeld integriert sind und in diesem agieren. Kognitive Agenten besitzen die Fähigkeit, Handlungsentscheidungen auf der Grundlage eines expliziten internen Modells ihrer Umgebung zu fällen. In dem Vortrag wird eine neuartige Programmiermethodik für kognitive Agenten präsentiert und in die zugrundeliegende Theorie der Repräsentation und des logischen Schließens über Aktionen eingeführt. Zukunftsweisende Anwendungsgebiete kognitiver Agenten sind persönliche Softwareagenten für das Internet und die Steurung autonome Roboter.


 

Thursday, 21. February 2002: Forschungs-Kolloquium

Referent:Eckart Modrow, Max-Planck-Gymnasium
Titel:Fundamentale Ideen als Leitlinien für schulnahe Curriculumfortschreibung
Resümee:

Für den Informatikunterricht besteht einerseits Bedarf an größerer Konstanz als bisher, andererseits an einer gerichteten Fortentwicklung, die in höherem Tempo als in anderen Fächern abläuft und deshalb zu großen Teilen in den Schulen selbst geleistet werden muss. Im Vortrag wird versucht, den Weg zu einem Kanon von langfristig gültigen Inhalten zu bestimmen, die anhand fundamentaler Ideen der Informatik ausgewählt werden. Dieser Kanon soll dann mit austauschbaren und somit vor Ort leicht aktualisierbaren Inhalten verwirklicht werden. Die Auswirkungen auf die aktuelle Virtuelle Lehrerweiterbildung Informatik in Niedersachsen VLIN werden diskutiert.


 

Wednesday, 20. February 2002: Forschungs-Kolloquium

Referent:Dr. Joachim Selbig, Max-Planck-Institut für molekulare Pflanzenphysiologie
Titel:Bioinformatics: From protein structure prediction to medical applications

 

Friday, 15. February 2002: Forschungs-Kolloquium

Referent:Prof. Dr. Juhani Karhumäki, Uni Turku (Finnland), Sektion Mathematik und Informatik-Zentrum
Titel:Some open problems in combinatorics of words and related areas
Resümee:

Combinatorics of words is an enormous source of fascinating open problems. Problems might be of quite a different nature, some asking decision questions and some others existential questions of various types. Often problems are closely related to other areas of discrete mathematics, in particular to algebra or matrices. A striking feature of these problems is that they are very easy to formulate and understand, but in many cases very hard to solve. In other words, they are mathematically extremely challenging.

The goal of this talk is to discuss several such problems. More precisely, we introduce six problem areas and formulate on each of these 1-4 different problems. Problems are by no means "discovered" by the author, but each of those have fascinated the author over the past years.

The problems we introduce deal with the following questions on different problem areas: How large can an independent system of word equations on n variables be? When does a cumulative defect effect of words hold true? When an equality language of two morphisms is guaranteed to be "simple"? When is the equivalence of two finite substitutions on languages decidable? When do two finite languages commute? Are some simple problems on integer matrices decidable?


 

Thursday, 31. January 2002: Kolloquium

Referent:Prof. Ilkka Niemelä, Helsinki University of Technology, Finnland
Titel:Logic Programs with Weight Constraints
Resümee:

A novel logic program like language, weight constraint rules, is developed for answer set programming purposes. It generalizes normal logic programs by allowing weight constraints in place of literals to represent, e.g., cardinality and resource constraints and by providing optimization capabilities. A declarative semantics is developed which extends the stable model semantics of normal programs. A decidable fragment of the language allowing restricted use of variables and function symbols is introduced. For ground programs the computational complexity of the language is shown to be similar to that of normal programs under the stable model semantics. A simple embedding of general weight constraint rules to a small subclass of the language called basic constraint rules is devised. The language has been implemented in the Smodels (http://www.tcs.hut.fi/Software/smodels/) using a two level architecture. A front-end compiles general weight constraint rules to basic constraint rules for which an efficient search procedure computing stable models has been developed.


 

Thursday, 29. November 2001: Forschungs-Kolloquium

Referent:Markus Holzer, Universität München
Titel:An Overview on Auxiliary Pushdown and Stack Automata
Resümee:

An auxiliary pushdown automaton is a resource bounded Turing machine with a separate resource-unbounded pushdown (PD) store. Probably, such machines are best known for capturing P when their space is logarithmically bounded (Cook 1971) and for capturing the important class LOG(CFL) P when additionally their time is polynomially bounded (Sudborough 1978). These two influential milestones in reality form part of an extensive list of equally striking characterizations using variants of auxiliary stack automata. For example, a stack (S) is a pushdown store allowing its interior content to be read at any time, a nonerasing stack (NES) is a stack which cannot be popped, and a checking stack (CS) is a nonerasing stack which forbids any push operation once an interior stack symbol gets read.

In this talk known results for deterministic, nondeterministic, and (empty) alternating auxiliary pushdown and variants of stack automata are summarized. A handful of fundamental "tricks" are presented forming the basis of all known simulations. For instance, Cook's "surface configuration" trick (1971), Ibarra's (1971) and former authors' "response set" or "pointer to a pointer" trick, and Ladner et. al's tricks (1984) to simulate alternation. Although very much is known for these machine, there were still some open problems. For instance, unsettled questions are about auxiliary stack automata with a constant number of alternations, with running time restrictions, and/or with the feature of empty alternation. Recently this gap was closed by completing the picture afforded by variants of auxiliary stack automata. Part of this talk presents results from a joint work together with Pierre McKenzie (Université de Montréal).


16.12.2014