Faculteit
VF programma: DISCRETE STRUCTUREN 3
Yüklə 1,87 Mb.
|
- Bu səhifədəki naviqasiya:
- 1.4 VF-programma: PROGRAMMEREN
- 1.5. VF-programma: Parallellisme
- 1.6 VF-PROGRAMMA INFORMATIESYSTEMEN 2
1.3. VF programma: DISCRETE STRUCTUREN 3 VF code: TUE.WSK.303.90.25 Programmaleiding: prof.dr. A.E. Brouwer, prof.dr. A.M. Cohen, prof.dr.ir. H.C.A. van Tilborg (Wsk/I), prof.dr.ir. J.P.M. Schalkwijk (E) Wetenschapsgebied ISN: 1204, 1299 Discrete Wiskunde, 3325 Wetenschapsgebied NWO: P110, T 180 Toepassingsgebied NABS: N025 A. Eindige meetkunde 1. (Eindige) meetkunde en designtheorie
In samenwerking met Simeon Ball zijn ook nieuwe grenzen afgeleid voor dubbele blocking sets in Desarguesische projectieve vlakken. Deze zijn scherp voor vlakken waarvan de orde een kwadraat is. Het begrip t voudige nucleus werd geintroduceerd, en scherpe grenzen hiervoor zijn afgeleid. Als gevolg kon een ca. 30 jaar oud vermoeden van Lunelli en Sce met betrekking tot de afmeting van een maximale (k,n) boog in het affine vlak bewezen worden. In samenwerking met Karoly Bezdek werd een betere bovengrens bewezen voor het Radon getal van het Z3 rooster. In samenwerking met A. Pasini werden de eindige vlag transitieve An.L*.L meetkunden geklassificeerd. Daarbij werd onder andere een meetkundige karakterisatie van de groepen M 23 en M 24 gegeven. In samenwerking met A. Kasikova en D. Pasechnik werden de sporadische groepen McL en Co 3 meetkundig gekarakteriseerd. Uitbreidingen van gegeneraliseerde hexagons werden onderzocht. Dit heeft tot een meetkundige karakterisatie van de groepen en grafen uit de Suzuki keten geleid. Regelmatige lijn systemen waarin twee lijnen een hoek φ maken met cosφ = 0 of ± 1/3 en de connectie met uitbreidingen van near hexagons werden onderzocht. De vlag transitieve uitbreidingen van de klassieke eindige gegeneralizeerde hexagons en duaal polaire ruimten met rang 3 werden geklassificeerd onder een meetkundige conditie. In samenwerking met J. van Bon werden de G2 hexagons gekarakteriseerd. De grafen op de niet absolute punten van een niet ontaarde polariteit waarbij twee punten verbonden zijn dan en slechts dan als ze loodrecht zijn, werden onderzocht. Onder zekere voorwaarden werd bewezen, dat deze grafen lokaal herkenbaar zijn. In samenwerking met J. Abel en C. Colbourn werden nieuwe existentie resultaten voor stelsels onderling orthogonale Latijnse vierkanten verkregen. De spreads in zekere gegeneraliseerde vierhoeken werden onderzocht. 2. Grafentheorie De spectra van grafen van Coxeter en Lie type behorend by een "eindknoop" van het Coxeter diagram werden bepaald. Een nieuwe afstandsreguliere graaf werd geconstrueerd. Voor enkele afstandsreguliere grafen werd de 2 rang van de buurmatrix bepaald. In samenwerking met S.V. Shpectorov werden de afstandsreguliere grafen waarvan de afstandsmatrix precies 1 positieve eigenwaarde heeft, gekarakterizeerd. In samenwerking met C.D. Godsil werd de Euclidische voorstelling van een afstandsreguliere graaf onderzocht. Dit leidde tot het overlijden van een oneindige familie van tot dusverre acceptabele parameters voor afstandsreguliere grafen. In samenwerking met W. Martin worden afstandsreguliere grafen met multipliciteit acht onderzocht. De grafen waarin de puntomgevingen de maximale onafhankelijke verzamelingen zijn werden bepaald. Goede ondergrenzen voor de taaiheid van grafen met gegeven spectrum werden bewezen. 3. Groepentheorie (zie ook onder 1.)
In samenwerking met Nebe en Plesken werden de roosters van Cayley getallen bepaald die invariant zijn onder vermenigvuldiging en onder de werking van groepen isomorf met L(2,8) of L(2,13). In samenwerking met Borovik werd naar voorwaarden gezocht onder welke het aantal conjugatieklassen van inbeddingen van een gegeven eindige groep in een gegeven algebraïsche groep eindig is. Vooruitgang is geboekt bij het onderzoek aan algoritmen voor conjugatieproblemen in Coxetergroepen. B. Coderingstheorie en cryptografie
Voor vier keuzen van woordlengte en dimensie werd de exacte maximum minimum afstand van een lineaire ternaire code bepaald, waarmee het probleem van het vinden van deze minimum afstand voor codes met een woordlengte van ten hoogste 21 opgelost werd. In samenwerking met R.N. Daskalov, D. Berntzen & P. Kemper werden bovengrenzen voor de minimum afstand van lineaire ternaire en quaternaire codes bepaald met behulp van lineaire programmerings technieken. In samenwerking met N.J.A. Sloane werd gewerkt aan onder en bovengrenzen voor de minimum afstand van binaire, ternaire en quaternaire lineare codes. Een begin is gemaakt met het onderzoek naar de maximale minimum Lee afstand van "lineaire" codes over de gehele getallen mod 4. Verschillende constructies van het Leech rooster werden onderzocht. Onderzoek werd gedaan naar "soft decision" decodering van enkele roosters en codes, zoals het Leech rooster, de Golay code en de Nordstrom Robinson code, en efficiëntere decodeeralgoritmen werden afgeleid. Een meetkundige beschrijving werd gegeven van een constructie van Davydov en Drozhzhina Labinskaya voor lineaire overdekkingscodes, en deze constructie werd gegeneraliseerd tot niet noodzakelijk lineaire codes over een willekeurig alfabet. Niet lineaire asymptotisch perfecte codes met overdekkingsstraal 2, en enkele andere codes, werden geconstrueerd. Deze codes leveren een spectaculaire verbetering van parameters op t.o.v. eerder bekende codes. Ook uit de Golay code zijn enkele nieuwe overdekkingscodes geconstrueerd. Een constructie is gegeven voor (d,k) codes die in staat zijn om 1 of meerdere peak shifts te verbeteren. De cardinaliteiten van deze codes zijn beter dan die van tot nu toe bekende codes. Een constructie voor (d,k) codes, die in staat zijn om insertions en deletions van nullen te verbeteren, is gegeven. Binaire array codes zijn beschreven voor het verbeteren van bursts van insertions en deletions. Geanalyseerd is welke foutenpatronen nog meer verbeterd kunnen worden dan die welke gegarandeerd worden door de minimum afstand van een code, als majority logic decoding wordt gebruikt bij projectieve meetkunde codes. Een methode is gevonden om het verlies van synchronizatie met een (d,k) beperkte rij te herstellen. I.h.b. wordt aangetoond dat voor (1,7) beperkte rijen tot en met drie verloren of erbij gekomen symbolen gecorrigeerd kunnen worden (met IBM Almaden). Een nieuwe, efficiëntere methode is gevonden om binaire gegevens om te zetten in 0/1 rijtjes met begrenzingen aan de partiele sommen. Mogelijkheden om hierbij fouten te corrigeren zijn hierbij aangegeven (met IBM Almaden). Het minimale aantal binaire vectoren, v 1, ..., v k, dat nodig is om een willekeurige binaire vector w, met behulp van de Hamming afstanden d H (v 1 ,w), ... , d H (v k ,w) te representeren is onderzocht. 1A. Algebraisch meetkundige coderingstheorie De MDS codes van minimumafstand 5 die een 2 foutenverbeterend paar hebben werden gekarakteriseerd. De grens van Roos voor cyclische codes werd gegeneraliseerd naar algemene lineaire codes. "Majority coset decoding" voor AG codes werd gegeneraliseerd tot decodering van algemene lineaire codes door middel van een foutenverbeterend array. Voor deze arrays is de zogenaamde "Feng Rao" grens ingevoerd die voor AG codes vaak beter is dan de grens van Goppa. De zgn. schuifgrens voor cyclische codes is gegeneraliseerd naar algemene lineaire codes met een foutenverbeterend array. Zeta functies in twee variabelen voor krommen over een eindig lichaam werden bestudeerd. Het gemiddelde gewichtsverdelingspolynoom van AG codes werd bestudeerd. - Het partitie design van een divisoren klassegroep werd onderzocht. Alle mogelijke gewichtsverdelingspolynomen van codes op de Klein kromme werden bepaald. Aurifeulliaanse factorizatie met behulp van zeta functies werd bestudeerd. De relatie tussen de zeta functies van krommen in een overdekking werd onderzocht. Grenzen voor en constructies van MDS codes op hyperelliptische krommen werden gevonden. De Klassegetallen van zekere hyperelliptische krommen werden bepaald. De minimum afstand van zekere codes op hyperelliptische krommen werd bepaald. Maximale bogen op vlakke kromen van geslacht 1 en 2 werden onderzocht. Bogen die invariant zijn onder de actie van PSL(2,q 2) werden onderzocht. Grenzen voor en constructies van bijna MDS codes werden gevonden. 1B. Informatie en communicatietheorie
2. Cryptografie Een verbetering van het McEliece cryptosysteem m.b.v. overdekkingscodes werd beschreven. Een algoritme is gegeven om lange cykels in een De Bruijn graaf efficient aan elkaar te koppelen zodat een volledige De Bruijn rij ontstaat. Daarna zijn de cryptografische merites van deze constructie onderzocht (samen met Philips Crypto). Een uitvoerig onderzoek is verricht naar verschillende aspecten van digitale handtekeningen: hun belang, de voornaamste protocollen, hash funkties, sleutel management en het gebruik van smart cards (samen met MBLE). Een flexibele beveiligingsstructuur is voorgesteld voor het uitvoeren van allerlei applikaties met van de gebruiker afhankelijke beveiligingseisen via een breed toegankelijk netwerk (samen met Van Lanschot). Onderzoek is verricht naar een constructie van optimale coderingsschema's voor wire tap channel II. The binary symmetric broadcast channel with confidential messages with tampering resp. public feedback zijn onderzocht. Het capaciteitsgebied van een klasse broadcast channels with confidential messages is bepaald. Nieuwe bovengrenzen voor de optimal information rate van perfect secret sharing schemes zijn gevonden m.b.v. een nieuw ontwikkelde methode. Een nieuwe practische constructie voor perfect secret sharing schemes, direkt gerela- teerd aan lineaire codes, is ontwikkeld. Het probleem van het vinden van optimale perfect secret sharing schemes gebaseerd op samenhangende grafen met ten hoogste vijf punten is hiermee opgelost. B. Samenwerkingen Samenwerking op het gebied van de eindige meetkunde, grafentheorie en groepentheorie bestaat met J. Abel (St. Ives, NSW), S. Ball (London), D. Berntzen (Muenster), K. Bezdek (Budapest), S. Bezrukov (Moskou), J. van Bon (Rome), A. Borovik (Manchester), R. Calderbank (Bell Labs), P.J. Cameron (London), C. Colbourn (Waterloo), B.N. Cooperstein (Santa Cruz), R.N. Daskalov (Bucarest), D. Fon der Flaass (London), G. van der Geer (Amsterdam), C.D. Godsil (Waterloo), W.H. Haemers (KUB), J.I. Hall (Michigan), J.P. Hansen (Aarhus), R. Hill (Salford), J.W.P. Hirschfeld (Sussex), T. Hoholdt (Kopenhagen), J.E. Jensen (Kopenhagen), P. Johnson (Eindhoven), A. Kasikova (Delaware), P. Kemper (Muenster), G. Lachaud (Marseille), H. van Maldeghem (Gent), W. Martin (Winnipeg), Th. Meixner (Giessen), K. Metsch (Giessen), E. Moorhouse (Laramie), C. Munuera (Valladolid), D.V. Pasechnik (Perth), A. Pasini (Napels), J.P. Pedersen (Aalborg), S. Sakata (Toyohashi), S.V. Shpectorov (Moskou), A.N. Skorobogatov (Moskou), N.J.A. Sloane (Bell Labs), H. Stichtenoth (Essen), T. Szönyi (Budapest), J.A. Thas (Gent), M.A. Tsfasman (Moskou), S.G. Vladut (Moskou), D. Wales (Caltech, Pasadena) en met tal van andere wiskundigen op meer incidentele basis. 1.4 VF-programma: PROGRAMMEREN VF-code: TUE.INF.301.90.26 Programmaleiding: dr.ir. C. Hemerik, prof.dr. R.C. Backhouse, dr. A. Kaldewaij, dr. R.R. Hoogerwoord Wetenschapsgebied ISN: 1101, 1203, 3304 Wetenschapsgebied: P110 Toepassingsgebied: N076, N070, N10
Dit project behelst onderzoek naar de fundamentele aspecten van programmeren. Hieronder vallen het ontwikkelen van technieken voor en het evalueren van diverse programmeerstijlen (relationeel, functioneel, logisch, sequentieel, parallel, object georiënteerd), het ontwikkelen van geschikte notaties voor specificaties en programma's, en het formuleren van heuristieken voor het ontwerpen van (correcte en efficiënte) programma's. Ook het redeneren over en het ontwerpen van ingewikkelder datastructuren is onderwerp van onderzoek. Tenslotte vormt de ontwikkeling van een op de relationele calculus gebaseerde theorie van datatypen een belangrijk onderzoeksthema. Voortgang van het onderzoek
Nederpelt en Kamareddine (University of Glasgow; voor twee maanden gast van de vakgroep Informatica) hebben hun werk op het gebied van de fijnstructuur van de getypeerde lamda calculus voortgezet. Van hun eerdere werk zijn twee artikelen geaccepteerd voor publicatie. Hun huidige samenwerking betreft de semantiek van de fijne lambda calculus [Kamareddine en Nederpelt] en twee versies van uitbreiding van het reductiebegrip. Ze hebben bovendien een boek op stapel gezet over de fijnstructuur van de getypeerde lambda calculus, waarvan de helft in voorlopige versie af is. Hemerik heeft een user interface en type checking algoritmen geimplementeerd voor het systeem "Lolita", waarmee voor een grote klasse van PTS'en goedgetypeerde termen geconstrueerd kunnen worden. Samen met Nederpelt en Kamareddine werkt hij aan een boek over typentheorie. Poll en mevr. Severi hebben hun onderzoek van definities in Pure Type Systems voltooid [Poll en Severi]. Poll heeft voor een belangrijke klasse van Pure Type Systems een syntaxgestuurd type checking algoritme ontworpen en correct bewezen [Poll]. Poll zal naar verwachting in Juni 1994 promoveren op het onderwerp "A Programming Logic based on Type Theory". Nieuw op de faculteit zijn de oio Bloo, werkzaam sinds 1 10 93 op het NWO/SION project "Pragmatics of lambda calculus reduction", en de aio Laan, die sinds 1 11 93 werkt aan het SOBU project "De ontwikkeling van het typebegrip". Beiden worden begeleid door Nederpelt; Laan ook door De Swart (KUB).
"A Semantics for a Fine Lambda Calculus with De Bruijn indices", Computing Science Note 93/28, TUE, 1993.
"A Typechecker for Bijective Pure Type Systems", Computing Science Note 93/22, TUE 1993.
" Pure Type Systems with Definitions", Computing Science Note 93/24, TUE, 1993.
Een conferentiebijdrage van Watson en Zwaan over de in 1992 geconstrueerde taxonomie van keyword pattern matching algoritmen is op de conferentie CSN'93 (Computing Sience in The Netherlands) bekroond met een "Best Paper Award" [Watson en Zwaan]. Van de algoritmen uit deze taxonomie is een "benchmark" uitgevoerd. Daaruit bleek o.a. dat het nauwelijks bekende algoritme van Commentz Walter in veel gevallen betere resultaten oplevert dan de populaire algoritmen van Aho Corasick en Boyer Moore. Over deze benchmark zal begin 1994 gerapporteerd worden. Door mevr. Van Geldrop is m.b.v. een originele combinatie van programmeermethoden een nieuwe afleiding gevonden van de Aho Corasick algoritmen [Van Geldrop]. Het taxonomie onderzoek heeft zich in 1993 geconcentreerd op algoritmen voor constructie en minimalisatie van eindige automaten. Dergelijke algoritmen worden veel toegepast bij de constructie van compilers, in text editors, file searching, patroonherkenning, verificatiesystemen, etc.. De resultaten zijn vastgelegd in een tweetal taxonomieën: "A Taxonomy of Finite Automata Construction Algorithms" [Watson1]. Deze taxonomie beschrijft in een uniform kader een groot aantal algoritmen voor de constructie van eindige automaten bij reguliere expressies. Sommige van deze algoritmen zijn klassiekers, zoals Thompson's algoritme en Brzozowski's derivatives. Andere, zoals DeRemer's algoritme, zijn nauwelijks bekend maar blijken toch heel goede resultaten te geven. In de taxonomie worden al deze algoritmen met elkaar in verband gebracht. Tevens zijn enige nieuwe algoritmen gevonden. Een belangrijk resultaat is het verband dat is gelegd tussen de algoritmen van McNaughton Yamada, Glushkov, Berry Sethi en Aho Sethi Ullman. Los van de taxonomie is van deze groep algoritmen ook een rechtstreekse afleiding gegeven in [Ten Eikelder en Van Geldrop] "A Taxonomy of Finite Automata minimization Algorithms" [Watson2] Deze taxonomie beschrijft een aantal algoritmen voor minimalisatie van eindige automaten. Ook hier is als nevenproduct van de classificatie een nieuw algoritme gevonden. Verwijzingen naar publicaties H.M.M. ten Eikelder en H.P.J. van Geldrop; "On the Correctness of Some Algorithms to Generate Finite Automata for Regular Expressions". Computing Science Note 93/32, TUE, 1993. R.van Geldrop, "Deriving the Aho Corasick algorithms: a case study into the synergy of programming methods", Computing Science Note 93/01, TUE, 1993.
"A Taxonomy of Finite Automata Construction Algorithms" Computing Science Note 93/43, TUE, 1993. B.W.Watson; "A Taxonomy of Finite Automata Minimization Algorithms" Computing Science Note 93/44, TUE, 1993. B.W.Watson en G.Zwaan; "A Taxonomy of Keyword Pattern Matching Algorithms" Procs. CSN'93 (Computing Science in The Netherlands); H.A.Wijshoff(ed.); pp.25 39.
Er is een methode ontworpen om stellingen in de tralietheorie om te zetten in stellingen in de categorietheorie. In deze methode wordt categorietheorie opgevat als constructieve tralietheorie waarin de (constructieve) bewijzen van stellingen coherent zijn. De methode is met succes toegepast op het afleiden van isomorphieën en simulaties tussen datatypen. Een eerste versie hiervan is gepresenteerd op een workshop in Oxford. Samen met de universiteit van Oxford is een studie begonnen naar de ontwikkeling van generieke algoritmen; zulke algoritmen zijn geparameteriseerd naar datatypen [0]. In samenwerking met de universiteiten van Oxford en Pennsylvania is een theorie ontwikkeld die de basis legt voor toepassingen van zulke algoritmen [1]. Met behulp van het begrip factor [2] is een begin gemaakt met de integratie van de relationele theorie van datatypen en de bekende weakest precondition semantiek voor sequentiële programma's. Dit heeft geleid tot een verbeterde formulering van recursie [3]. Verder is een verkennend onderzoek gestart naar de toepasbaarheid van de methoden uit de relationele calculus op het gebied van databases en informatiesystemen. De resultaten van eerder verricht onderzoek naar typen met wetten en typen met restricties zijn aanzienlijk verbeterd; waar deze twee soorten typen eerder als verschillend werden beschouwd, is er nu een verband tussen aangebracht [4]. Een nieuwe, calculationele formulering van inductie heeft geleid tot een generalisatie van het begrip tot reductie relatief aan een datatype. Dit algemenere begrip kan worden gebruikt om uniciteits en eindigingsargumenten effectief te construeren [5].
[1] P. Freyd, P. Hoogendijk, O. de Moor. Membership of datatypes. (submitted to LICS) [2] R. Backhouse, H. Doornbos, P. Hoogendijk. A class of commuting relators. (presented at the ERCIM workshop on Development and Transformation of Programs, Nancy) [3] R. Backhouse, J. van der Woude. Monotype factors and demonic operators. (MSCP, 1993) [4] E. Voermans, J. van der Woude. A perspective on types with laws. (presented at Oxford) [5] R. Backhouse, H. Doornbos. Induction and recursion on datatypes. (presented at Oxford) Algoritmen en datastructuren: Er is grote vooruitgang geboekt met het gestructureerd afleiden van datastructuren en bijbehorende programma's. De centrale datastructuur hierbij is de leaf tree en een belangrijk begrip bij het afleiden van hierop betrekking hebbende programma's is decomponeerbaarheid. De theorie wordt toegepast op bestaande, tot nu toe niet bevredigend opgeloste, problemen. Op deze manier is een optimale (nog niet bekende) oplossing verkregen voor het union of intervals probleem [0]. Ook voor datastructuren zoals flexible arrays blijkt de methode toepasbaar. Een algemene behandeling van het gebruik van leaf trees is opgenomen in [1]. Het onderzoek richt zich nu op toepassingen op ingewikkeldere, tweedimensionale problemen uit de computational geometry. Verder is onderzoek gedaan op het gebied van graafalgoritmen. Hierbij worden klassen grafen onderzocht die voor in het algemeen NP moeilijke problemen toch polynomiale oplossingen toelaten. Een interessante klasse blijkt die der grafen met begrensde boombreedte te zijn [2,3,4].
[3] T. Kloks, H. Bodlaender, H. Müller, D. Kratsch. All you need are the minimal separators. (Proc. of the First Annual Eur. Symp. on Algorithms, LNCS 726(1993), pp.260 271) [4] T. Kloks, D. Kratsch. Finding all minimal separators of a graph. (to appear in Proceedings STACS'94) Diverse programmeerstijlen: Op het deelgebied functioneel programmeren is de aandacht vooral uitgegaan naar de voltooiing van een nette, niet conventionele behandeling van de wiskundige fundamenten van het functioneel programmeren. Als gevolg hiervan zijn enige in dit gebied gangbare opvattingen als foutief ontmaskerd [0]; aan dit onderzoek is een caputcollege gewijd. Samen met een afstudeerder is verder gewerkt aan het afleiden van (sequentiële) implementaties van de functionele taal. Wegens de omvang en moeilijkheid van dit onderzoek is voortzetting hiervan door een promovendus zeer wenselijk. Het ontwikkelen van een op de Owicki Gries theorie gebaseerde discipline voor het afleiden van parallelle programma's verloopt voorspoedig. Het werk van een afstudeerder heeft tot een publicatie [1] over dit onderwerp geleid. Thans richt de aandacht zich vooral op het formuleren van hanteerbare regels voor het houden van voortgangsbeschouwingen. Op het deelgebied sequentieel programmeren zijn regels voor het rekenen met procedureaanroepen ontwikkeld en gepubliceerd [2]. Verder zijn algemeen toepasbare stellingen voor het omzetten van diverse vormen van recursie in iteratie afgeleid [3]. Een studie naar de semantiek van partieel gedefinieerde expressies heeft aangetoond dat bij programma afleidingen probleemloos met zulke expressies kan worden gerekend [4]. [0] R.R. Hoogerwoord. On the foundations of functonal programming: a programmer's point of view. (Computing Science Note 94/, to appear) [1] P.D. Moerland. Exercises in multiprogramming. Computing Science Note 93/07) [2] A. Bijlsma. Calculating with procedure calls. (IPL 46, 1993, pp.211 217) [3] L. de Vries, A. Kaldewaij, R.R. Hoogerwoord. Elimination of infix recursion. (submitted to IFIP Working Conference 1994) [4] A. Bijlsma. Quasi boolean equivalence. (IPL 45, 1993, pp.243 247) Overzicht van samenwerkingen In het kader van het SION project "Typed Lambda Calculi" wordt samengewerkt met KUN (Barendregt) en RUU (Van Dalen). De TUE groep neemt via KUN deel aan het HCM project, een samenwerkingsverband tussen een aantal Europese universitaire onderzoeksgroepen op het gebied van getypeerde lambda calculi. Relatie met (toekomstige) onderzoeksscholen Programmatuurkunde (i.o.) 1.5. VF-programma: Parallellisme VF-code: TUE.INF.302.90.26 Programmaleiding: prof.dr. M. Rem, prof.dr. J.C.M. Baeten Wetenschapsgebied ISN: 1101, 1203, 3304 Wetenschapsgebied NWO: P110 Toepassingsgebied NABS: N076, N077, N070, N10
1. Ontwerp en implementatie van parallelle programma's. 2. Specificatie, verificatie en reïficatie van parallelle systemen
1.1 Ontwerpmethoden (afleiden van parallelle programma's uit formele specificaties) 1.2 Netwerk-implementaties (implementeren van parallelle programma's op processornetwerken) 1.3 VSLI-implementatie (implementeren van parallelle programma's als vertragings ongevoelige schakelingen) Project 2 houdt zich bezig met de concurrency theorie, met name de specificatie, verificatie en reïficatie van parallelle of gedistribueerde systemen m.b.v. formele methoden. Het project bestaat uit twee deelprojecten: 2.1 Assertionele methoden. 2.2 Algebraïsche methoden. In beide deelprojecten staat de theorie van concurrente en tijdkritische systemen centraal. In deelproject 2.1 wordt ook aandacht besteed aan betrouwbaarheid en foutbestendigheid van systemen. Voortgang van het onderzoek Project 1: Ontwerp en implementatie van parallelle programma's Deelproject 1.1: Ontwerpmethoden De nieuwe methode voor het ontwerpen van parallelle programma's, welke gebaseerd is op het in 1992 verschenen proefschrift van P. Struik, is in het verslagjaar verder uitgewerkt. Hij wordt thans ook gebruikt in het onderwijs; hiervoor wordt een overzicht van de methode (`Lecture Notes in Parallel Programming') geschreven. Het door NWO gesteunde onderzoek naar het ontwerpen van onregelmatige programma's, zoals we die bijvoorbeeld in besturingssoftware tegenkomen, is met de verschijning van het proefschrift van G.J.P. Koster afgerond. De semantiek van deze programma's is vastgelegd met behulp van het enabling model van Kloosterhuis. Dit resultaat is een van de produkten van de succesvolle samenwerking met de vakgroep Produk tietechnologie en automatisering van de faculteit Werktuigbouwkunde. In het verslagjaar is ook het proefschrift verschenen van J.M. van de Mortel Fronczak. Hierin wordt voor tracetheorie een interleaving model ontwikkeld dat onderscheid maakt tussen nondeterminisme en parallellisme. Ook is het model uitgebreid met het begrip fairness. Deelproject 1.2: Netwerk implementaties In het verslagjaar is P.A.J. Hilbers, werkzaam bij het Shell laboratorium in Amsterdam, benoemd tot deeltijdhoogleraar op het gebied `Industriële Toepassingen van Parallel Rekenen'. De samenwerking met A.P.J. Jansen van de vakgroep Anorganische Chemie en Katalyse (Fac. Scheikundige Technologie) op het gebied van de moleculaire dynamica is verder voortgezet. Vanuit de sectie PA wordt deze samenwerking uitgevoerd door J.J. Lukkien. Het drukke gebruik van het transputersysteem heeft de sectie ertoe gebracht om te zien naar een tweede systeem, zodat produktieruns kunnen worden gescheiden van het onderwijs en onderzoekgebruik. Met subsidie van het IVO is een systeem uit St Louis verworven, dat thans wordt geïnstalleerd. Deelproject 1.3: VLSI implementaties Dit deelproject is grotendeels uitgevoerd binnen het ESPRIT OMI project EXACT, waarin o.a. wordt samengewerkt met Philips (Nat. Lab.), IMEC (te Leuven) en de universiteit van Manchester. Doel van het project is de (industriële) toepasbaarheid te onderzoeken van vertragings ongevoelige schakelingen. In dit kader zijn twee onderdelen van de DCC (Digital Compact Cassette) speler herontworpen als vertragingsongevoelige chips. De nieuwe onderdelen bleken functioneel (en maken muziek) en liepen op een aanmerkelijk lager vermogen dan de originele onderdelen. Verder is er gewerkt aan een `single rail back end' (waarvan een verdergaande reductie van vermogen wordt verwacht), schakelingen voor vermenigvuldigen, en interfaces voor RAM geheugens. Het onderliggende model van vertragingsongevoelige schakelingen (het DI Model) is uitgebreid met een structuur waardoor ook voortgangseisen kunnen worden vastgelegd. Hierover wordt binnenkort gerapporteerd in het proefschrift van T. Verhoeff. In het verslagjaar is het proefschrift van W.H.F.J. Körver verschenen. Hierin wordt een discreet switch level model gepresenteerd voor CMOS schakelingen. Het betreft een hiërarchisch model dat gebaseerd is op tralietheorie. Het werk aan de silicon compiler VOICE, dat voornamelijk wordt uitgevoerd binnen de ontwerpersopleiding Technische Informatica, vordert goed. Hierdoor kunnen schakelingen nu zowel in de door Philips ontwikkelde taal Tangram als in de lokaal ontworpen taal VOKEL worden beschreven. Project 2: Specificatie, verificatie en reïficatie van parallelle systemen Deelproject 2.1: Assertionele methoden Het interface refinement werk van Gerth en Kuiper heeft in een tweede, simpeler versie geresulteerd. Op basis hiervan is een versimpeld bewijs voor een sequentieel consistent geheugen protocol geconstrueerd (CSN 93/47). Dit bewijs is onderdeel van een ESPRIT/BRA REACT deliverable over verificatie van sequential consistency waarvoor Gerth als editor is opgetreden. Deze deliverable zal als special issue in Distributed Computing verschijnen. Gerth heeft samen met Dams en prof. Grümberg (Technion) gewerkt aan de partitionerings technieken voor de automatische verificatie van programma's m.b.t. ACTL. Samen met prof. Damm (Oldenburg) wordt in de context van het ESPRIT FORMAT project gewerkt aan de implementatie van deze technieken in een VHDL model checker. Hooman heeft gewerkt aan toepassingen van zijn assertionele methode voor de specificatie en verificatie van gedistribueerde real time systemen. In het kader van een mogelijke mechanische ondersteuning van het formalisme is er gewerkt met de interactieve proof checker PVS (Prototype Verification System). Verder is de methode toegepast op een aantal voorbeelden, zoals real time protocollen en hybride systemen waarin continue componenten een rol spelen. Bovendien is in de context van hybride systemen samengewerkt met J. Vain (Tallinn) en is met Y. Lahkneche (Kiel) een artikel geschreven over een combinatie van Metric Temporal Logic en de Duration Calculus. Betreffende protocollen is bestudeerd hoe het formalisme uitgebreid kan worden zodat ook fout tolerante real time protocollen geverifieerd kunnen worden. Dit heeft geleid tot een artikel met P. Zhou over de compositionele verificatie van een atomic broadcast protocol. Daarnaast is met Zhou gewerkt aan bewijssystemen voor real time versies van Temporele Logica, resulterend in het proefschrift van Zhou. Het gecombineerde SION/STW project "foutbestendigheid" is succesvol afgesloten. In het kader van dit project werd door J. Coenen samenwerkt met de groep van J. Vytopil (KU Nijmegen). Samenwerking tussen Hooman en Schepers heeft geleid tot een aantal artikelen over een trace based formalisme voor fout tolerante systemen. Huizing heeft zich beziggehouden met het ontwerpen van een unificerend model voor de belangrijke talen voor Concurrency, teneinde dit te gebruiken voor de bouw van een front end voor verificatietools. Verder was hij betrokken bij het modelleren van industriële specificatie tools, zowel bij een publicatie als het voorbereiden van een internationaal onderzoeksproject op dat gebied. Kuiper en Penczek stelden een state of the art overzicht samen van de verbanden tussen temporele logica's en trace theorie, resulterend in een bijdrage van een boek ("The book on traces, ed. V. Diekert, G. Rozenberg). Penczek, Kwiatkowska (Leicester) en Peled (AT&T), onderzochten en rapporteerden karakteriseringen van partiële orde temporele logica eigenschappen. Deelproject 2.2.: Algebraïsche methoden In het onderzoek van Baeten is de modellering van tijd in ACP nog steeds belangrijk, getuige een promotie (6), een nieuw artikel over de modellering van urgente acties (3) en de aanstelling van een nieuwe oio (Vereijken) op dit gebied. Daarnaast staat de relatie van ACP met andere concurrency theorieën zeer in de belangstelling, met name de relatie met non interleaving theorieën zoals Petrinetten (1, 2), de relatie met CCS, CSP (4) en met trace theorie (5). In 1993 verscheen het boek "Algebraic specification of communication protocols" waarvan Mauw (samen met G.J. Veltink) editor is. Het onderzoek aan Leader election protocollen werd afgesloten met een intern rapport. In samenwerking met Philips heeft Mauw onderzoek gedaan naar semantieken voor Interworkings en Message Sequence Charts, hetgeen tot verschillende publikaties heeft geleid. Dit werk zal resulteren in een formele, door de ITU TS geaccepteerde standaard. De ontwikkeling van de PSF Toolkit, een serie software tools ter ondersteuning van het ontwerp van parallelle systemen, is momenteel gericht op het implementeren van een efficiënt algoritme voor het automatische verifiëren van correctheid. Het werk aan de PSF Toolkit geschiedt in samenwerk- ing met J.C. Mulder, M. van Wijk en P. Peters. Verhoef schreef enkele artikelen over het gebruik van het format van definities van de operationele semantiek van een taal. Zo kan dit gebruikt worden om stellingen te bewijzen over de congruentie eigenschappen van bisimulatie, over de conservativiteit van taaluitbreidingen, en over de compleetheid van een axiomatisering. Bol schreef een artikel over het gebruik van temporele logica bij real time ACP. Verder hield hij zich bezig met het automatisch checken van bewijzen, met gebruikmaking van het software tool COQ. Blanco werkte verder aan datatypen in procesalgebra, en houdt zich nu bezig met beslisbaar heidsresultaten. Vereijken analyseerde een eerste protocol in ACP met tijd. 1). Baeten, J.C.M.: The total order assumption. In: Proceedings First North American Process Algebra Workshop, Stony Brook, NY, 1992; S. Purushothaman, A. Zwarica, (eds.), Workshop in Computing, Springer Verlag 1993, pp. 231-240. 2). Baeten, J.C.M.; Bergstra, J.A.: Non interleaving process algebra. In: Proceedings CONCUR'93, Hildesheim; E. Best (ed.), Lecture Notes in Computer Science 715, Springer Verlag 1993, pp. 308-323.
Real time process algebra with infinitesimals. Rapport P9325, vakgroep Programmatuur, Universiteit van Amsterdam 1993. Rapport CSN 93/34, vakgroep Informatica, EUT, Eindhoven, 1993, pp. 39. 4). Baeten, J.C.M.; Bergstra, J.A.: On sequential composition, action prefixes and process prefix. Rapport P9305, Vakgroep Programmatuur, Universiteit van Amsterdam 1993. Rapport CSN 93/14, vakgroep Informatica, EUT, Eindhoven, 1993, pp. 21. 5). Baeten, J.C.M.; Bergstra, J.A.; Bol, R.N.: A real time process logic. Rapport P9309, Vakgroep Programmatuur, Universiteit van Amsterdam, 1993. Rapport CSN 93/15, Vakgroep Informatica, EUT, Eindhoven, 1993, pp. 31. 6). Klusener, A.S.: Models and axioms for a fragment of real time process algebra. Promotoren: prof.dr. Baeten, J.C.M; prof.dr. Bergstra, J.A.. Eindhoven, 1993, pp. 216. Samenwerkingen. . Met Philips, UT, UvA op het gebied met Leader election protocollen. . Met Philips op het gebied van Interworkings. . Met Siemens (München) op het gebied van Message Sequence Charts. . In het kader van ESPRIT BRA project CONCUR 2 no. 7166 wordt samengewerkt met University of Aalborg (Denmark), CWI, University of Edinburg (UK), INRIA Sophia Antipolis (France), University of Oxford (UK), University of Sussex (UK), Swedish institute for Computer Science (Sweden), IMAG Grenoble (France), ECRC (Germany), Sharp Laboratory (UK), Chalmers Technical University (Sweden). . In het kader van ESPRIT research project REACT no. 6021 wordt samengewerkt met University of Liège (Belgium), Foundation of Research and Technology Hellas (Greece), Swedish Institute of Computer Science (Sweden), University of Oxford (UK), University of Kiel (Germany), Institute National Polytechnique de Grenoble (France). . Logica & Informatiesystemen interuniversitaire werkgroep met KUB. . De vakgroep Informatica werkte samen met CWI en RUL in het Landelijk Project Concurrency (SION) en in het NFI project, REX. Deze samenwerking wordt voortgezet in het in 1994 te starten aandachtsgebied HOOP. . Samenwerking vindt plaats met UvA en RUL in het NFI projekt TRANSFER. . Op het terrein van procesalgebra wordt nauw samengewerkt met UvA, CWI en UU.
Wetenschapsgebied NWO: P170, P160, S190 Toepassingsgebied NABS: N083, N076, N070, N10
1.1 Ontwerpmethodologie voor informatiesystemen 1.2 Menskundige en organisatie-aspecten van de automatisering 1.3 Informatiesystemen in produktie en logistiek 1.4 Computer Integrated Manufacturing 2. Informatiesystemen vanuit informatica perspectief 2.1 Formele specificaties 2.2 Robuuste Technische Informatiesystemen 2.3 Database systemen 2.4 Computergraphics en user interface management systemen 2.5 Kennissystemen 3. Informatiesystemen vanuit besliskundig perspectief Voortgang van het onderzoek Algemeen Project 1: Informatiesystemen vanuit bedrijfskundig perspectief Zie bijdrage van de faculteit Bedrijfskunde Project 2: Informatiesystemen vanuit informatica perspectief Deelproject 2.1: Formele specificaties. Dit betreft het onderzoek in het kader van het ExSpect project. ExSpect is een specificatie formalisme gebaseerd op gekleurde Petri netten met tijd, een functionele taal en een binair datamodel. Enerzijds is er een fase in het onderzoek afgesloten met een proefschrift op het gebied van de integratie van proces- en datamodelleringsfaciliteiten binnen ExSpect en een boek, waarin van Hee het onderliggende formalisme en de methoden van toepassing daarvan uiteenzet. Er wordt daarnaast nog gewerkt aan de theorie voor hiërarchische Petri netten. Het PROOFS-projekt is afgerond met de oplevering van een workbench voor het opstellen en valideren van formele specificaties op basis van ExSpect. Anderzijds zijn er op onderzoeksgebied nieuwe richtingen ingeslagen met aan de ene kant het onderzoek naar generieke systeemcomponenten en aan de andere kant het onderzoek naar de relaties met andere formalismen voor het specificeren van systemen zoals proces algebra's. De toepassing van ExSpect in tal van praktijksituaties gaat onverminderd voort. Deze activiteiten leveren het basismateriaal voor standaardcomponenten voor specifieke toepassingsgebieden, zoals workflow management. Deze activiteiten leveren ook waardevolle expertise op voor de aanpassing van de theoretische formalismen aan wat door de praktijk gevraagd wordt. Publicaties binnen dit deelproject: Verkoulen, P.A.C.: Integrated Information Systems Design - An Approach Based on Object-Oriented Concepts and Petri Nets. Promotoren: prof.dr. K.M. van Hee; prof.dr. J.J.E.L. Paredaens. Eindhoven, 1993, pp. 184. Aalst, W.M.P. van der: Interval Timed Coloured Petri Nets and their Analysis. In: Application and Theory of Petri Nets 1993, M.A. Marsan (ed.), Springer Verlag, Lecture Notes in Computer Science, Vol. 691, 1993, pp. 453-472.
Specification and simulation with ExSpect. In: Functional programming, concurrency simulation and automatic reasoning. Lecture Notes Computer Science, Vol. 693, 1993, pp. 296-328. Hee, K.M. van; Voorhoeve, M.: Vergelijkende studie dienstregelingen generatoren. DONS-rapport voor NS, 1993, pp. 12.
Improving Software Design Quality with ExSpect: an application of CASE-based prototyping in real-world situations. Proceedings CASE'93 workshop, IEEE computer society press, 1993, pp. 174-177.
Modelling and Analysis of Complex Logistic Systems. In: Integration in Production Management Systems; H.J. Pels, J.C. Wortmann (eds.), Elsevier Science Publishers, Amsterdam, IFIP Transactions, Vol. B-7, 1992, pp. 277-292.
Project 2.2.1: DEDOS (Dependable Distributed Operating System) Executie-omgeving In het afgelopen jaar is een begin gemaakt met een op de voorstudies gebaseerde realisatie van een DEDOS prototype: De object georiënteerde implementatie van het Eindhoven Multiprocessor Systeem EMPS dat als kernel van DEDOS dient, is afgesloten met de promotie van G.J. van Dijk. In hechte samenwerking met de faculteit Technische Natuurkunde wordt het EMPS nu toegankelijk gemaakt voor studenten, zodat de resultaten van gezamenlijke projecten gebaseerd op het EMPS voor beiden faculteiten beschikbaar komen. De volgende algoritmen zijn verder uitgewerkt: . Hiërarchische communicatie protocollen. . Het hiërarchische clock synchronisatie algoritme. . Hiërarchische lidmaatschap algoritmen. . De gedistribueerde DEDOS concurrency control algoritmen. Daarmee zijn alle onderdelen van de protocol-hiërarchie van de DEDOS integratielaag uitgewerkt. De aandacht bij de ontwikkeling van de communicatie protocollen en andere noodzakelijke DEDOS onderdelen begint nu meer en meer gericht te worden op de prestatie van de verschillende software onderdelen afhankelijk van hun onderlinge wisselwerking. Er worden verschillende alternatieven bekeken om tot de meest efficiënte oplossing te komen. De samenwerking met RUU, UvA en CWI in het kader van het NFI project ALADDIN op het gebied van gedistribueerde algoritmen is verder versterkt. Gedurende wekelijkse bijeenkomsten vertellen aio's en oio's over hun huidige werk en recent gepubliceerd werk van anderen. De bijdrage van de de sektie TT concentreert zich op algoritmen die tijdsfouten van synchrone gedistribueerde systemen tolereren. Dit onderwerp zal het hoofdthema zijn van de toekomstige promotie van D. Alstein. In het kader van het EEG BRITE EURAM project IMAGES 2000 is in samenwerking met de Europese civiele vliegtuigindustrie een onderzoek gestart naar de betrouwbaarheids en beschikbaarheidsaspecten van een modulair "fly by wire" controle systeem voor een toekomstige generatie van vliegtuigen. Het voor DEDOS ontwikkelde lidmaatschap algoritme bleek met enige modificaties gebaseerd op de communicatie faciliteiten binnen een vliegtuig, bijna direct toepasbaar te zijn. In samenwerking met de vakgroep I&T van de faculteit Bedrijfskunde is een project uitgevoerd met het oogmerk een object-georiënteerde modelleermethode voor de controle software van produktie besturingssystemen te ontwikkelen. Een generiek model voor dit soort systemen is ontwikkeld dat de voordelen van object oriëntatie zoals flexibiliteit en herbruikbaarheid realiseert. Een publikatie is in voorbereiding. Het project is uitgevoerd met medewerking van het Cooperative Engineering Center van Digital te Nieuwegein alwaar zich een geschaalde modelfabriek bevindt. In een aanverwant project is gekeken naar een object georiënteerde scheduling architectuur voor produktie systemen. Een hiervoor ontwikkeld model wordt het komende jaar geïmplementeerd en op zijn effectiviteit getest. Dit project wordt uitgevoerd in samenwerking met de faculteit elektrotechniek en werktuigbouwkunde van de TUE. Een en ander zal worden getest m.b.v. de FALC (Flexibele Automatische Las Cel).
Het afgelopen jaar is verder gewerkt aan het realiseren van de software ontwikkelomgeving voor DEDOS. Verschillende tools zijn (verder) ontwikkeld met name de preprocessor, execution graaf viewer. Ook aan de definitie van de applicatie taal DEAL is gewerkt. De structuur van de bij DEDOS behorende Application Language DEAL is nu zodanig dat de distributie van de verschillende programma onderdelen volledig onzichtbaar wordt voor de programmeur; restricties op parameter types zijn weggevallen. Volgende uitbreidingen betreffen de atomiciteits en synchronisatie faciliteiten van DEAL. Samen met Technische Natuurkunde zijn er tevens studies verricht om te komen tot de specificatie van een object georiënteerde taal ter ondersteuning van natuurkunde experimenten.
Het scheduling model is uitgebreid met een aantal constructies die de herbruikbaarheid van de code bevorderen en die het mogelijk maken inherent parallellisme in een applicatie te benutten. Dit werk is vastgelegd in een New Jersey Institute of Technology (NJIT) CS note. Tevens is een algoritme voor de toekenning van processoren aan processen uitgewerkt en gepubliceerd als een NJIT CS note. Dit algoritme maakt gebruik van heuristieken zoals minimalisatie van de communicatie en de maximalisatie van parallellisme. Er is een begin gemaakt met een algoritme om beads in scheduling blokken te groeperen. Het window scheduling algoritme is verder uitgewerkt en gepresenteerd op de First Workshop on Parallel and Distributed Real Time Systems. Het werk aan scheduling wordt merendeels uitgevoerd door Jack Verhoosel. Een eerste complete versie van de scheduler is binnenkort gereed. Verhoosel is begonnen met het schrijven van zijn proefschrift. Het werk zal in het komende jaar met een promotie worden afgesloten. De samenwerking met Prof. A.D. Stoyenko en Prof. L. Welch van het NJIT is verder geïntensiveerd en zal worden voortgezet. Prof. Welch heeft gedurende de zomermaanden twee maanden aan de TUE doorgebracht, terwijl Prof. Stoyenko een week op de TUE is geweest. Ir. J.P.C. Verhoosel heeft 4 maanden aan het NJIT doorgebracht. De samenwerking heeft geresulteerd in een aantal gezamenlijke publikaties. De samenwerking met de groep van L. Feys en H. Jonkers van het Philips Natlab is verder uitgebouwd. In dit verband wordt de toepassing van statische scheduling technieken voor besturingen van audio en video apparatuur onderzocht. De samenwerking is gerealiseerd met behulp van afstudeerders en een student van de ontwerpersopleiding. Dit werk heeft geleid tot een prototype van een scheduler. Ook deze samenwerking zal worden voortgezet.
In het afgelopen jaar is het onderzoek voortgezet naar een op traces gebaseerd formalisme, dat het exceptionele gedrag van een component als een transformatie van het foutvrij componentgedrag modelleert. Met name is gewerkt aan een bewijssysteem. Dit gebeurde in nauwe samenwerking met de sectie TI. Het bijzondere van dit formalisme is dat het fouten op een abstracte manier modelleert door uit te gaan van het observeerbare communicatie gedrag van componenten: het beschouwt de mogelijke gevolgen van fouten op het observeerbare gedrag, zonder expliciet op die fouten in te gaan. Daardoor is het formalisme compositioneel. Dit jaar is het untimed traces model uitgebreid met een model dat timed traces toelaat om te redeneren over safety eigenschappen van real time systemen. Verder is gewerkt aan de verfijning van een programma met behulp van traces zodat het mogelijk is de zwakste fout hypothese te bepalen waaronder een systeem aan zijn specificaties kan voldoen. Het model is verder uitgebreid om te kunnen redeneren over de toekenning van resources aan programma's. Daarbij is met name de pseudoparallelle uitvoering van meerdere programma's op een processor gemodelleerd. Ook hiervoor is een bewijssysteem uitgewerkt. Het project zal in 1994 afgesloten worden met de promotie van H. Schepers. Er is samengewerkt met: - Digital Equipment Cooperate Engineering Centre, Nieuwegein - Philips Telecommunication , Hilversum - Philips Natlab, Eindhoven en Aachen - Océ Nederland, Venlo - Fokker Aircraft, Amsterdam - Prof. A. Stoyenko en Prof. L. Welch van het New Jersey Inst. of Technology (NJIT) - Prof. K. Ecker van de Technische Universiteit Clausthal - Prof. J. Vytopil (KUN), Prof. M. Joseph (universiteit of Warwick, UK) en met Prof. W.P. de Roever (universiteit Kiel, Duitsland) in het kader van het STW project fouten tolerantie
Het onderzoek in het kader van het GOOD model is voortgezet in twee richtingen. Op het gebied van het onderliggende formalisme is een aantal uitbreidingen onderzocht, zoals PaMal, waardoor een afzonderlijke abstractie-operator overbodig is geworden. Het verband tussen GOOD en visuele logische talen en rule-based talen is onderzocht. Op het gebied van het GOOD-interface (XGOOD) zijn uitbreidingen gerealiseerd voor aanroepen en uitvoeren van GOOD-programma's in andere GOOD-programma's en het bekijken van de resultaten daarvan, met gebruikmaking van het meta-schema. Ook de query-taal zelf is uitgebreid met de mogelijkheid niet grafische condities in te voeren. Dit onderzoek heeft geleid tot een aantal conferentie-bijdragen en rapporten. Het onderzoek naar modellen voor hypertext is verder voortgezet met een accent op de prestaties van dergelijke systemen en het analyseren van gebruikersgedrag met het oog op ondersteuning en anticipatie daarvan. Er is intensief onderzocht wat de relatie is tussen de diverse strategieen van browsing, de faciliteiten die een hypertextsysteem aanbiedt en het herkennen van het hyperdocument. Op basis van dit onderzoek is een prototype-implementatie van een geautomatiseerd zoekgereedschap gemaakt bovenop Mosaic, een browsing-gereedschap voor gedistribueerde hypertexts.
Navigational Search, algoritme voor Mosaic. Intern rapport beschikbaar via ftp.win.tue.nl., 1993.
An Object-Oriented Pattern Matching Language. JSSST, International Symposium on Object Technologies for Advanced Software, Kanazawa, Japan, Lecture Notes Computing Science 742, 1993, pp. 339-355.
GOOD, A Graph-Oriented Database System. Proceedings of SIGMOD, SIGMOD Record, Vol. 22, no. 2, 1993, pp. 505-510.
GOLD: A Graph Oriented Language for Databases. Computing Science Note 93/29, EUT, Eindhoven, 1993, pp. 42.
In het kader van het werk aan grafische algoritmen is door van Overveld tijdens het laatste deel van zijn verblijf in het buitenland gewerkt aan oppervlakte modellerings algoritmen (aan de universiteit van Calgary, Canada, in samenwerking met prof. B. Wyvill en prof. P. Prusinkiewicz) en aan dynamisch gesimuleerde loop beweging (aan de universiteit van Philadelphia, in samenwerking met Hyeongseok Ko). Tevens is, ook in Philadelphia, het werk aan branching structuren voor splines uitgebreid met interactie en animatie i.s.m. Marie Luce Viaud. Over al deze onderwerpen zijn manuscripten ter publikatie aangeboden aan internationale gerefereerde tijdschriften. Terug in Nederland is veel effort gestoken in het beschikbaar maken van de in Amerika en Canada ontwikkelde software op onze eigen werkstation omgeving. Onder andere is hiervoor een generieke user-interface library gebouwd met direct manipulation opties voor gesimuleerde 3 D camera besturing. Ook zijn tools geschreven voor de interactieve specificatie van renderingsattributen en (niet lineaire) geometrische transformaties.
Zoals vorige jaren vermeld, bevindt het zwaartepunt van het computer animatie onderzoek zich thans in het SOBU project 'Dialoogvoering en Kennisopbouw'; uitvoerder is Eric Peeters. Als resultaat van dit werk is de gegeneraliseerde display processor (GDP) operationeel geworden. Peeters is thans begonnen met het schrijven van zijn proefschrift; daarnaast wordt zijn onderzoek aan botsingsdetectie algoritmen nog afgerond. Ook buiten het SOBU project is door van Overveld nog onderzoek verricht op het gebied van dynamische simulatie: dit heeft geleid tot algoritmen voor curved path walking. Tevens is een nieuw formalisme geïntroduceerd om de dynamica van gelinkte rigid bodies te beschrijven. Dat wordt op dit moment door een afstudeerder nader uitgewerkt. Er is samengewerkt met: in SOBU verband: KUB (Tilburg), IPO, secties IS, TI (Eindhoven) advisering: faculteit W, TUE software ondersteuning (GDP): faculteit IO, TUD meldkamer Rijkspolitie, Eindhoven, Centrale Bibliotheek TUE, Computel, Tiel, en Jac van Ham Speelautomaten, Tilburg, in het kader van case studies voor het OOTI vak User Interfaces VU Academisch Ziekenhuis (Amsterdam) Prof. B. Wyvill en prof. P. Prusinkiewicz van de universiteit van Calgary.
De onderzoeksactiviteit zoals beschreven in het voorgaande verslag is in het verslagjaar afgerond, omdat Van Lierop zich full time voor de OOTI-opleiding is gaan inzetten. Er zijn geen nieuwe onderzoeksonderwerpen in de sfeer van user interface opgepakt. Deelproject 2.5: Kennissystemen Project 2.5.1: Decision Support Systems. Dit onderzoek richt zich op drie aspecten: efficiente en robuuste algoritmen voor een zeer ruime klasse van scheduling problemen, grafische user interfaces voor zulke problemen en het flexibel maken van DSS'sen. Aan de algoritmische zijde is vooral gewerkt aan constraint satisfaction technieken technieken en lokale zoekalgoritmen. Nieuwe constraint satisfaction algoritmen zijn ontwikkeld en getoetst aan de hand van theoretische job shop scheduling problemen en een aantal scheduling problemen afkomstig uit de praktijk. Hierbij zijn goede resultaten verkregen, die verwerkt zijn in een vijftal artikelen, die ter publicatie zijn aangeboden en waarvan sommige reeds geaccepteerd zijn. Het werk aan lokale zoekalgoritmen concentreert zich op het ontwikkelen van data en buurruimtestructuren voor parallelle implementaties voor grote instanties van lastige combinatorische optimaliseringsproblemen. Ook hier zijn goede resultaten bereikt die hebben geleid tot een aantal publicaties. Er is verder gewerkt aan periodieke scheduling problemen n.a.v. het vervaardigen van dienstregelingen voor de Nederlandse Spoorwegen met behulp van constraint propagatie technieken. Deze lijn van onderzoek is gestopt toen bleek dat er betere algoritmen voor bestaan; deze zijn nu in onderzoek. Het constraint propagatie onderzoek heeft wel een studie-rapport en een conferentie-bijdrage opgeleverd. Aan de interface zijde is gewerkt aan Petri net representaties van scheduling problemen. Deze representaties kunnen ook gebruikt worden voor het berekenen van schedules d.m.v. prioriteitsregels. Het onderzoek op het gebied van het toepassen van Markov beslissingstheorie op zoek-problemen heeft geleid tot een artikel en een aantal experimentele resultaten. Binnen het kader van flexibele DSS'sen worden de mogelijkheden onderzocht voor het toepassen van deontische logica voor (re)scheduling en planning. Daarnaast wordt onderzoek verricht naar het aanpakken van dergelijke problemen mbv intelligente c.q. lerende algoritmen. Samenwerkingen • Op het gebied van specificatie en simulatie wordt samengewerkt met TNO, in het bijzonder met IPL-TNO/TUE in het kader van het TASTE-project. • Een werkgroep ex art. 89 WWO met de vakgroep Grondslagen der wetenschappen van de faculteit der Wijsbegeerte van de KUB en de vakgroep Informatica van de faculteit der Wiskunde en Informatica van de TUE: de werkgroep Logica en Informatiesystemen. Binnen dit kader valt het promotie-onderzoek van Seljée. • Binnen het 'Human Capital' programma van de EU wordt deelgenomen aan het MATCH (Modelling and Analysis of Time Constrained and Hierarchical Systems)-projekt, samen met de informatica-faculteiten van de universiteiten van Hamburg, Paris VI, Torino, Vienna en Zaragoza. • Op het gebied van de scheduling wordt samengewerkt met Philips Research en, in het kader van het SPIN project PARTOOL met EHT CWI. • Op het gebied van operationele planning is samengewerkt met het RIKS te Maastricht in het kader van een aantal praktijkstudies. • Op het gebied van het ontwikkelen van paralle lokale zoekalgoritmen is samengewerkt met de Universiteit van Leiden in het kader van het MASPAR project en met het rekencentrum van de Universiteit van Amsterdam. • Er is samengewerkt met de Nederlandse Spoorwegen en Bakkenist Management Consultants (dienstrooster planning; DONS-projekt), ESA (satelliet besturing simulatie) en Philips Natlab (software process modelling). De samenwerking bestaat uit het ontwikkelen van modellen en software. • Op het gebied van hypertext is er samenwerking met de Ben-Gurion University of the Negev and de University of Toronto.
Neural networks and the traveling salesman problem. Proceedings of the International Conference on Neural Networks, Amsterdam, 1993, pp. 950-956.
Randomized constraint satisfaction for job shop scheduling and control. In: Proceedings IJCAI, Workshop on Knowledge-Based Production Planning, Scheduling and Control, Chambery, 1993, pp. 251-262. Vaessens, R.J.M.; Aarts, E.H.L.; Lenstra, J.K.: Genetic algorithms in coding theory: a table for A3 (n, d). Discrete Applied Mathematics 45, 1993, pp. 71-87.
A Parallel Lin-Kernighan algorithm for the Traveling Salesman Problem. Proceedings of the International Conference on Parallel Computing (ParCo93), 1993.
A new method for retiming multifunctional processing units. Proceedings of the VLSI93 International Conference on Very Large Scale Integration, Grenoble, France, 1993, pp. 5.2.1 - 5.2.10.
The construction of minimal multilayered perceptrons: a case study for sorting. Neuro Computing 5, 1993, pp. 197-210.
Local search in coding theory. In: A Collection on Contributions in Honour of Jack van Lint; J. Cameron, H.C.A. van Tilborg (eds.), Topics in Discrete Mathematics 7, North Holland, 1992, pp. 11-18.
In 1993 zijn de onderzoekactiviteiten vanuit de groepen discrete optimalisering en stochastische besliskunde met kracht voortgezet. Verschillende samenwerkingsverbanden met andere participanten in dit VF-programma zijn opgestart dan wel versterkt. Het onderzoek op het gebied van neurale netwerken heeft in de verslagperiode een eerste afronding gekregen. Hierbij zijn de mogelijkheden om discrete optimaliseringsproblemen met multi-layered perceptrons exact op te lossen in kaart gebracht. De tweede fase van dit onderzoek is in 1993 gestart (met NWO-subsidie) en heeft vooral betrekking op de praktische gebruiksmogelijkheden van neurale netwerken voor produktieplanning.
Yüklə 1,87 Mb. Dostları ilə paylaş:
|