Programme of colloquia with abstracts for the Autumn 1997 semester

30 September 1997: Dr Martin Schoenhacker, Vienna University of Technology; Visualisation of Algorithms; Abstract: As algorithms continue to grow in size and complexity, modern computer science faces the problem that understanding — let alone improving — these algorithms is becoming increasingly difficult. Teaching them effectively is yet another challenge. There are even algorithms that cannot possibly be followed without appropriate tools, for instance in multi-processor systems. All of these tasks can be made easier by using systems capable of visualising algorithms and corresponding data structures.
Following a general overview, the results of various experiments conducted over the last few years will be used to illustrate useful applications of visualisation techniques. One such example, a typical algorithm operating on graphs, demonstrates the usefulness of visualisation in understanding problems that are not necessarily rooted in computer science.
7 October 1997: Prof. RNDr. Jaroslav Kral, Charles University, Faculty of Informatics, Brno; Horizontal Software Integration; Abstract: What is horizontal integration? Tools for horizontal integration. Advantages and disadvantages of horizontal and vertical integration. An example of the use of horizontal integration in software from Lawson Software. Similar trends can be observed in software as in other areas of production. There is a gradual shift from vertical integration (everything under one roof) to horizontal integration (flexible collaboration, multiple entities). The advantages and disadvantages of both approaches will be discussed. Furthermore, horizontal integration in software has the advantage that it is only possible if technologies are used that will shape the future of software. The advantages of horizontal integration will be illustrated using a commercial enterprise solution from Lawson Software, which was the first to introduce a high-quality web-based solution. Another example is the integration of a workflow system and alternative data warehouse solutions. The conditions for achieving a situation where the customer can assemble the system themselves will be discussed.
14 October 1997: Prof. Dr Alexander Leitsch, Vienna University of Technology; Resolution Decision Procedures and Automated Model Building; Abstract: Resolution is frequently regarded merely as a method for deriving the empty clause from an unsatisfiable set of clauses. However, by adapting resolution refinements to the specific syntactic properties of clause classes, it can be transformed into a decision procedure and even into a model-building method. We demonstrate how hyperresolution can be applied as a model-building procedure in the form of post-processing following the decision procedure. The method consists of an iteration of deductive closure and clause reduction and is entirely backtracking-free. The final result of the procedure is an atomic (not necessarily ground) representation of a Herbrand model. Furthermore, we define an algorithmic method for evaluating the truth of clauses (‘model checking’) over (symbolic representations of) Herbrand models — thereby extending the scope of model checking to infinite models; this method is again based on resolution, and is purely proof-theoretic and symbolic. Finally, we show how decision procedures, model building and clause evaluation can be extended to Herbrand models with equality, and present some open research problems and new techniques.
21 October 1997: Dr Pavol Sevecek, Faculty of Informatics, Brno; New-generation dictionaries
4 November 1997: Doc. Petr Jancar, CSc, Technical University, Ostrava; Petri nets (a personal perspective); Abstract: Following a general introduction to Petri nets as a means of modelling, designing and analysing systems, the author will focus primarily on his own results in this field. These primarily concern research into the limits of algorithmic verifiability; the main findings will be outlined informally.
11 November 1997: Dr Jiri Sgall, MU CAV Prague; Multiparty communication complexity; Abstract: One motivation for studying communication complexity is to use it as a tool for proving lower bounds on Boolean circuit complexity. We survey these connections and models of multiparty communication complexity studied in this context. Next, we present some upper bounds demonstrating that even some seemingly very restrictive models of communication can be surprisingly powerful. We conclude with open problems that illustrate the current state of the art in this field.
18 November 1997: Professor Dr Hermann Maurer, Graz University of Technology, Austria; Content management and training aspects on large websites; Abstract: I will review the problems that arise when managing large websites using most current web systems. These problems are mainly due to the fact that insufficient support is provided for ‘content’ management. I will argue that many tasks which could be handled automatically require manual intervention in most systems, that automatic data and link management are not merely a pipe dream, and that the combination of powerful web servers with existing database systems provides optimal solutions for large websites, particularly for intranet and educational applications. I will support my claims by discussing the WWW system Hyperwave in some detail and explaining a number of concrete examples. I will demonstrate a number of features hitherto unheard of in other systems. Finally, I will explain how Hyperwave, as an add-on, enables a smooth migration path from current WWW servers to more manageable environments, and that not only the information provider (webmaster) but also users benefit significantly from this process.
2 December 1997: Doc. Pavol Voda CSc, Institute of Informatics, Faculty of Mathematics and Physics, Comenius University, Bratislava; Computer programming as mathematics; Abstract: CL (Clausal Language) is a computer programming language with mathematical syntax (no reserved words) suitable for teaching an introduction to
* declarative programming,
* programme specification and verification,
* computability theory.
We teach these three topics in three courses during the first two years of the undergraduate programme. This is only possible because we have designed CL as a minimal language that supports precisely the unary primitive recursive functions over natural numbers. CL is not only a programming language but also incorporates its own proof system, within which one can state and prove properties of programmes. The strength of the system lies in I\Sigma1-arithmetic, which is a simple fragment of Peano arithmetic.
The domain of natural numbers is so well-known that students have no difficulty understanding the meaning (semantics) of CL functions and possess a good intuition regarding their properties. This stands in contrast to similar systems with more complex and less intuitive domains, such as PVS, which is based on typed functionals. Our experience is that students not only seem to understand but also enjoy the presentation in CL of the above extremely important topics in computer science. We will answer some FAQs (frequently asked questions) about CL:
** Do we lose the expressiveness of the language by restricting CL to the domain of natural numbers?
** Isn’t the encoding of data structures as natural numbers artificial and computationally costly?
** Do we lose computational efficiency by restricting definitions in CL to the schemas of primitive recursive functions?
Why only primitive recursive functions – why not Ackermann?
We will argue that the answer to the first three questions is a resounding NO. Question (4) will be answered by reference to Gödel’s incompleteness theorem.
9 December 1997: Professor Jiri Zlatuska, CSc, Faculty of Informatics, Masaryk University, Brno; Stepping stones to an information society; Abstract: The information revolution is radically transforming many of the patterns along which society and businesses have traditionally operated. These changes do not merely bring minor technological improvements, but represent a fundamental transformation of our industry-based society into an information-based one. The changes are most visible and well-documented within the business world, but the synergy between technological and social shifts does not stop there. This talk addresses the key trends and challenges that this development presents to us.
16 December 1997: Dr Jana Kosecka PhD, University of California, Berkeley; Intelligent highway systems – From theory to practice and back to theory; Abstract: In this talk, I will first provide a brief overview of the activities carried out under the Intelligent Highway Systems Programme over the past five years at UC Berkeley. This has been one of the most widely publicised projects in computing in recent times. I will present the basic concept of the Automated Highway, the overall architecture of the system and some of the practical and theoretical issues, the resolution of which led to a highly successful demonstration of an Intelligent Highway Concept, which took place in August 1997 in San Diego and attracted a great deal of media attention.
In the second part of the talk, I will show that the main aim of the project – to increase motorway capacity whilst preserving and improving the safety of individual vehicles – has led to the development of novel techniques in the field of hybrid system verification, as well as the design of a new programming language for simulating such systems. The successful operation of an automated vehicle in a dynamically changing environment and in the presence of other vehicles requires the coordination of information from various sensors and the control of various actuators. In the third part of my talk, I will present in more detail the design of an automated vehicle control system using visual sensing, which was carried out in collaboration with HONDA R&D North America.
The talk will be accompanied by video demonstrations.