Programme of colloquia with abstracts for the Autumn 1998 semester

29 September 1998

FI Research Projects

Abstract:

• Prof. RNDr. J. Gruska, DrSc: Quantum information and computing
• Doc. Ing. J. Staudek, CSc.: Security Policies in Information Technology
• Doc. Ing. J. Sochor, CSc.: Human–computer interaction
• Doc. RNDr. M. Kretinsky, CSc.: Parallel and Distributed Systems
• Doc. PhDr. K. Pala, CSc.: Information Technology in Natural Language Processing
• Doc. RNDr. I. Kopecek, CSc.: Dialogue Systems and Dialogue Programming with Applications in Assistive Technologies
• Mgr. M. Kozubek, Dr.: Applications of computer image analysis in cytogenetics

6 October 1998

Bing Wu, Trinity College, Dublin, Ireland

Legacy Information Systems: The Problems and Possible Solutions

Abstract: Legacy information systems typically form the backbone of the information flow within an organisation and are the main vehicle for consolidating information about the business. To address the problems these systems present – fragility, inflexibility, isolation, lack of scalability, lack of openness, etc. – many companies are migrating their legacy systems to a new environment that allows the information system to adapt easily to new business requirements.
This talk aims to provide an overview of the migration of legacy information systems. Firstly, it discusses the problems associated with legacy systems and outlines the possible solutions. Secondly, the main focus is on a detailed discussion of the evolutionary approach to the legacy system problem: the migration of legacy systems. Two main approaches to migration currently available – the gateway-based ‘Chicken Little’ approach and the gateway-free ‘Butterfly’ methodology – are presented in detail. A brief comparison between these two methods is also provided. Finally, some possible future research topics and directions are outlined.

13 October 1998

Ivan Kopecek, Faculty of Informatics, Masaryk University, Brno

DIALOG – programming with your eyes closed

Abstract: The DIALOG programming system is a new paradigm inspired by efforts to develop programming support for the visually impaired. Paradoxically, it has become apparent that many of the principles are general in nature and lead to an entirely new perspective. The main features of DIALOG are:
- programming based on dialogue with natural language support
- high consistency and, consequently, simplicity of the language
- full system integration
- object-oriented design (in a somewhat non-traditional sense)
- structured orientation
DIALOG is the first language that is not a language in the classical sense (it is not a subset of a free monoid) and which therefore moves away from the concept of a language written on paper. DIALOG is a system developed at FI, raising many interesting practical and theoretical issues.

P.S.: One day, we will be able to programme in DIALOG. Either because:
A) it is such a good system, or
B) you’ll ruin your eyes by programming in classical languages.


A) is correct :-)

20 October 1998

J. Cernocky, FEI VUT Brno

Speech Processing using Automatically Derived Segmental Units: Applications to Very Low Rate Coding and Speaker Verification

Abstract: Sub-word units are widely used in various domains of speech processing. Traditionally, they are based on phonemes or their derivatives (context-dependent phonemes, syllables, etc.) and require a significant amount of phonetic and linguistic knowledge to be determined. In order to train a speech processing system, one must have access to an annotated training database (DB). Annotation using phonetically-derived units is a time-consuming, costly and error-prone task.
Although natural language processing cannot be carried out without phonetic and/or linguistic expertise, recent advances in Automatic Language-Independent Speech Processing (ALISP) have demonstrated that many tasks currently reliant on such knowledge can be performed more efficiently using data-driven approaches.
Among the various ALISP tools, we use Temporal Decomposition (introduced by Atal in 1982 and refined by Bimbot) to determine segment boundaries, and unsupervised clustering, represented by Vector Quantisation (VQ), for class assignment. The segmental units are modelled using Hidden Markov Models (HMMs) – these are initialised using the original TD+VQ transcriptions and refined in successive steps of corpus segmentation and parameter set re-estimation. Experiments were also carried out using multigrams (MG) as pre- or post-processing for the HMMs.
The application of this method is demonstrated using a very low bit-rate speech vocoder. In the encoder, the incoming speech is segmented into coding units and their indices are transmitted. The decoder incorporates a speech synthesiser, which concatenates examples of coding units (‘representatives’) drawn from the training corpus. In speaker-dependent experiments, carried out using the PolyVar and Boston University databases, intelligible speech was achieved at an average bit rate of 120 bps for the transmission of unit indices. However, side-information is still required for the transmission of representative selection and prosody.
Another application of these units is in text-independent speaker verification. It is known that the discriminative power of different phonemes varies and that phoneme-based verification systems perform better than ‘global’ ones. Where a speech recogniser is not available, ALISP units may be used to segment and classify speech for a verification system. This approach was tested using a Multi-Layer Perceptron (MLP) during the NIST-NSA 98 evaluation campaign. The results demonstrated the superiority of this approach over the global MLP system.

27 October 1998

Petr Hanacek, FEI VUT Brno

The Security of Electronic Money

Abstract: The topic of this lecture will be the issue of the security of electronic payments and, in particular, one form of these – electronic money.
In recent years, there has been increasing pressure to develop e-commerce systems. However, it is very difficult to create a functional e-commerce system without a corresponding system for making electronic payments. It is, of course, possible to use one of the conventional payment systems (such as payment cards, cheques or payment orders); however, these instruments do not meet the current requirements for the quality and speed of e-commerce. The resulting e-commerce system would, in fact, suffer from all the shortcomings inherited from these payment instruments. That is why new electronic payment systems are being developed, the main aim of which today is to convert conventional money into its electronic equivalent – electronic money.
Given that the situation in the field of electronic payment systems is currently somewhat unclear, this paper will also endeavour to introduce a taxonomy for classifying these systems according to various criteria.
The issue of electronic money is closely linked to the issue of information system security and, above all, cryptography. Designing a purely functional electronic payment system is straightforward. However, designing a functional and secure (i.e. fraud-resistant) payment system is relatively complex, and security mechanisms often constitute the most important part of the system. This issue will be illustrated using the specific example of an electronic wallet.

3 November 1998

Antonín Kučera, TU Munich and FI MU

Bisimulation and Simulation Games: Infinite vs. Finite-State Systems

Abstract: The ‘semantic sameness’ of two concurrent processes X and Y is often defined by means of bisimulation- and simulation-like games on the transition systems associated with X and Y. These games are played by two players, Al and Ex; Al repeatedly ‘attacks’ Ex with his moves, and Ex must ‘defend’ each of these individual moves by making his own move that is consistent with the rules. Al wins the game if, after a finite number of rounds, Ex is unable to defend against Al’s final attack. Processes X and Y are then considered to be ‘the same’ if and only if Ex has a universal defence strategy. (i.e., Al cannot win the game if Ex plays sufficiently cleverly).
As the processes X and Y can have an infinite number of states, the existence of a defence strategy for Ex is generally undecidable. We focus solely on the sub-case where X is infinite-state, whilst Y is guaranteed to have only a finite number of states. We devise a general method for establishing the decidability of the problem of whether Ex has a defence strategy in a bisimulation-like game. We also show that this method can be successfully applied to various classes of infinite-state processes (from which X can be chosen) and various bisimulation-like equivalences (in particular, strong and weak bisimulation equivalences). We also demonstrate that there is a close relationship with the model-checking problem for the simple temporal logic EF.
We then examine the analogous problem(s) for simulation games. As we shall see, decidability issues for bisimulation- and simulation-like games are quite different, although there is an interesting and general relationship between bisimulation and simulation, which will also be precisely formulated (and applied). Finally, we present some decidability and undecidability results for specific process classes.
The first part of the talk is based on joint work with P. Jancar and R. Mayr, which was presented at Icalp’98. The second part contains some recent (unpublished) results.

10 November 1998

Dana Pardubska, KVI, Faculty of Mathematics and Physics, Comenius University, Bratislava

OBDDs – Ordered Binary Decision Diagrams

Abstract: Thanks to their algorithmic properties, OBDDs have become a popular data structure in the fields of CAD, testing and verification of digital systems. They are a highly effective tool provided that their size does not exceed a certain critical threshold. In general, OBDDs are highly sensitive to the order in which variables are tested – there are known to be exponential differences in the size of equivalent OBDDs depending on the order of the variables. It is therefore natural that considerable attention is devoted to the problem of optimising the size of OBDDs. As this problem is NP-hard, various heuristics are used in practice to solve it.
This lecture will introduce OBDDs, their properties and the problem of optimising their size. We will present the most efficient known heuristics together with algorithms for manipulating OBDDs.

17 November 1998

Jiří Zara, Faculty of Electrical Engineering, Czech Technical University in Prague

Construction of a BSP tree to accelerate the ray-tracing method

Abstract: The partitioning of three-dimensional space and its representation using hierarchical data structures is one of the fundamental means of reducing computation time for a range of tasks based on searching for objects according to specified conditions. Among the most sophisticated data structures are binary trees – BSP (Binary Space Partitioning trees). A special case of these, based on orthogonal space partitioning, finds effective application in computer graphics, particularly in ray casting and ray tracing tasks.
Various criteria are used to construct a BSP tree – tree balance, minimising the number of objects in the leaves, and a heuristic approach. Similarly, a BSP tree can be represented by various data structures, the form of which influences the efficiency of subsequent traversal.
The lecture will discuss various criteria for constructing orthogonal BSP trees and their corresponding data structures. Furthermore, algorithms for traversing BSP trees with regard to the ray-tracing method will be presented.

24 November 1998

Ivana Kolingerová, University of West Bohemia, Plzeň

Construction of Triangular and Quadrilateral Meshes

Abstract: Triangular and tetrahedral meshes play a significant role in approximations, the finite element method, numerical analysis, CAGD, computer graphics, computer vision, robotics, etc. Consequently, numerous methods have gradually emerged for the construction of triangular meshes – triangularisation – and tetrahedral meshes – tetrahedronisation. These methods differ in terms of the requirements for the resulting mesh, computational complexity, implementation difficulty and numerical stability.
This lecture briefly summarises the basic methods of triangularisation and tetrahedronisation and their properties. Emphasis will also be placed on the common and distinct features of meshes in E2 and E3. In addition to an overview of existing methods, original results will also be included.

1 December 1998

Peter Ruzicka, Faculty of Mathematics and Physics, Comenius University, Bratislava

Interval Routing Schemes: A Survey

Abstract: We survey both the classical and the most recent results achieved in the field of Interval Routing Schemes, a well-known strategy for implementing distributed routing algorithms in a compact manner. These results are categorised into several themes: characterisation, compactness and shortest path, dilation and stretch factors, congestion, specific classes of graphs (interconnection networks, planar graphs, graphs of bounded degree, chordal rings, etc.), and other recent extensions, including deadlock-free, multi-dimensional and distributed problems related to Interval Routing Schemes. For some of these themes, we present the state of the art and several open questions.

8 December 1998

Herbert Wiklicky, University of Mannheim, Germany

Linear Operators in Semantics

Abstract: This talk introduces a new approach to the semantics of Concurrent Constraint Programming (CCP), which is based on operator algebras. In particular, we show how (stochastic) matrices can be used to model both a quantitative version of nondeterminism (in the form of a probabilistic choice) and synchronisation. We will take Probabilistic Concurrent Constraint Programming (PCCP) as the reference paradigm. The model presented here subsumes CCP as a special case.
The model is derived via a fixpoint construction on a space of linear operators. For the purposes of this talk, we consider only finite constraint systems. This enables us to define our model using finite-dimensional linear operators, i.e. matrices. We show that this model is equivalent to a notion of observables which extends the standard one in CCP (input/output behaviour) by including information about the likelihood of the computed results. The model also captures infinite computations.

15 December 1998

Radim Jirousek, VSE Prague

Representation of high-dimensional distributions by Bayesian networks

Abstract: In many probabilistic artificial intelligence models, it is necessary to work with high-dimensional distributions (of the order of hundreds or thousands). Graphical Markov models were developed for this purpose; they make effective use of the properties of conditional independence to represent such distributions efficiently. This lecture will introduce the two most important of these models: Bayesian networks and decomposable models. It will also outline the methods by which computations can be performed within these models.