Programme of colloquia with abstracts for the Spring 1998 semester

17 February 1998: Prof. Keith G. Jeffery, CLRC Rutherford Appleton Laboratory, Chilton; Metadata; Abstract: The information landscape changed over four years ago, yet data and information providers (with a few notable exceptions) have scarcely taken notice. If metadata describing the information available within a provider’s system is not visible on the web, the information itself remains invisible to the world. People lack the time, energy or motivation to seek out information from providers with obscure access procedures. The importance of metadata cannot be underestimated – both commercially and in terms of publicity. The W3C’s (World Wide Web Consortium) current work in this field is establishing the global standard. Metadata enables intelligently assisted querying, online help and the intelligent interpretation of results. Metadata aids in the quality control of input data. Metadata enables systems to exchange information or participate in global queries across heterogeneous, distributed systems. Metadata can publicise information. Metadata is, in every sense, the gateway to information systems. There is no widely accepted consensus on what constitutes metadata. This seminar proposes a classification and begins to move towards introducing some formality into this very informal area of Information Technology.
3 March 1998: Professor Dr Peter Starke, Humboldt University, Berlin; Signal event nets; Abstract: Modular synthesis of control devices is based on a concept of interaction between modules. If the modules are described by classical Petri nets, the only concepts available in net theory to date are token reading (via so-called test arcs, i.e. loops), token passing (from module to module) and the merging (synchronisation) of transitions. It is easy to see that these concepts are insufficient. What is needed is a non-symmetric synchronisation of transitions. Hanisch and Rausch introduced a new concept of non-symmetric synchronisation via signals passed from transition to transition: the signal from the source transition forces the target transition to fire if it is enabled; otherwise, the signal has no effect. In this talk, we consider the corresponding class of Signal-Event-Nets, demonstrate their suitability for the modular synthesis of control devices, and show their place in the hierarchy of computational models. Furthermore, we present some preliminary results on the analysis of such nets.
10 March 1998: Professor Dr Georg Gottlob, Technische Universität, Vienna; Existential Second-Order Logic on Strings; Abstract: Second-order logic has long attracted the interest of logicians, mathematicians and computer scientists, and many important results have been obtained that link logic and automata theory. Two of the best-known results are the famous Buechi Theorem, which states that monadic second-order logic (MSO) over strings precisely characterises the regular languages, and Fagin’s Theorem, which states that the existential prefix class of second-order logic (ESO) exactly expresses the NP properties over finite structures (in particular, over strings). Thus, ESO is a much more expressive logic over strings than MSO. However, little is known about the relationship between syntactic fragments of ESO and MSO.
We shed light on this issue by investigating regular prefix classes of (non-monadic) ESO, i.e., prefix classes of ESO which express only regular languages. Our main results are briefly summarised as follows. Let ESO(Q) denote the prefix class Sigma^1_1(Q), where Q is a first-order prefix class.
1.) The prefix class ESO(E*AA) is regular. (Note that model checking for this class is NP-complete over graphs.)
2.) The prefix class ESO(E*AE*) = ESO(Ackermann) is regular. (Note that model checking for this class is NP-complete over graphs.)
3.) Any prefix class ESO(Q) not contained in the union of ESO(E*AA) and ESO(E*AE*) is not regular; that is, ESO(E*AA) and ESO(E*AE*) are the maximal regular standard prefix classes.
1.–3. provide a complete characterisation of the regular prefix classes of ESO.
4.) We obtain the following dichotomy theorem:
Let ESO(Q) be any prefix class. Then, either ESO(Q) is regular, or ESO(Q) expresses some NP-complete language.
This means that model checking for ESO(Q) is either possible using a DFA, or it is NP-complete.
5.) We provide a precise characterisation of those prefix classes of ESO which are equivalent to MSO over strings.
6.) Assuming NP ≠ coNP, we provide a precise characterisation of those standard prefix classes of ESO which, over strings, are closed under complement.
The results are the result of joint work with Th. Eiter (Giessen) and Y. Gurevich (Michigan)
17 March 1998: Professor Dr Guenter Harring, University of Vienna; Analytic performance modelling with workload uncertainties and variables; Abstract: Uncertainties and variabilities in workload parameters, such as service demands, may be present in many types of system models. Using analytical models with a single aggregate mean value for each parameter in such systems can lead to inaccurate or even incorrect results. In this presentation, the use of histograms is proposed for characterising mean model parameters associated with uncertainty and/or variability. It will be shown where these types of parameters might exist, how existing solution techniques can be adapted appropriately, and how corresponding performance measures can be aggregated and refined.
24 March 1998: Professor Eva Hajicova, DRSc, Charles University, Prague; Does computer science need linguistics?; Abstract: In this lecture, we shall reflect on the past contributions of linguistics and linguists to ‘computer science’ (Chomsky’s grammar), for formal semantics (including as one of the foundations of knowledge representation) and for applications in areas such as human–computer interaction and information retrieval, and we shall attempt to outline the most current areas of interaction between the two disciplines.
31 March 1998: RNDr Ludek Matyska CSc, Faculty of Informatics, Masaryk University, Brno; Metacomputing; Abstract: ‘META-computing’ represents one of the newest trends in the field of highly demanding computations. Essentially, it involves linking geographically dispersed, heterogeneous computing resources via high-speed networks into a single virtual entity — a parallel META-computing system.
The successful implementation of METApocitace requires the resolution of a whole range of administrative and technical problems associated with geographical scale, differing administrative practices, the heterogeneity of the interconnected resources, the quality and characteristics of the interconnecting networks, and, last but not least, the selection of a suitable computational model for its effective utilisation. Another non-trivial challenge lies in identifying suitable applications capable of utilising the computational resources thus pooled.
The second part of the lecture will be devoted to the current state of METApocitace implementation in the Czech Republic and the possibilities of using ATM interconnection networks to resolve at least some of the problems associated with high-quality connections between computing nodes. The lecture will conclude with a presentation of the results of the first applications utilising the computing power of the METApocitace system currently under construction.
7 April 1998: Doc. Martin Platek CSc, KU, Prague; Formal methods for distinguishing between syntactically correct and incorrect structures; Abstract: The lecture will focus on restarting automata and certain types of formal grammars (FOD grammars). Restarting automata and FOD grammars appear to be a suitable formal framework for the study of valency and word order in Czech syntax (and in other languages with free word order). The first part of the lecture will present theoretical results concerning computational power and other properties of various types of restart automata. These results have been achieved in recent years in collaboration with P. Jancar, F. Mraz, M. Prochazka and J. Vogel.
The second part of the lecture will be devoted to techniques for the formal capture of the surface syntax of Czech using FOD grammars. These techniques are being developed in collaboration with T. Holan, V. Kubony and K. Oliva.
14 April 1998: Doc. Jiří Wiedermann, DrSc, UIVT CAV Prague; Kogitoid: A mathematical model of mental activity; Abstract: Current progress in the field of cognitive computing suggests that the time is approaching when we will uncover the algorithmic principles underlying the brain’s mental activity. This is one reason why the study, design and implementation of such ‘thinking’ machines are becoming a subject of increased interest in computer science. Most current computational models of brain activity are based on biologically motivated models of the brain.
In this lecture, we shall present new findings and perspectives concerning a mathematical model of the brain’s cognitive activity – the so-called ‘kogitoid’. The cogitoid represents a radical departure from biologically motivated models of the brain and instead models ‘mental processes’ at the level of concept formation and the excitatory and inhibitory connections between them. In addition to describing the model in question, we shall briefly indicate that, within its framework, it is possible to demonstrate basic behaviourist patterns of behaviour, including Pavlovian reflexes and learning through reward and punishment.
As a new result, we shall show that, with the appropriate peripherals and sensors (memory, writing and reading devices), a cogitoid can be taught to simulate any Turing machine, and that any cogitoid can be simulated using an interactive Turing machine.
Furthermore, we shall suggest, by means of a thought experiment, that if a cogitoid were to receive inputs similar to those of the human brain and were able to control similar peripherals, one could expect, over time, the formation of behaviour not unlike that controlled by the human mind.
In particular, certain structures will begin to form spontaneously within the cogitoid, corresponding to episodic memory, frameworks for frequently repeated activities, the roles played by various objects, mechanisms of attention for different contexts, and habits. Habits constitute the efficient, algorithmic part of the cogitoid. In the corresponding model, it is then possible to explain, for example, the formation of the concept of ‘self’, the flow of thought, introspection, problems of free will, language learning, speech generation, and the emergence of consciousness. In principle, a cogitoid would pass the Turing test.
The relevant theory suggests that the phenomenon of thought need not be exclusive to living beings or, for that matter, to mechanisms constructed in their image.
21 April 1998: Dr Jan Pavelka CSc, KU and DCIT Prague; Software Process Assessment and Improvement; Abstract: Information and communication technologies account for a large and still growing share of investment and operating expenditure, both in industry and at all levels of government. All too often, however, the potential of these technologies to help customers achieve their strategic objectives and improve the quality and effectiveness of their business processes remains untapped. For information system projects, delays and cost overruns are still the rule rather than the exception.
This presentation addresses three aspects of software process quality assessment and improvement that reflect the shift in emphasis from ‘fitness to model’ to ‘fitness for purpose’:
a) ISO 9001 compliance
b) CMM assessment
c) Project quality assurance.
To illustrate these approaches, a case study of a real-world project will be presented.
28 April 1998: Doc. Ing. Martin Sperka CSc, Department of Informatics and Computing, FEI STU, Bratislava; Post-symbolic human-machine communication: the reality and vision of multimedia; Abstract: Current developments in computing, video and telecommunications offer a realistic prospect that the current method of human-computer or human-human communication via a computer – where one communicates with a computer programme or another person (via a computer) using symbolic representations of objects and phenomena – may evolve into communication with their visual, auditory or tactile counterparts. The lecture will examine some examples of the realisation of these visions in scientific and artistic projects
5 May 1998: Dr Klara Osolsobe PhD, Institute of the Czech Language, Faculty of Arts, Masaryk University, Brno; Formal means for distinguishing between syntactically correct and incorrect structures
12 May 1998: Dr Pavel Pudlak, DrSc, Institute of Mathematics, Prague; On algorithms for satisfying logical formulas; Abstract: Although the satisfaction of Boolean formulas is an NP-complete problem, it is of interest from both a practical and theoretical perspective to study (exponential) algorithms for this problem. In this lecture, I shall provide an overview of known algorithms and known lower bounds for special cases, and then focus on recent results concerning probabilistic saturation algorithms, which are faster than deterministic ones.
19 May 1998: Dr Vaclav Matyas, University of Cambridge, Computer Laboratory, Faculty of Informatics, Masaryk University, Uptime Commerce Ltd.; The Global Trust Register; Abstract: The Computer Security Group at the University of Cambridge has been working on a project that should be of immediate interest to most users of public-key cryptography. This is the Global Trust Register, an annual directory published in collaboration with the MIT Press that contains the fingerprints of many important public keys used throughout the world.
When public-key cryptography emerged in the 1970s, its inventors suggested that the names of computer users, along with their public keys, should be published in a public directory, much like a telephone directory. By the 1980s, the idea had shifted towards certification authorities (CAs). However, people still have to obtain authentic copies of the public keys of the certification authorities themselves. It is unlikely that cross-certification will become viable any time soon. Furthermore, CAs have solved only part of the problem; the remaining challenge is to obtain an authentic copy of the CA’s root key. The Global Trust Register was developed to solve this problem in the form of a directory of public key fingerprints.
The talk will address both the practical and scientific issues arising from the project. Further information can be found on the Global Trust Register’s website.
26 May 1998: Mgr. Milan Sekanina, Faculty of Law, Masaryk University, Brno; Shape in computing; Abstract: Most data structures commonly supported by programming languages, including arrays, lists and trees, can be divided into two components – the underlying structure (or the shape) and the data stored within. Although the benefits of manipulating the data alone have been recognised for a long time (as evidenced, for example, by the widespread use of data polymorphism), it is only in recent years that greater attention has been paid to the shape as well, primarily by research groups studying areas such as intensional polymorphism or polytypism. Shape theory, a part of this programme of work, unifies the various notions of shape under a single framework.
In this talk, we will focus on shape analysis, a branch of shape theory which extracts the shapes of data structures and utilises them for programme optimisation. It concentrates on using shape analysis to detect errors arising from ill-formed or incompatible shapes. A typical example of such shape errors might be multiplying matrices of mismatched dimensions. Since shape analysis ignores all data and data-based computations, it has the potential to be a highly efficient, as well as completely safe, error-checking method.