Programme of colloquia with abstracts for the Spring 1997 semester

4 March 1997

Jiri Wiedermann, CSAV Prague

Cognitive computing – getting started

11 March 1997

Horst Reichl, TU Dresden

C0-induction

18 March 1997

Karel Pala, Faculty of Informatics, Masaryk University, Brno

A morphological analyser for Czech (corpus application)

25 March 1997

Michael Noelle, Technical University of Hamburg-Harburg

Data distribution concepts for data-parallel implementations

Abstract: Parallel distributed memory systems are increasingly used as scientific computing platforms, as they offer high performance at relatively low hardware costs. The widespread use of these systems depends mainly on the availability of software and the ease with which solutions for new applications can be developed. To exploit the high performance potential of distributed-memory multiprocessor systems, two programming paradigms – functional and data parallelism – are the main focus of research and are widely used. In this talk, data distribution concepts will be presented that offer a convenient, scalable and portable means of expressing data parallelism for a wide range of parallel systems and programming environments.
The impact of data distributions on parallel implementations can be described in terms of three factors. Load balancing addresses the task of distributing the workload evenly amongst the processors. Minimising communication involves optimising the volume and distance of data exchange between different processors at runtime. By overlapping computation and communication, it is often possible to mask communication latencies.
Data distributions suitable for parallel image processing and those defined by some of today’s more popular parallel languages (HPF) and libraries (ScaLAPACK) will be analysed. The impact of flexible data distributions on parallel implementations will be discussed.

2 April 1997

Petr Hajek, UIVP CSAV Prague

Deductive Systems of Fuzzy Logic

Abstract: Axiomatic systems of non-finite-valued propositional and predicate logics, which form formal systems of fuzzy logic, will be presented. The basis is the concept of a continuous t-norm as the semantics of fuzzy conjunction. I shall present both the basic fuzzy logic, which is correct for all logics defined by t-norms, and three special logics defined by three basic t-norms (Lukasiewicz, Gödel and product). Issues of complete axiomatisability, as well as computational and arithmetic complexity, will be discussed. In conclusion (or in the introduction), I shall address some frequently recurring questions and doubts concerning vagueness logics.

8 April 1997

Georg Gottlob, Vienna University of Technology

Revising and updating logical knowledge bases

Abstract: When knowledge is represented in logic, a knowledge base corresponds to a logical theory. Since our knowledge of the world changes continuously, such knowledge bases must be revised and/or updated. This talk provides an overview of various methods that have been developed in Computer Science (in the fields of Databases and AI) for incorporating new information into a knowledge base, even in the event of inconsistencies. A taxonomy of the various approaches will be presented, and three approaches will be discussed in detail. In particular, we will explain the difference between ‘revision’ and ‘update’. The complexity of knowledge base updates and revisions will also be discussed.

15 April 1997

Keith G. Jeffery, SERC, RAL, Oxon, UK

Databases and the Web

Abstract: The World Wide Web (WWW) is the most significant information technology yet known. Its impact is enormous – on both professional and personal life. However, the web has been developed with little or no reference to theoretical computer science or best-practice engineering. This seminar discusses end-user requirements, the features of the web and of database systems, and explores how the best features can be combined to provide well-engineered information systems.

22 April 1997

Frantisek Plasil, Faculty of Mathematics and Physics, Charles University, Prague

CORBA Architecture – Basic Principles

Abstract: The main aim of this talk is to provide the audience with a fundamental understanding of the Common Object Request Broker Architecture (CORBA), with an emphasis on one of its core components: CORBA Object Services (COSS). A brief history of CORBA’s development, from CORBA 1.1 to CORBA 2.0, which supports interoperability features, is provided. Key concepts specified in CORBA 1.1 and CORBA 2.0 are reviewed: Interface Description Language (IDL), client stub, server skeleton, Basic Object Adapter (BOA), Internet Inter-ORB Protocol (IIOP), request-level bridging and inline bridging. Based on the OMG series of Requests for Proposal (RFP), the evolution of expanding the family of CORBA Object Services is analysed and discussed.

29 April 1997

Jan Hajic, Charles University, Prague

Linguistic Annotations of the Czech National Corpus

Abstract: The Czech National Corpus is being compiled as a collection of Czech written texts from a wide variety of fields (journalism, fiction, non-fiction, ephemera, etc.). This collection essentially reflects the original text, albeit explicitly tagged (annotated) at the level of words, sentences, paragraphs and documents. However, for the purposes of linguistic research and applications in the field of natural language processing, it is important to have access to as much text as possible that is annotated not only ‘technically’ but also ‘linguistically’. In the ‘Formal Representation of Linguistic Structures’ project, we are working on three levels of such annotation: morphological, syntactic and text-grammatical. The morphological level deals with morphological categories such as case, number, gender, tense, etc., but sentence structure is not taken into account – it is treated as a linear sequence of words and their attributes. At the analytical level, which most closely resembles surface syntax as we know it from conventional grammars, a dependency structure and so-called analytical functions (subject, predicate, object, attribute, etc.) are introduced. The number of nodes in the dependency tree always corresponds to the number of words in the sentence. At the highest, tectogrammatical level, the project works with concepts of linguistic meaning, and also captures phenomena absent at the analytical level (ellipsis, reference, actual segmentation). The result of the entire project will be at least 0.5 million words annotated at the analytical level, and a smaller sample annotated at the tectogrammatical level.

6 May 1997

Bruno Buchberger, RISK Linz

The Theorema Project: An overview

Abstract: The Theorema Project aims to integrate proof support into computer algebra systems. The emphasis is on proof generation for routine parts of proofs, structured proof presentation in natural language, and seamless interaction with the existing solving and computing facilities of computer algebra systems. Our current system framework is Mathematica 3.0.
We will first provide an overview of the Theorema Project and then present further details regarding the following aspects of the system:
* A predicate logic prover that mimics the proof style of humans (in particular, the proof style of the authors).
* A number of specialised provers for various ‘areas’ of mathematics (currently for equalities over natural numbers, lists and polynomials), where an ‘area’ is defined by a functor that generates the domains within that area; these are currently under development. The main tool is simplification, combined with setting up the induction recursively over the universally quantified variables.
* Automatic generation of knowledge bases using the information contained in the functors.
* Structured proof presentation in (technical) natural language using the nested cells feature of Mathematica.
* Theory generation versus theorem proving.
The talk will be illustrated with demonstrations.

13 May 1997

Rudolf Freund, TU Wien

Molecular computing with test tube systems

Abstract: Test tube systems were introduced as molecular computing devices used to solve specific practical problems. In test tube systems, specific operations are applied to the objects within their components (test tubes) in a distributed and parallel manner; the results of these computations are redistributed according to specific input and/or output filters. Various theoretical models were investigated, such as test tube systems based on the splicing operation, as well as those based on the operations of cutting and recombination. Even simple, restricted types of filters allow the generation of any arbitrary recursively enumerable language when using the splicing operation or the operations of cutting and recombination. The same results can be obtained by using controlled sequences of test tubes instead of filters.

20 May 1997

Roland Vollmar, University of Karlsruhe

On some physical restrictions of models of computation

Abstract: We begin by citing Schorr’s results. He introduced two obvious restrictions, namely a finite size of processing elements and a finite speed of signals, and derived bounds for a possible speed-up of parallel devices. As a third restriction, we consider energy consumption, or heat dissipation, in three-dimensional devices. Different models are considered:
1. Heat dissipation proportional to the surface area of the entire cube in which the machine is housed
2. Heat dissipation proportional to the surface area of each subcube
3. The addition of wires, which reduces the energy costs associated with the transmission of information
It is shown that there are problems which can be solved by the different models only in different time scales.

27 May 1997

Petr Stepanek, Charles University, Prague

Declarative semantics of logic programmes

Abstract: Several semantics have been proposed for logic programmes and so-called ‘pure’ Prolog, which are based on the semantics of first-order logic and emphasise the declarative nature of logic programmes. Probably the best known is the semantics of the smallest Herbrand models (Van Emden, Kowalski (1976)). Of almost the same date is the semantics of the smallest term model (Clark (1979)), known today rather as the C-semantics (Falaschi et al. (1993)), whilst among the more recent ones is the so-called S-semantics (Falaschi et al. (1989)), which also provides a good description of the operational semantics of logical programmes. It is precisely the problem of the relationship between declarative and operational semantics and the proof of partial correctness of programmes that we shall be addressing.

10 June 1997

Ivan Bruha, McMaster University, Hamilton, Canada

Processing Unknown Attribute Values in Rule-based Inductive Algorithms

Abstract: Genuine inductive machine learning algorithms lack the ability to process unknown (missing) attribute values in the input (training and testing) databases. Newer versions of such algorithms have incorporated procedures for processing unknown attribute values. The speaker has designed and implemented an inductive learning algorithm capable of generating rules using the covering paradigm. He has also embedded several routines for processing unknown attribute values. In addition, the talk will introduce some new trends in this area of processing.

24 June 1997

V. A. Vasilenko, Novosibirsk

New developments in algorithms and software for multidimensional and extra-multidimensional (extraMD) approximations