Program kolokvií s abstrakty pro semestr Jaro 1998

17. 2. 1998: Prof. Keith G. Jeffery, CLRC Rutherford Appeleton Laboratory, Chilton; Metadata; Abstract: The information world changed over 4 years ago, yet data / information suppliers (with some notable exceptions) have hardly noticed. If metadata describing the information available in an information provider system is not visible on the web the information itself is invisible to the world. People do not have time, energy or motivation to find information from suppliers with arcane access procedures. The importance of metadata cannot be underestimated - in both commercial and publicity terms. The W3C (World Wide Web Consortium) current work in this field is providing the world standard. Metadata allows for intelligently-assisted querying, online help and intelligent interpretation of results. Metadata helps in quality control of input data. Metadata allows systems to exchange information or participate in global queries over heterogeneous distributed systems. Metadata can advertise information. Metadata is in every sense the gateway to information systems. There is no commonly-accepted consensus on what is metadata. This seminar proposes a classification and starts to move towards bringing some formality into this very informal area of Information Technology.
3. 3. 1998: Professor Dr. Peter Starke, Humbolt University, Berlin; Signal event nets; Abstract: Modular synthesis of control devices is based on a concept of interaction for modules. If the modules are described by classical Petri nets, the only concepts available in net theory so far are token reading (by so-called test arcs, i.e. loops), token passing (from module to module) and merging (synchronization) of transitions. It is easy to see that these concepts are not sufficient. What is needed is a non-symmetric synchronization of transitions. Hanisch and Rausch introduced a new concept of non-symmetric synchronization by signals which are 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 usability for modular synthesis of control devices, and show their position in the hierarchy of computational models. Moreover we give some preliminary results on the analysis of such nets.
10. 3. 1998: Professor Dr. Georg Gottlob, Technische Universitaet, Vienna; Existential Second Order Logic on Strings; Abstract: Second-order logic has attracted the interest of logicians, mathematicians, and computer scientists for a long time, and many important results have been obtained which link logic and automata theory. Two of the most well-known results are the famous Buechi Theorem, which says that monadic second-order logic (MSO) over strings precisely characterizes 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 (nonmonadic) ESO, i.e., prefix classes of ESO which express only regular languages. Our main results are briefly summarized as follows. Denote by ESO(Q) 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, i.e., ESO(E*AA) and ESO(E*AE*) are the maximal regular standard prefix classes.
1.-3. give a complete characterization 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 by a DFA, or it is NP-complete.
5.) We give a precise characterization of those prefix classes of ESO which are equivalent to MSO over strings.
6.) Assuming NP <> coNP, we give a precise characterization of those standard prefix classes of ESO which, over strings, are closed under complement.
The results are joint work with Th. Eiter (Giessen) and Y. Gurevich (Michigan)
17. 3. 1998: Professor Dr. Guenter Harring, University of Wien; Analytic performance modelling with workload uncertainities and variables; Abstract: Uncertainties and variabilities in workload parameters, like service demands, may exist in many types of system models. Using analytic models with a single aggregate mean value for each parameter in such systems can lead to inaccurate or even incorrect resutls. In this presentation the use of histograms is proposed for characterizing mean model parameters that are 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 cumulated and can be refined.
24. 3. 1998: Profesor Eva Hajicova, DRSc, KU, Praha; Potrebuje informatika lingvistiku?; Abstract: V prednasce se zamyslime nad minulym prinosem lingvistiky a lingvistu pro 'computer science' (Chomskeho gramatiky), pro formalni semantiku (i jako jedno z vychodisek reprezentace znalosti) i pro aplikace v oblastech jako komunikace s pocitacem a v selekci informaci, a pokusime se naznacit nejaktualnejsi oblasti kontaktu mezi obema vednimi obory.
31. 3. 1998: RNDr Ludek Matyska CSc, FI MU Brno; Metapocitace; Abstract: "META-computing" predstavuje jeden z nejnovejsich smeru v oblasti velmi narocnych vypoctu. V podstate se jedna o spojeni i geograficky vzdalenych heterogennich vypocetnich zdroju prostrednictvim vysokorychlostnich siti do jednoho virtualniho celku -- paralelniho METApocitace.
Uspesna realizace METApocitace vyzaduje vyreseni cele rady administrativnich i technickych problemu, spojenych s geografickou rozlehlosti, s rozdilnymi administrativnimi zvyklostmi, s heterogenitou spojovanych zdroju, kvalitou a vlastnostmi propojovacich siti a v neposledni rade i s vhodnym vypooetnim modelem pro jeho efektivni vyuziti. Netrivialnim problemem jsou i vhodne aplikace, schopne vyuzit takto shromazdene vypocetni prostredky.
Druha cast prednasky bude venovona stavu realizace METApocitace v Ceske republice a moznostem vyuziti ATM propojovaci site pro vyreseni alespon nekterych problemu kvalitniho spojeni vypocetnich uzlu. V zaveru prednasky budou prezentovany i vysledky prvnich aplikaci, vyuzivajicich vykon budovaneho METApocitace.
7. 4. 1998: Doc. Martin Platek CSc , KU, Praha; Formalne prostredky pro separaci syntakticky korektnich a nekorektnich struktur; Abstract: Abstrakt. Tematem prednasky budou restartovaci automaty a jiste typy formalnich gramatik (FOD-gramatiky). Restartovaci automaty a FOD-gramatiky se jevi vhodnym formalnim prostredkem pro studium valence a slovosledu v ceske syntaxi (a v jinych jazycich s volnym slovosledem). V prvni casti prednasky budou prezentovany teoreticke vysledky o vypocetni sile a dalsich vlastnostech ruznych typu restartovacich automatu. Tyto vysledky byly dosazeny v poslednich letech ve spolupraci s P. Jancarem, F.Mrazem, M.Prochazkou a J.Voglem.
Druha cast prednasky bude venovana technikam formalniho zachyceni povrchove syntaxe cestiny pomoci FOD-gramatik. Tyto techniky jsou vyvijeny ve spolupraci s T.Holanem, V.Kubonym a K.Olivou.
14. 4. 1998: Doc. Jiri Wiedermann, DrSc, UIVT CAV Praha; Kogitoid: Matematicky model mentalni cinnosti; Abstract: Soucasny pokrok v oblasti kognitivnich vypoctu naznacuje, ze se blizi doba, kdy odhalime algoritmicke principy mentalni cinnosti mozku. I proto se studium, navrh a realizace prislusnych "myslicich" stroju stava predmetem zvyseneho zajmu v informatice. Vetsina soucasnych vypocetnich modelu mozkove cinnosti vychazi z biologicky motivovanych modelu mozku.
V prednasce uvedeme nove vysledky a pohledy, tykajici se matematickeho modelu kognitivni cinnosti mozku - tzv. kogitoidu. Kogitoid predstavuje radikalni odklon od biologicky motivovanych modelu mozku a spise modeluje "dusevni pochody" na urovni formovani konceptu a excitacnich a inhibicnich vazeb mezi nimi. Krome popisu prislusneho modelu strucne naznacime, ze v jeho ramci lze dokazat zakladni behavioristicke vzorce chovani, vcetne Pavlovovskych reflexu a uceni metodou odmeny a trestu.
Jako novy vysledek ukazeme, ze prislusnymi periferiemi a senzory (pameti, psacim a ctecim zarizenim) vybaveny kogitoid lze naucit simulovat libovolny Turinguv stroj a ze kazdy kogitoid lze simulovat pomoci interaktivniho Turingova stroje.
Dale naznacime pomoci myslenkoveho pokusu, ze pokud by kogitoid dostaval podobne vstupy jako lidsky mozek a mel moznost ridit podobne periferie, po case lze ocekavat formovani chovani ne nepodobneho tomu, ktere je rizeno lidskou mysli.
Specialne, v kogitoidu se zacnou spontanne formovat jiste struktury, ktere odpovidaji episodicke pameti, ramcum pro casto opakovane aktivity, rolim, ktere hraji ruzne objekty, mechanismum pozornosti pro ruzne kontexty, a zvykum. Zvyky predstavuji vykonnou, algoritmickou cast kogitoidu. V prislusnem modelu lze potom vysvetlit napr. formovani konceptu "ja", tok mysleni, introspekci, problemy svobodne vule, uceni se jazykum, generaci reci, a vznik vedomi. Kogitoid by principialne prosel Turingovym testem.
Prislusna teorie naznacuje, ze fenomen mysleni vubec nemusi byt vlastni pouze zivym tvorum a pripadne k jejim obrazum konstruovanym mechanismum.
21. 4. 1998: Dr. Jan Pavelka CSc, KU a DCIT Praha; Software Process Assessment and Improvement; Abstract: Information and communication technologies represent a large and still growing share of the investment and operation expenses both in the industry and all levels of government. Too often, however, the potential of these technologies for attaining the strategic objectives of the customers and the improvement of the quality and effectiveness of their business processes remains untapped. For information system projects, slippages and cost overruns are still rather a rule than an exception.
The talk confronts three aspect of software process quality assessment and improvement that reflects the shift of 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 project will be presented.
28. 4. 1998: Doc. Ing. Martin Sperka CSc, Katedra informatiky a vypoctovej techniky, FEI STU, Bratislava; Post symbolicka komunikacia clovek-stroj: realita a vizie multimedii; Abstract: Sucasny vyvoj pocitacov, videa a telekomunikacii dava realne sance, ze sucasny sposob komunikacie clovek-pocitac alebo clovek-clovek cez pocitac, kde sa komunikuje s pocitacovym programom alebo inou osobou (cez pocitac) pomocou symbolickej reprezentacie veci a javov sa moze zmenit na komunikaciu s ich vizualnymi, zvukovymi resp. taktilnymi klonami. Prednaska sa bude zaoberat s niektorymi prikladmi realizacie tychto vizii vo vedeckych a umeleckych projektoch
5. 5. 1998: Dr. Klara Osolsobe PhD, Ustav Ceskeho jazyka, FF MU, Brno; Formalni prostredky pro separaci syntakticky korektnich a nekorektnich struktur
12. 5. 1998: Dr. Pavel Pudlak DrSc, Matematicky ustav, Praha; O algoritmech pro splnovani logickych formuli; Abstract: Prestoze je splnovani booleavskych formuli NP-uplna uloha, je zajimave, jak z praktickeho tak teoretickeho hlediska, studovat (exponencialni) algoritmy pro tento problem. V prednasce udelam prehled znamych algoritmu a znamych dolnich odhadu pro specialni pripady a potom se soustredim na nedavne vysledky o pravdepodobnostnich algoritmech pro splnovani, ktere jsou rychlejsi, nez deterministicke.
19. 5. 1998: Dr. Vaclav Matyas, University of Cambridge, Computer Laboratory, FI MU, 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 public key cryptography users. 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 came along in the 70's, its inventors suggested that the names of computer users, and their public keys, should be published in a public directory like a phone book. By the 80's, the idea had shifted to certification authorities (CAs). However, people still have to get authentic copies of the public keys of the certification authorities themselves. It is unlikely that a cross-certification will work soon. Also, CAs have solved only part of the problem, and the part which remains 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 book of public key fingerprints.
The talk will present both practical and scientific issues arising from the project. Further information can be found at the web page of The Global Trust Register.
26. 5. 1998: Mgr. Milan Sekanina, PrF MU Brno; Shape in computing; Abstract: Most data structures commonly supported by programming languages, including arrays, lists and trees, can be split into two components -- the underlying structure (or the shape) and the data stored within. Though the benefits of manipulating the data alone have been known for a long time (as witnessed, for example, by the wide-spread use of data polymorphism), only in recent years has greater attention been paid to the shape content as well, primarily by 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 the talk we will concentrate on shape analysis, a branch of shape theory which extracts the shapes of datastructures and uses them for program optimisation. It concentrates on using shape analysis for detecting errors arising from ill formed or incompatible shapes. A typical example of such shape errors might be multiplying matrices of ill matched dimensions. Since shape analysis ignores all data and data-based computations, it has a potential to be very efficient, as well as completely safe error-checking method.