Programme of colloquia with abstracts for the Spring 2004 semester

24 February 2004: Prof. Pavel Zezula, CSc, Faculty of Informatics, Masaryk University, Brno; Tree signatures of XML documents; Abstract: To speed up the execution of various matching and navigation operations on collections of XML documents, a new indexing structure based on tree signatures is proposed. We demonstrate that XML tree structures can be efficiently represented as ordered sequences of pre-order and post-order ranks, on which extended string matching techniques can readily solve the tree matching problem. We also demonstrate how to apply tree signatures in query processing and show that a speed-up of up to one order of magnitude can be achieved compared with the containment join strategy. Other applications of tree signatures in intelligent XML searching are outlined in the conclusions.
2 March 2004: Prof. Ivo Serba, CSc, Faculty of Informatics, Masaryk University, Brno; Knot Algorithms; Abstract: Motto: From the legacy of the Celts to computer-generated creations. Decorative knots represent one of the most fascinating topics in Computer Art. The aesthetic value of knot patterns lies in their intricate interlacing. Knotting algorithms are shrouded in the mystery of the ages and are undoubtedly worthy of your attention. The lecture will begin with a brief mention of several theoretical concepts and will then focus on algorithms for recording interlacing patterns, which show promise (i) for computer interpretation.
9 March 2004: Prof. Jaroslav Nesetril, DrSc, Faculty of Mathematics and Physics, Charles University, Prague; Satisfiability with Constraints, Complexity and Algebra, 14.00; Abstract: In this lecture, we shall present examples of satisfiability problems with constraints and an approach to solving these problems using algebraic methods, which is based on the study of structures derived (invariant) via polymorphism.
This approach has recently led to the resolution of a number of long-standing open problems. Owing to its generality, the approach appears suitable for many specific situations.
9 March 2004: Prof. Franz Baader, TCS, TU Dresden; Engineering of logics for the content-based representation of information, 15.00; Abstract: The 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. The content-based representation of information, which seeks to overcome this shortcoming, requires representation formalisms with a well-defined formal semantics. This semantics can be elegantly provided by translating the formalism into a suitable logic or by using a logic-based formalism from the outset. However, in this context, there is a fundamental trade-off between the expressiveness of the representation formalism and the efficiency of reasoning using this formalism.
This motivates the ‘engineering of logics’, i.e. the design of logical formalisms that are tailored to specific representation tasks. The talk will illustrate this approach using the example of so-called Description Logics and their application to databases and as ontology languages for the Semantic Web.
16 March 2004: Dr Michael Noelle, ARC Seibersdorf Research Ges.m.b.H, Seibersdorf, Austria; Visual pattern recognition, pattern search and quantum information; Abstract: The talk will provide an overview of some tasks, possible solutions and problems encountered in the field of visual pattern search and pattern recognition. Starting from practical applications, the talk will highlight strategies that enable solutions across different application areas. In particular, the close relationships with certain methods used in quantum information theory will be discussed.
23 March 2004: Prof. Jan Slovak, DrSc, Faculty of Law, Masaryk University, Brno; Geometry – its role and tools; Abstract: In a broadly conceived presentation, I shall attempt to outline the implications and forms of geometric thinking in contemporary mathematical methods. The discussion will centre on symmetries, their algebraic expressions and analytical consequences, as well as analytical problems and geometric approaches to their algebraic solutions.
In all cases, I shall endeavour to highlight their practical applicability in computational and classification tasks and their algorithmisation.
30 March 2004: RNDr. Bohumir Stedron CSc, Adviser to the Chairman of the Czech Telecommunications Office, Prague; The future has already begun; Abstract: This presentation describes the development of a new super-technology in the field of artificial intelligence in the past, present and future, and posits that future developments will not be determined by two components – namely, humans and robots – but by a total of four: humans, the biosphere (equipped with artificial intelligence (higher mammals, cetaceans, insects, the plant kingdom), systems of mutually communicating robots, and artificial life (the legal system, artificially intelligent computer and telecommunications networks, the energy system and food production). Scenarios for the development of the information society up to the year 2050 will be presented, along with new aspects of the future development of the legal system. The presentation places new super-technology – artificial intelligence – on a par with the fundamental discoveries of human civilisation, such as the discovery of fire, the wheel and writing as a means of recording information. The lecture includes a number of new approaches: the transition to a holographic model of the world around 2030; the limitation of holographic information extraction carried out by biological systems represents a further mechanism of biological evolution alongside the well-known Darwinian mechanism of natural selection; and a new explanation of the energy crisis affecting parts of Canada and the USA in August 2003 as a manifestation of artificiallife in information systems. The presentation is based on the book by Belohlavek, Stedron: The Future Has Already Begun, published by Sdelovaci technika in 2003, and an article published in the American journal FUTURIST, March 2004 (Stedron: Forecasts for Artificial Intelligence).
6 April 2004: Doc. Ivan M. Havel, DrSc, CTS, KU, Prague; TheEnactive Approach in Cognitive Science; Abstract: Over the last two decades, a new direction has emerged in cognitive science, known as enactive cognitive science (F. Varela et al., 1991). Unlike the classical, cognitivist approach, which is based on the notion of the human mind as an algorithmic process operating on symbolic representations, the enactive approach regards mental processes as part of the organism’s sensorimotor activity within its environment. Embodied cognition does not consist in the representation of a pre-given world within a pre-given mind, but rather in the ongoing enaction or shaping of an individual world and, simultaneously, of the mind itself, throughout the continuous history of human action within the environment. Perception, which is mutually conditioned by action, serves as the guide in this process. Cognitive structures are formed through emergent and self-organising processes that interconnect the brain, the body and the environment. In this lecture, I shall discuss some of the basic concepts of the enactive approach and their potential application in the analysis of certain modalities of human experience.
13 April 2004: Doc. Maria Bielikova, PhD, FIIT, STU, Bratislava; Development and modelling of adaptive hypermedia.; Abstract: The popularity of adaptive hypermedia – particularly the adaptive presentation of information in the form of hypermedia applications – has been rising significantly in recent times, partly due to the increasing volume of information available on the web. This lecture focuses on certain aspects of adaptive hypermedia, particularly in relation to the models that enable the adaptive presentation of information. We will analyse methods and techniques for adaptation at the levels of content, presentation and navigation, which are based not only on the user model (e.g. user preferences, level of knowledge, goals), but also on the environment model (location, language, device used, time) in which the user finds themselves. We shall illustrate this customisation using the example of an application for the field of education. We will not address specific problems and tasks arising from the nature of the media presented.
20 April 2004: Doc. Emil Pelikan CSc, UI CAV, Prague; Predictive methods and their application; Abstract: Estimating the future behaviour of a given variable is necessary wherever we are dealing with uncertainty. This paper will discuss some principles that can assist in the design and application of predictive models. Particular attention will be paid to statistical prediction models, although other aspects will also be mentioned, such as judgemental forecasting, the use of artificial neural networks, the combination of prediction methods, etc. We shall also present some real-world results achieved through the application of forecasting methods in the fields of energy, banking, meteorology, the environment and transport.
27 April 2004: Ing. Tomas Vojnar, FIT, Brno University of Technology; Verification of parametric systems with shared resources.; Abstract: (Joint work with: Ahmed Bouajjani and Peter Habermehl, LIAFA, Université Paris 7)
One very common source of potential errors in concurrent systems is access to shared resources. It is therefore desirable to be able to verify the correctness of how shared resources are handled in such systems. In this talk, we discuss the verification of parameterised systems of processes competing for access to shared resources under the FIFO resource management policy, with or without priorities. We consider various generic property classes expressible in (fragments of) temporal logics, covering certain forms of safety, deadlockability and liveness.
In particular, we present three types of results. (1) We prove that certain parametric verification problems arising in the context under consideration can be efficiently reduced to finite-state verification. This is achieved by demonstrating that, to prove a given property for any number of processes, it is often sufficient to consider a certain ‘cut-off’ number of processes, depending on the number of processes made visible in the formula of interest and/or the number of available resources. (2) For some problems in the domain of FIFO with priorities, we show that using a simple cut-off as in the previous case is generally insufficient. However, such problems may still be decidable, and there may exist cut-offs that additionally take into account the structure of the process control automaton and/or the formula to be verified. We present an example of such a cut-off for 1-index liveness properties. (3) Finally, we discuss some undecidability results relating to this area.
11 May 2004: RNDr. Jan Paseka CSc, Faculty of Law, Masaryk University, Brno; Quantum algebras and their applications in computer science; Abstract: Quantum algebras were introduced by C.J. Mulvey in connection with efforts to formulate the foundations of quantum mechanics constructively. At the same time, it was shown, amongst other things, that intuitionistic linear logic can be interpreted in commutative quantum bundles and that commutative quantum bundles form a consistent and complete class of models.
In this lecture, we shall present basic examples of quantum algebras and outline methods for their application in theoretical computer science.
One such example will be the so-called relational quantum algebras, which form a consistent and complete class of models for non-commutative intuitionistic linear logic. Another example will be the ideals of Kleene algebras, which are studied within the framework of language theory.
18 May 2004: Prof. Pavel Slavik, FEL, CTU, Prague; Navigation methods in 3D space; Abstract: This lecture will describe various approaches to solving the problem of navigation in space. The lecture summarises the results achieved by the Department of Computer Science over the last few years as part of several national and international projects. The results obtained stem primarily from two groups of applications:

spatial orientation for blind and visually impaired people
support for spatial orientation using mobile devices.

For both applications, methods have been developed for the effective filtering of information, enabling both the easy creation of mental models of the environment by blind users and the optimisation of the display process on mobile devices. Furthermore, special interaction methods for blind users will be described, which facilitate the acquisition of additional information about the structure of the environment in which the user is located.