Programme of colloquia with abstracts for the Spring 1999 semester

2 March 1999: Prof. Vladimir Buzek, DrSc, Slovak Academy of Sciences, Bratislava; The Secret Life of Qubits; Abstract: In the first part of my talk, I briefly review the basic concepts and ideas of quantum information processing. I introduce the definitions of the qubit, the superposition principle and entanglement. These concepts are essential for explaining phenomena such as quantum dense coding, quantum teleportation and quantum cloning. Using these tools, I will demonstrate how they can be applied in quantum cryptography (quantum key distribution) and quantum computing. I will conclude the review section of the talk with comments on physical feasibility, decoherence and quantum error correction schemes.
The second part of the talk is devoted to a description of optimal operations on qubits.
9 March 1999: Prof. Eduard Groeller, Vienna University of Technology; Interactive visualisation applications; Abstract: Visualisation techniques are often quite time-consuming. Interactivity, however, is highly desirable in many applications to facilitate insight and visual analysis. Therefore, the investigation of interactivity issues is a significant area of research in scientific visualisation.
In the first part of my talk, I will provide a brief overview of recent visualisation projects undertaken by our group (http://www.cg.tuwien.ac.at/research/vis/).
In the second part, I will discuss some of the projects in more detail: fast maximum-intensity projection, fast surface rendering for volumetric data, multimodal volume visualisation, and oriented line integral convolution. Particular emphasis will be placed on real-time techniques for 3D flow visualisation.
16 March 1999: Mgr. Rudolf Ruzicka, Brno; Computer music — computer-based musical art; Abstract: A brief history of the use of computers in musicology and in the creation of musical compositions (Hiller, Isaacson, the ‘Illiac Suite’ for string quartet from August 1956, and others).
Computer-generated electroacoustic music as an autonomous art form. For musicology, the analysis of musical works is of great value; computers are used to gain insights into musical style and other aspects of the analysed compositions.
An introduction to computer programmes for the creation of artificial musical works, their automatic notation and sound realisation. Synthesisers that mimic musical instruments and human voices.
Audio samples of Czech and international computer music.
23 March 1999: Prof. Jaroslav Nesetril, DrSc, Faculty of Mathematics and Physics, Charles University, Prague; A morphism scheme for combinatorial optimisation; Abstract: This lecture will present a scheme suitable for expressing good characteristics (i.e. membership of the classes NP and coNP) for combinatorial optimisation problems and for polynomially solvable instances of such problems. This relates, on the one hand, to the theory of good quasi-orders and, on the other, to the so-called hom-duality theorems. We shall present the characteristics of these theorems for general relational systems (which were recently proven by the author together with C. Tardif).
30 March 1999: Doc. Libor Polak, CSc, Faculty of Science, Masaryk University, Brno; Unification in subgroup classes; Abstract: The two main areas of application of (equational) unification in computer science and artificial intelligence are deductive systems and term rewriting. The problem of unification is nothing other than the solving of equations in free algebras. The fundamental questions concern the existence of solutions and, if they exist, the description of all solutions, e.g. by means of so-called ‘most general’ solutions. In computer science, we speak of decidability, unification types, unification algorithms and unification procedures. The unification type is determined by the structure of the set of all solutions (= unifiers) to solvable equations. This may be unitary, finite, infinite or zero, depending on the cardinality of the set of the most general solutions (= minimal unifiers). Type zero means that such a set does not exist at all. A unification algorithm/procedure (for finite/infinite type) yields the set of all minimal unifiers. We shall focus on certain classes of (unary) semigroups, typically involving constants. We shall recall well-known results concerning the varieties of all subgroups, commutative subgroups, semilinks, completely regular subgroups, groups and commutative groups. We shall outline the author’s results concerning decidability for completely simple and completely regular subgroups and note the set of all solutions to certain equations, e.g. $ xy = yx$ or $ p x^n q = r$, for example in inverse subgroups.
6 April 1999: Dr Jozef Vyskoc, Bratislava; Computer Steganography; Abstract: The protection of data transmitted via public (open) channels can essentially be achieved in two ways, In the first case, the message is transformed prior to transmission with the aim of ensuring that the result is ‘understandable’ only to the authorised recipient. The second method is based on transforming the message so that an unauthorised person is unable to detect or extract the original message from the transmitted data. In the first case, we are talking about cryptography; the second approach is known as steganography.
Whilst cryptography has, over the years of its existence, succeeded in establishing a solid theoretical framework, steganography was, until recently, known mainly in connection with invisible inks, microdots and similar technology-driven (and difficult to formalise) methods of concealment. In recent years, however, there has been a sharp rise in interest in the application of steganographic principles within the environment created by modern information technologies.
The aim of the lecture is to provide a basic introduction to this fascinating area of information security. The lecture will focus on the following areas: a brief historical overview of steganography; methods of computer steganography; the taxonomy of steganographic algorithms; the relationship between steganography and cryptography
13 April 1999: Doc. Jiří Matoušek, DrSc, Faculty of Mathematics and Physics, Charles University, Prague; Combinatorial algorithms for linear programming; Abstract: The number of arithmetic operations performed by known polynomial-time algorithms for linear programming depends on the number of digits in the coefficients. We consider ‘combinatorial’ algorithms, where the number of arithmetic operations depends only on the dimension $d$ and the number of constraints $n$ (working with the model of computation commonly used in computational geometry). In this setting, no polynomial-time algorithm is known.
We survey some developments in this area from recent years (most of which are up to 5 years old), including a randomised algorithm with a subexponential expected running time.
20 April 1999: Dr Patrick Hanks, Oxford University Press, Oxford; On the preparation of the New Oxford Dictionary of English; Abstract: The talk focuses on a discussion of the process by which the largest and newest dictionary of contemporary English has been prepared and compiled. The resources (the British National Corpus) and the techniques used to build this monumental volume will be discussed and analysed.
27 April 1999: Prof. Nicola Leone, Vienna University of Technology; Representing and solving problems in the DIV System; Abstract: The advanced logic-based knowledge representation (KR) languages developed over the last two decades allow problems to be represented in a natural, declarative manner, using principles of common-sense reasoning. These languages are highly expressive; for instance, non-monotonic languages such as Default Logic, Autoepistemic Logic and Disjunctive Logic Programming allow very difficult problems (even SigmaP2-complete problems) to be encoded in a simple manner. Nevertheless, such languages are rarely used in practice, and their application in specific domains has been very limited. This is mainly due to the lack of efficient implementations of non-monotonic languages, the development of which is a difficult task because the greater the expressive power, the higher the computational complexity of the language.
The dlv system — currently under development at the Vienna University of Technology — has the ambitious aim of addressing this shortcoming by providing an efficient implementation of a highly expressive non-monotonic language that can serve as a tool for the development of advanced knowledge-based applications. The kernel language of dlv is full disjunctive Datalog under stable model semantics (dlv stands for DataLog with ‘v’, i.e., DataLog with disjunction) extended with strong negation (à la Gelfond and Lifschitz), integrity constraints, and finite integers, together with arithmetic operators and comparison predicates; dlv also provides front-ends to other advanced KR formalisms. Smart algorithms and sophisticated optimisation techniques are implemented in dlv to ensure efficient programme evaluation. This talk demonstrates the use of dlv as an ‘implementation engine’ for knowledge representation purposes. In particular, we illustrate how complex problems from various application domains can be naturally encoded in the dlv language in a declarative and easy-to-understand manner. We also present some benchmarks showing that even hard problems of a reasonable size are solved rather quickly by dlv. These benchmarks are compared with the dlv evaluation times reported at KR’98, and highlight the tremendous speed-up achieved over the past year, which makes us very optimistic about the possibility of achieving dlv’s ultimate goal.
29 April 1999 Thursday: Prof. Mark Hillery, Hunter College, City University of New York; Quantum secret sharing; Abstract: Secret sharing is a procedure for splitting a message into several parts so that no subset of parts is sufficient to read the message, but the entire set is. We show how this procedure can be implemented using quantum GHZ states. In the quantum case, the presence of an eavesdropper will introduce errors, thereby enabling his presence to be detected. We also show how GHZ states can be used to split quantum information into two parts so that both parts are necessary to reconstruct the original qubit.
4 May 1999: Ing. Vladimir Benko, L. Stura Institute of Linguistics, Slovak Academy of Sciences, Bratislava; Lexicography, computers and ‘cheap solutions’; Abstract: One of the tasks of computational lexicography is the computerisation of the dictionary-compilation process. The first step involves, in particular, selecting a suitable software environment and developing tools and methods to streamline the work of lexicographers at all stages of a lexicographical work’s life cycle. Given the relatively small market and the specific needs of individual lexicographical projects, there are as yet virtually no commercial software tools that would satisfactorily cover at least the main activities involved in dictionary compilation. Nor can we expect this situation to change in the near future. Most projects are therefore reliant on using tools originally designed for other purposes, whilst the development of ‘bespoke’ tools is only feasible on a very limited scale. In this lecture, using the example of several lexicographical projects, we highlight the need for and possibilities of so-called ‘low-cost solutions’, which can be applied particularly in the area of dictionary text validation (this primarily involves error detection and improving the consistency and integrity of data, whereby we consider the ratio of the ‘cost’ in terms of the amount of programming work to the number of errors found as a measure of the solution’s success). We present one possible way of representing dictionary data on a computer and a set of tools used at our workplaces to process it.
11 May 1999: Dr Thomas Worsch, Department of Computer Science, University of Karlsruhe; Cellular automata with dynamically reconfigurable buses; Abstract: Motivated by advances in FPGA technology and optical computing, there is growing interest in dynamically reconfigurable architectures. In this talk, we will consider an extension of the very simple model of one-dimensional cellular automata. Even in this case, the addition of reconfigurable buses already leads to a seemingly very powerful model (RCA) on which one can solve all PSPACE problems in polynomial time. Building partly on Rothstein’s work on bus automata, we provide a characterisation of RCA time complexity in terms of Turing machines.
18 May 1999: Prof. Jiri Zlatuska, Masaryk University, Brno; Globalisation of Academic Disciplines; Abstract: Trends associated with the advent of the information society are creating a transformed environment for research work and altering its nature, the ways in which collaboration takes place, and the methods used to measure results.
Computer science acts here both as a catalytic medium in which these changes take place as a consequence of more general processes, and as a new element in the construction of infrastructure for these disciplines.
The exchange of information in symbolic form creates a permeable environment corresponding to ‘globalisation’ in its purest form or to the prototype of a ‘knowledge’ society.
25 May 1999: Dr Wolfgang Slany, Technical University, Vienna; Ramsey games; Abstract: We study combinatorial games based on graph Ramsey theory: Given two graphs G and A, two players, Red and Green, take turns colouring the edges of G in their respective colours. The aim is to avoid (or achieve) the creation of a monochromatic subgraph isomorphic to A. We determine the complexity of finding winning strategies for several variants of these games and provide ultra-strong solutions for some small instances.
A Java applet that improves its strategy by playing online and allows you to play some small but non-trivial instances can be tried out at http://www.dbai.tuwien.ac.at/proj/ramsey/.
Please give it a go! If you win, you’ll be able to add your name to our hall of fame.
8 June 1999: Shun Ha Sylvia Wong, BSc, University of Birmingham; An investigation into the use of Argument Structure and Lexical Mapping Theory in LFG for Machine Translation; Abstract: Lexical Functional Grammar (LFG) has been widely used as the linguistic backbone for recent Machine Translation (MT) systems. The relatively order-free functional structure (f-structure) in LFG is believed to provide a suitable medium for performing source-to-target language transfer in a transfer-based MT system. However, the linguistic information captured by traditional f-structure is syntax-based, which makes it relatively language-dependent and thus inadequate for handling the mapping between different languages. Problems have been identified in lexical selection and in the transfer of certain English passive sentences into Chinese. The recent development of the relatively language-independent argument structure (a-structure) and lexical mapping theory within the LFG formalism appears to offer a solution to these problems. In the light of the study carried out on the application of a-structure and lexical mapping in various tasks involving the translation of English sentences into Chinese, this talk will discuss how this method can be used to improve the structural disambiguation process for various combinations of verbs and prepositions, as well as how to improve the lexical selection process for verbs. This talk will also illustrate how the use of a-structure and lexical mapping theory can overcome the problem of translating certain passive sentences from English into Chinese. A brief assessment of the effectiveness of using a-structure and lexical mapping theory for machine translation (MT) will also be provided in this talk.