Workshop im Kurort Gohrisch, 31. März - 04. April 2003

Vorträge und Abstracts:

• Prof. Dr. Franz Baader

  Engineering of Logic for the Content-based Representation of Information
  

  Abstract: Storage and transfer of information as well as interfaces for accessing this information have undergone a remarkable evolution. Nevertheless, information systems are still not "intelligent" in the sense that they "understand" the information they store, manipulate, and present to their users. A case in point is the world wide web and search engines allowing to access the vast amount of information available there. Web-pages are mostly written for human consumption and the mark-up provides only rendering information for textual and graphical information. Search engines are usually based on keyword search and often provide a huge number of answers, many of which are completely irrelevant, whereas some of the more interesting answers are not found. In contrast, the vision of a "semantic web" aims for machine-understandable web resources, whose content can then be comprehended and processed both by automated tools, such as search engines, and by human users.
  The content-based representation of information requires representation formalisms with a well-defined formal semantics since otherwise there cannot be a common understanding of the represented information. This semantics can elegantly be provided by a translation into an appropriate logic or the use of a logic-based formalism in the first place. This logical approach has the additional advantage that logical inferences can then be used to reason about the represented information, thus detecting inconsistencies and computing implicit information. However, in this setting there is a fundamental tradeoff between the expressivity of the representation formalism on the one hand, and the efficiency of reasoning with this formalism on the other hand. This motivates the "engineering of logics", i.e., the design of logical formalisms that are tailored to specific representation tasks. This also encompasses the formal investigation of the relevant inference problems, the development of appropriate inferences procedures, and their implementation, optimization, and empirical evaluation. The talk will illustrate this approach with the example of so-called Description Logics and their application for conceptual modelling of data bases and as ontology languages for the semantic web. The first application will be illustrated with a demonstration of the conceptual modelling tool ICOM.
  
  

  Terminological Cycles in a Description Logic with Existential Restrictions
  

  Abstract: Cyclic definitions in description logics have until now been investigated only for description logics allowing for value restrictions. Even for the most basic language FL0, which allows for conjunction and value restrictions only, deciding subsumption in the presence of terminological cycles is a PSPACE-complete problem. This report investigates subsumption in the presence of terminological cycles for the language EL, which allows for conjunction and existential restrictions. In contrast to the results for FL0, subsumption in EL remains polynomial, independent of whether we use least fixpoint semantics, greatest fixpoint semantics, or descriptive semantics. These results are shown via a characterization of subsumption through the existence of certain simulation relations between nodes of the description graph associated with a given cyclic terminology.

  
  

• Dipl.-Math. Björn Borchardt

  Recognizable Tree Series
  

  Abstract: The concept of weighted tree automata (wta) generalizes the models of (unweighted) tree automata and of weighted (string) automata. We investigate, which theorems of the two underlying models carry over to wta. Topics covered in the talk are the determinization and minimization of wta, characterizations of recognizable tree series, and decidability problems.
  

  
  

• Dipl.-Inf. Kai Brünnler

  Atomic Cut Elimination for Classical Logic
  

  Abstract: I firstly present a deductive system for classical propositional logic, which is in the tradition of the sequent calculus, but features deep inference and symmetry. These features allow to easily reduce the cut rule to atomic form, which is not possible in the sequent calculus. Because then it suffices to eliminate the atomic cut, I can secondly present the simplest cut elimination procedure known to me.
  

  
  

• Dipl.-Inf. Frank Felfe

  
  

  
  

• Dipl.-Math. Claus Jürgensen

  Monadic fusion of functional programs
  

  
  

• HDoz. Dr. Dietrich Kuske

  Automatische Strukturen (2 Stunden)
  

  
  

• Dipl.-Math. Leonard Kwuida

  Dicomplemented lattices
  

  Abstract: Concept algebras are concept lattices enriched by a weak negation and a weak opposition. The problem of finding an abstract structure (called dicomplemented lattice) the theory of which is the theory of concept algebras is still open. I will present some substantial results in the finite case. The class of weakly dicomplemented lattices, defined by some equations valid in all concept algebras, can be seen as a "natural" extension of Boolean algebras.
  

  
  

• Dipl.-Math. Ina Mäurer

  
  

  
  

• Dipl.-Inf. Andreas Maletti

  Accumulation - Improving the Efficiency of Functional Programs
  

  Abstract: Given a functional program script which contains endomorphisms (substitutions) and unary functions specified by simultaneous recursive descent (they may, however, liberally call upon the endomorphisms) on an algebraic data type, we integrate the endomorphisms into the unary functions by adding additional parameters to gain a semantically equivalent functional program script, which is at least as efficient as the original program.
  

  
  

• Dipl.-Math. Grit Malik

  Morphismen zwischen Begriffsgraphen - Eine Erweiterung der Theorie von Barwise und Seligman über den Informationsfluss in verteilten Systemen
  

  
  

• Dipl.-Math. Ingmar Meinecke

  Parallelism in costs
  

  Abstract: Up to now costs in word or tree automata were calculated by means of a semiring. The costs along a path were multiplied, and then the costs of all successful paths with the same label were summed up. But this does not provide the possibility to disthinguish between the way of calculation of sequential opposite to parallel processes. We present in this talk the model of branching automata with costs. These automata carry explicit different notions of sequential and parallel processes.
  We characterize the behaviour of these automata by a Kleene-like result.
  

  
  

• Dipl.-Math. Christian Pech

  Kleene-type results for weighted tree-automata
  

  Abstract: I will present one of the main results from my PhD-thesis. In particular I will demonstrate a characterization of recognizable formal tree-series over commutative semirings by rational expressions. This generalizes partial results by, Kuich, Bozapalidis, Bloom and Esik and of Droste and Vogler that needed to put different restrictions on the underlying semirings.
  

  
  

• Prof. Dr. Reinhard Pöschel

  
  

  
  

• Ulrike Püschmann

  
  

  
  

• Sebastian Rudolph

  Methoden der Formalen Begriffsanalyse zur extensionalen Exploration binärrelationaler Daten
  

  
  

• Dipl.-Inf. Lutz Straßburger

  Linear Logic and Non-commutativity in the Calculus of Structures
  

  
  

• Prof. Dr. Michael Thielscher

  (2 Stunden)
  

  
  

• Dipl.-Inf. Janis Voigtländer

  Efficiency Improvement by Tree Transducer Composition
  

  
  

(12.03.2003/sg)