BIJLAGE A VOORTGANG ONDERZOEK. Lotgevallen W&I 1995 p.46

BIJLAGE A

VOORTGANG ONDERZOEK

Lotgevallen W&I 1995 – p.46

BETA en Stieltjes Instituut, verslag 1995 BETA Programmaleiding

:

Onderwerpontsluiting ISN : Onderwerpontsluiting NWO : Onderwerpontsluiting NABS :

prof.dr. J. Wessels, prof.dr. P. van der Laan 1203, 1207, 1208, 1209 P175, P160 10.0, 5.0, 8.3

Stieltjes Instituut Programmaleiding

:


prof.dr. J. Wessels 1208, 1209 P160 10.0

De meeste onderzoekers in de groepen Statistiek, Kansrekening en Stochastische Besliskunde maken deel uit van zowel de wiskundige onderzoekschool Stieltjes als de meer bedrijfskundige onderzoekschool BETA. Het is vanzelfsprekend van groot belang deel uit te maken van de discipline-gerichte wiskundige onderzoekschool Stieltjes. Omdat echter een groot deel van het onderzoek, niet alleen het toegepaste maar ook het meer fundamentele, wordt geinspireerd door vragen uit de praktijk is het zeer nuttig ook deel te nemen in de meer in de toepassing gewortelde onderzoekschool BETA. Aangezien vrijwel al het onderzoek zowel fundamentele als toegepaste kanten heeft is het niet zinvol de individuele onderzoekprojecten bij precies een onderzoekschool onder te brengen. Daarom is gekozen voor deze gecombineerde verslaglegging. 1) Er wordt gewerkt binnen het thema 4.

Operations Research and Statistics,

in de subthema's 4.2 4.3

Quantitative Methods for Operations Management Mathematical Tool for Design and Management of Business Processes

in de wiskundige disciplines 1) 2) 3) 4) 2) a)

Kansrekening Statistiek Stochastische Besliskunde. Combinatorische optimalisering. Kansrekening (subthema 4.3) Het boek met Van Harn over oneindige deelbaarheid is nu voor ongeveer de helft klaar; we verwachten dat de tweede helft minder tijd zal vergen, al was het maar omdat de Eindhovense auteur nu over meer tijd beschikt. Er is dit jaar in het verlengde van het werk van Brands, Steutel, Thiemann en Wilms gekeken naar "The number of values near the maximum"; hierover is tijdens zijn bezoek aan Pakes in Perth door Steutel en zijn gastheer een artikel geschreven.


Er wordt gewerkt aan de asymptotiek van momenten van maxima bij grote steekproeven. Het bezoek van Steutel aan Ken-iti Sato in Nagoya resulteerde in een gezamenlijk artikel over het voortzetten van oneindig deelbare verdelingen en hun kanonieke maten. Tijdens zijn reis werden vijf voordrachten gehouden. Het artikel met Bondesson en Kristiansen is geaccepteerd en zal binnenkort verschijnen in Stat. & Prob. Letters. Steutel heeft een bijdrage geleverd aan het liber amicorum voor Kruseman Aretz. b)

Statistiek

i)

Selectieprocedures (subthema 4.2) Onderzoek is verricht op het gebied van statistische subset selectieprocedures. De resultaten zijn weergegeven in de COSOR-Memoranda 95-02, 95-14, 95-20, 95-25, alsmede in Technical Report No. 153, University of British Columbia, Vancouver. Het onderzoek naar een gegeneraliseerde selectie procedure heeft geleid tot een publicatie in Proceedings of the 50th Session of the International Statistical Institute, Beijing. Tevens zijn een aantal voordrachten op het gebied van selectieprocedures gehouden . Een drietal publicaties zijn verschenen. Samenwerking met Prof. C. van Eeden, University of British Columbia; dr. F. Coolen, University of Durham en dr. M. van der Laan, University of California is voortgezet. Dit heeft geleid tot gegeneraliseerde aanpakken.

ii)

Niet-parametrische en semi-parametrische statistiek (subthema 4.3) Het onderzoek naar precedence tests voor complete data en voor gecensureerde data is voortgezet. Een tweetal artikelen is ter publicatie aangeboden. Er is onderzoek verricht op het gebied van de extreme-waardentheorie. Hierbij is samengewerkt met Prof. De Haan en drs. Sinha (EUR). De resultaten zijn vastgelegd in Report 9533/A, Erasmus Universiteit Rotterdam, dat inmiddels geaccepteerd is voor publicatie. Een ander artikel is verschenen in 1995. Op het gebied van de stochastische censurering zijn 2 artikelen verschenen in wetenschappelijke tijdschriften, terwijl er nog één zal verschijnen. Samenwerking vond en vindt plaats met Prof. Ruymgaart (Lubbock, Texas), Prof. Deheuvels (Parijs) en Prof. Beirlant (Leuven). Tevens is onderzoek gedaan m.b.t. empirische processen, zie COSOR-Memorandum 95-30. Een ander artikel zal spoedig verschijnen. Verder is een begin gemaakt, samen met Prof. Ruymgaart, met onderzoek naar afhankelijke stochas ten (tijdreeksen). Voordrachten zijn gehouden in Heidelberg, Groningen, Bern (2x), Lubbock, Tilburg en Oberwolfach. De samenwerking met Loeb op het gebied van toepassingen van de combinatoriek (i.h.b. umbrale calculus) in de statistiek is voortgezet. Een artikel over persistente Sheffer-polynomen en een eletronisch overzichtsartikel over umbrale calculus zijn verschenen. Het onderzoek naar toepassingen van computeralgebra in de statistiek heeft de eerste resultaten opgeleverd. In samenwerking met een afstudeerstudent is Mathematica-programmatuur ontwikkeld voor een grote klasse van niet-parametrische tweesteekproeventoetsen. Het komende jaar zal vooral aandacht geschonken worden aan het meersteekproevenprobleem. Voorts is een niet-parametrische regelkaart onderzocht. Hiervoor zijn enige verdelingsresultaten afgeleid. Deze resultaten zullen het komende jaar in een computerprogramma geïmplementeerd worden.

iii)

Statistische modellen voor besluitvorming (subthema 4.3) Het onderzoek naar de principes van statische besluitvorming en de wiskundige fundering ervan heeft in 1995 geresulteerd in de publicatie van een artikel over de reductie en classificatie van de data waar de besluitvorming op is gebaseerd. Het onderzoek naar inference rules en de bijbehorende inferential distributions heeft geresulteerd in de acceptatie van een artikel op dit gebied. Dit artikel moet nog verschijnen. In 1995 is vooral onderzoek gedaan naar conditionele besluitvorming en de


betekenis van betrouwbaarheid van uitspraken in de aanwezigheid van partieel ancillaire statistieken. Dit werk kan gezien worden als een uitbreiding en wiskundige fundering van de ideeën van R.A. Fisher door hem samengevat in de woorden 'Sampling the reference set'. Een artikel op dit punt is bijna gereed. iv)

Statistische theorie van het proefopzetten (subthema 4.3) Onderzoek naar goede proefopzetten met weinig waarnemingen voor factoriële schema's heeft geresulteerd in twee COSOR-memoranda. Dit onderzoek gebeurt onder andere in samenwerking met B. Pauwels, een promovendus bij UFSIA, Universiteit van Antwerpen. Samen met hem wordt ook onderzoek gedaan naar proefopzetten voor paarsgewijze vergelijkingen. In 1995 is een promotieonderzoek gestart naar het ontwerp van een interactief computerprogramma voor het genereren van proefopzetten en analyseren van waarnemingen. Dit onderzoek gebeurt in samenwerking met het Unilever Research Laboratorium in Vlaardingen. Er is begonnen met evaluatie en testen van een prototype dat al ontwikkeld was. Verder is gewerkt aan uitbreidingen op het gebied van Taguchi-proefopzetten en het analyseren van waarnemingen. Naar aanleiding hiervan is er een lezing gehouden op de conferentie HUGS '95 in Amsterdam, een conferentie voor SAS-gebruikers in Nederland.

c)

Stochastische Besliskunde

i)

Wachtrijen met meer rijen en onderling afhankelijke instroomprocessen (subthema 4.3) Het onderzoek op het gebied van de compensatie-aanpak is in 1995 voortgezet. De methode is gebruikt bij de analyse van modellen voor produktiesystemen waarin zowel op order als op voorraad wordt geproduceerd. De recent ontwikkelde methode voor de bepaling van onder- en bovengrenzen voor de prestaties in systemen die zelf niet analytisch behandeld kunnen worden, is toegepast op een wachtrijmodel (afkomstig van een probleem op het gebied van onderhoud), waarin klanten na een stochastische tijd van prioriteit kunnen veranderen. Tevens is een wachtrijmodel voor een reparatiesysteem met 2 verschillende reparatiekanalen (normaal en spoed) geanalyseerd.

ii)

Fitten van discrete verdelingen (subthema 4.2) Er is een methode ontwikkeld voor het fitten van discrete verdelingen op de eerste twee momenten van een gegeven verdeling. Deze methode is bijvoorbeeld zeer nuttig bij het benaderend oplossen van wachtrijsystemen met discrete aankomst- en/of bedieningstijdverdelingen. Verder is de methode gebruikt bij de analyse van handmatige orderverzamelsystemen (en geïmplementeerd in een pakket op dit gebied t.b.v. KPN Research). Momenteel wordt de methode uitgebreid naar discrete verdelingen met een eindige drager.

iii)

Multi-echelon voorraadsysteem (subthema 4.3) Er is onderzoek verricht naar de wijze waarop een multi-echelon voorraadsysteem beheerst dient te worden zodanig dat de totale kosten (voorraadkosten en boetekosten) geminimaliseerd worden. Een algoritme is ontwikkeld om de parameters van de beheersstrategieën in de verschillende voorraadpunten te bepalen. In de meeste analyses betreffende multi-echelon voorraadsystemen wordt aangenomen dat de onbalans in elk voorraadpunt geen grote invloed heeft op de totale kosten en de uiteindelijk gerealiseerde klanten-servicegraden. Onderzoek is verricht om m.b.v. alle parameters van de beheersstrategieën het effect van onbalans op deze servicegraden te voorspellen.

iv)

Periodieke produktiesystemen (subthema 4.3) Het onderzoek op het gebied van de periodieke produktiesystemen is voortgezet met het analyseren van additionele mogelijkheden tot vooruitwerken en op voorraad produceren. Voorts is een begin gemaakt met het vastleggen van deze en vorige resultaten in een


proefschrift. Naast het onderzoek naar periodieke produktiesystemen, is een M/G/1 wachtrij met twee typen vakanties geanalyseerd. Bovendien is een algoritme ontwikkeld dat de optimale twee-drempelwaarde strategie bepaalt voor dit wachtrijsysteem. v)

d)

Real-time databases (subthema 4.3) Het door STW gefinancierde project op het gebied van de real-time databases loopt inmiddels een jaar. Doel van het project is te bereiken dat reeds in de ontwerpfase de real-time prestaties beoordeeld kunnen worden en daarmee teleurstellingen achteraf te voorkomen. De prestatiemaat voor een real-time database is het percentage van de transacties dat zijn deadline haalt. Een manier om dit percentage te verhogen is transacties zoveel mogelijk parallel uitvoeren. Er is dan wel een transactie-scheduler nodig die de consistentie van de database bewaakt. Twee schedulers, Single Queue Static Locking en Optimistic Concurrency Control, zijn met behulp van stochastische modellen geanalyseerd. Het resultaat voor beide modellen is een goede benadering voor de responstijdverdeling van de transacties, en daarmee voor de kans dat een transactie zijn deadline haalt. Combinatorische Optimalisering

i)

On-line scheduling (subthema 4.2) Een gedeeltelijk door STW gefinancierd onderzoek naar het flow shop probleem met parallelle machines in elke produktiefase stagneerde door vertrek van de onderzoeker. Een tijdelijke voortzetting van het onderzoek concentreerde zich op max-cost flow modellen voor insertiemethoden voor een grote klasse van scheduling problemen. In 1996 zal met het project een nieuwe start worden gemaakt. Het nieuwe project geschiedt in samenwerking direct onder de vlag van BETA en betreft nieuwe methoden en modellen voor scheduling en aggregaatplanning. In een voor 50% door TNO gefinancierd onderzoek werd voortgang geboekt bij de bestudering van modellen en methoden voor on-line scheduling problemen, met name op het gebied van worst-case performance van klassen van on-line algorithmen. Er zijn zowel positieve resultaten afgeleid (gegarandeerde worst-case ratios), als negatieve uitspraken (zoals "geen enkele online algorithme kan een gegarandeerde relatieve bovengrens leveren kleiner dan een zekere constante c").

3) Samenwerkingen Prof.dr. E.H.L. Aarts - TUE Dr. A. Agnetis - Università degli Studi di Roma "La Sapienza", Rome, Italië Prof.dr. J. Beirlant - Katholieke Universiteit Leuven, Leuven, België Dr. J.L. van den Berg - PTT Research Prof.dr. L. Bondesson - Universiteit Uppsala, Uppsala, Zweden Prof.dr.ir. O.J. Boxma - CWI Ir. J.J.A.M. Brands - TUE Prof.dr. T. Calinski - Landbouwuniversiteit Pozna_, Pozna_, Polen Prof.dr. S. Chakraborti - Universiteit of Alabama, Tuscaloosa, Alabama, USA Dr.ir. F. Coolen - Universiteit of Durham, Durham, Engeland Prof.dr. P. Deheuvels - Universiteit van Parijs VI, Parijs, Frankrijk Prof.dr. C. van Eeden - Universiteit van British Columbia, Vancouver, B.C., Canada Prof.dr. L. de Haan - EUR Dr. K. van Harn - VU Amsterdam Prof.dr. E. Khmaladze - Georgische Akademie van Wetenschappen, Tbilisi, Georgië H.G.M. van der Knaap - Unilever Research Lab., Vlaardingen Dr. G.K. Kristiansen - Universiteit van Kopenhagen, Kopenhagen, Denemarken Dr. M.J. van der Laan - Universiteit van California, Berkeley, California, USA


Dr. Z. Liu - Institut National de Recherche en Informatique et en Automatique, Sophia Antipolis, Frankrijk Dr. D.E. Loeb - Universiteit van Bordeaux I, Bordeaux, Frankrijk Prof. Y. Nakamori - Konan Universiteit, Kobe, Japan Drs. J. Oudemans - CQM, Eindhoven B. Pauwels - Universiteit van Antwerpen/UFSAI, Antwerpen, België Dr.ir. J. Praagman - CQM, Eindhoven Prof.dr. G.-C. Rota - Massachusetts Instituut voor Technologie, Cambridge, Massachusetts, USA Prof.dr. F. Ruymgaart - Texas Technische Universwiteit, Lubbock, Texas Prof.dr. Y. Sawaragi - Het Japans Instituut voor Systeem Onderzoek, Kyoto, Japan Prof.dr. P.J. Schweitzer - Universiteit van Rochester, Rochester, New York, USA Drs. A.K. Sinha - EUR Drs. D. van der Sluis - RUG Drs.ing. J. Smit - Smit Consult, Drunen Prof. H. Tamura - Osaka Universiteit, Osaka, Japan Dr.ir. P.M. Upperman - Oosterhesselen Ir. J.I. van Zante-de Fokkert - TUE Prof.dr. W.H.M. Zijm - UT International Institute for Applied Systems Analysis (IIASA) Laxenburg, Austria 4) Voornemens op korte termijn Het onderzoek binnen de genoemde subthema's wordt in 1996 met ongeveer dezelfde intensiteit en aandachtspunten voortgezet.


DISC, verslag 1995 Programmaleiding

:

Onderwerpontsluiting ISN : Onderwerpontsluiting NWO : Onderwerpontsluiting NABS : Beschrijving en resultaten

prof.dr.ir. M.L.J. Hautus 3399 Systeem- en Regeltechniek, 1299 Systeemtheorie P175 10.0

In het kader van de onderzoeksschool DISC is in 1995 gewerkt aan de volgende onderzoeksthema's: Modelvorming en systeemrepresentatie -

Oneindigdimensionale realisatietheorie voor lineaire tijdcontinue systemen Er wordt een theorie ontwikkeld voor de realisatie (representatie) van systemen met een niet nader bepaalde, vrij te kiezen signaalruimte. Hierdoor hopen we meer inzicht te krijgen in de topologische en algebraïsche aspecten van de realisatietheorie. Wiskundige onderwerpen die een rol spelen zijn: - C0-semigroepen op rijvolledige lokaalconvexe vectorruimtes, - convolutie-algebra's van distributies, - Translatie-invariante deelruimtes en spectraaltheorie.

-

Gedistribueerde vertraagde systemen De theorie van vertraagde systemen kent een aantal benaderingen: - de algebraïsche benaderingen van systemen over ringen, - de functionaalanalytische benadering, waarbij (geïnspireerd door J.C. Willems) een systeem als kern (nulruimte) is van een convolutie-operator wordt gezien. - De klassieke benadering, waarin een vertraagd systeem beschreven wordt door een stelsel differentiaalvergelijkingen. Het doel van ons onderzoek is deze benaderingen onderling te vergelijken aan de hand van een aantal systeemtheoretische concepten zoals waarneembaarheid, bestuurbaarheid en stabiliseerbaarheid. Een grote rol hierbij spelen convolutiedeelalgebra's van distributies die een zogenaamd Bezoutdomein vormen. In het onderzoek worden de in het voriggenoemde onderzoek gevonden resultaten gebruikt. Het onderzoek kan worden gezien als een uitbouwing van het promotiewerk van dr.ir. J. M. Soethoudt en dr.ir. L.C.J.G.M. Habets.

-

Identificatie en modelvorming We onderzoeken hier de modelvorming met de zogenaamde "behavioural approach'' (ingevoerd door J.C. Willems), waarbij in de modelvorming geen onderscheid wordt gemaakt tussen ingangen en uitgangen. Daarnaast kijken we naar modelapproximatie waarbij we stochastische processen approximeren met als criterium de Kullback-Leibler afstand (ook wel de divergentie genoemd).

Systemen met begrenzingen -

Verzadiging In dit onderzoeksproject onderzoeken we in hoeverre de resultaten uit de lineaire theorie kunnen orden gegeneraliseerd tot de situatie waar in de onderzochte systemen verzadiging aan de uitgang of aan de ingang optreedt. Enerzijds komen zulke syste-


men vaak voor, anderzijds kan men hopen dat voor deze speciale vorm van nietlineariteit explicietere resultaten kunnen worden verkregen dan voor algemene lineaire systemen. We hebben gekeken naar stabilisatie en naar het onderdrukken van sinusoïdale verstoringen. Ook is de waarneembaarheid van zulke systemen onderzocht. Er zijn hier nog veel open problemen. -

Begrenzingen in het tijdsdomein We bestuderen hoe wij er door middel van een regelaar voor kunnen zorgen dat de toestand of de ingang binnen een bepaalde verzameling blijft. We hebben het hieraan gerelateerde l-optimale regelaar probleem bestudeerd en bijv. aangetoond dat we in het algemeen niet-lineaire regelaars nodig hebben zelfs als het system verder lineair is. Op dit moment bestuderen we het verwante probleem van het schatten van de toestand met een optimaliteitscriterium in het tijdsdomein. Een van de methodes die hierbij wordt gebruikt is gebaseerd op de (klassieke) theorie van optimale besturingen.

Robuustheid We zijn we geïnteresseerd in het onderdrukken van modelonzekerheid, terwijl we ook de stochastische onzekerheid veroorzaakt door bijv. meetruis willen onderdrukken. De dualiteit tussen deterministische en stochastische effecten maakt dit een zeer lastig probleem. Niet-lineaire systemen -

Meetkundige en algebraïsche eigenschappen van niet-lineaire systemen In dit deelprogramma worden methoden ontwikkeld voor de regeling van nietlineaire systemen. Speciale aandacht wordt besteed aan (differentiaal-)meetkundige en (differentiaal-)algebraïsche methoden. Er zijn resultaten geboekt op het gebied van "fixed modes'' voor nietlineaire systemen, gegeneraliseerde stuurinvariantie voor nietlineaire systemen, waarnemerontwerp voor nietlineaire tijddiscrete systemen, en (gedeeltelijke) ingangs-uitgangslinearisatie van nietlineaire systemen.

-

Lie-algebraïsche technieken in de Hamiltontheorie, Met de groep 'deeltjesversnellers' van Prof. dr. H.L. Hagedoorn van natuurkunde is het afgelopen jaar het werk bestudeerd van A.J. Dracht. Er bestaat de hoop dat met Lie-algebraïsche technieken de beweging van deeltjes (elektronen) in versnellers adequater dan tot nu toe beschreven kan worden. Dit onderzoek is onderdeel van het project Euterpe met als doel het ontwerp en de bouw van een elektronenopslagring met een daaraan gekoppeld microtron. De hoge mate van niet-lineariteit van de Hamiltonse bewegingsvergelijkingen laat geen analytische oplossingen toe. De resultaten zijn daarom beperkt tot kwalitatieve aspecten, zoals de stabiliteit (focusering) van de deeltjesbanen. het primaire doel van het onderzoek is na te gaan of het Lie-algebraïsch formalisme voldoende krachtig is om zogenaamde randveldeffecten in rekening te brengen.

Samenwerking met andere faculteiten: -

Elektrotechniek (S. Weiland, P.van de Bosch) Natuurkunde (L. Hagedoorn, F. Preisig) Werktuigbouwkunde (J. Kok, R. Kriens) BMGT, gerontechnologie (J. Graafmans, T. Harrington)

met andere universiteiten: -

Rutgers University (P. Sannuti, E. Sontag) New York State University at Stonybrook (Z. Lin) Washington State University (A. Saberi) University of Michigan (J. Grizzle) Beijing University of Aeronautics and Astronomics (X. Xia)


met onderzoeksinstellingen: - CWI (J. van Schuppen) - Laboratoire d'Automatique de Nantes (C. Moog) met bedrijven: - IPCOS (Ir. J. Ludlage) Voornemens Het merendeel van de bestaande onderzoeksthema's bevat nog belangrijke open vragen. Het onderzoek in die gebieden zal daarom worden voortgezet. Nieuwe onderzoeksthema's zullen zijn: de bestudering van nietlineaire dynamische systemen en toepassingen van de computeralgebra bij de regeling van nietlineaire dynamische systemen, identificatie en modelvorming, signaalanalyse.


EIDMA - verslag 1995 Programmaleiding

:


prof.dr. A.E. Brouwer, prof.dr. A.M. Cohen, prof.dr. J.K. Lenstra, prof.dr.ir. H.C.A. van Tilborg. 1204, 1299 Discrete Wiskunde, 3325 P110, T180 N025, 10.0

1. (Eindige) meetkunde, grafentheorie en designtheorie Onderzoek is gedaan in samenwerking met Ball en Mazzocca naar het bestaan van (q+1)-bogen in projectieve vlakken van de orde q. Een beroemd 40 jaar oud probleem werd opgelost door aan te tonen dat zulke bogen niet bestaan in vlakken van oneven orde. In samenwerking met Ball, Storme en Szönyi is de vraag naar het aantal richtingen bepaald door de grafiek van een functie over een eindig lichaam vrijwel volledig beantwoord. Dit beantwoord een 25 jaar oude vraag van Rédei. In samenwerking met Storme en Szönyi werden de ondergrenzen voor de afmeting van meervoudige blocking sets in Desarguese projectieve vlakken aanzienlijk verscherpt, en in veel gevallen werd de exacte structuur van de minimale verzamelingen bepaald. In samenwerking met Szönyi is de nonexistentie van zekere blocking sets van bijna Rédei type aangetoond. Onderzoek is gedaan naar MDS codes, in de formulering in termen van bogen in projectieve ruimten. In samenwerking met Cooperstein is gewerkt aan Lieincidentiesystemen. Beschouw de inbedding in de projectieve ruimte van een meetkunde Γ (of alleen maar een stel punten). Laat ∆ de meetkunde zijn met als punten de punten van Γ en als lijnen de projectieve lijnen die volledig in Γ liggen. De algemene vraag hier is: Beschrijf ∆. Deze vraag is beantwoord in het geval Γ een Lieincidentiemeetkunde is. In samenwerking met R. Blok is bepaald welke Lieincidentiesystemen opgespannen worden door een appartement. Punt-lijn meetkunden met grote deelruimten zijn bestudeerd. Hierbij werden connecties met Fischer ruimten, Zara grafen en polaire ruimten nader onderzocht. Euclidische roosters voortgebracht door vectoren met minimale norm 3 zijn onderzocht. Hiermee werd werk van Neumaier voortgezet. Dit heeft geleid tot karakterisaties van een aantal van dergelijke roosters gerelateerd aan de sporadische enkelvoudige groep Co_2. Verder zijn er eveneens connecties met het Leech rooster. Alle afstandsreguliere grafen zonder 3-klauwen werden bepaald. De spectra van verschillende associatieschema's werden bepaald. Een hoofdstuk over sterk reguliere grafen is geschreven voor het Handbook of Combinatorial Designs. In samenwerking met Colbourn en Dinitz is een hoofdstuk over onderling orthogonale Latijnse vierkanten geschreven voor het Handbook of Combinatorial Designs.


2. Theorie van groepen en Lie algebra's Onderzocht werd in hoeverre een eindige ondergroep H van een algebraische groep G een karakteristiek rooster invariant laat. Allereerst bleek dat er, bij niet al te sterke aannamen voor de ondergroep H (die aan maximaliteit als algebraische ondergroep doen denken), een uniek minimaal splijtlichaam is. Dat wil nog niet zeggen dat het eenvoudig is dit unieke lichaam ook te vinden. In samenwerking met Tiep is in het speciale geval van de Jordanondergroepen dit lichaam bepaald. Dit is een gezonde eerste stap in de gewenste richting. Immers, men neme de ring R van gehelen van dat minimale splijtlichaam en vrage zich af of er een definitie G_R van de groep G over R te vinden is, zo dat H de ondergroep van punten gedefinieerd over R is: H = G_R(R). Deze vraag is volledig beantwoord in het geval G=G_2 en H een van de vier Lieprimitieve ondergroepen die G kent; dit in samenwerking met Nebe en Plesken. Over het algemene geval wordt nog gedacht. In samenwerking met David Wales is gekeken naar het GL(4,k)-moduul van de kubische vormen modulo de derde machten, voor k een algebraisch afgesloten lichaam van karakteristiek 3. In dit geval bleken er eindig veel banen te zijn. Het artikel hierover, dat in J. Algebra zal verschijnen, bevat een beschrijving van een algoritme in de notedop hoe een algemene vorm in een van de expliciet gegeven baanrepresentanten te herschrijven. In geval van 3 dimensies is dit omgewerkt tot een interactief programma dat via de Proceedings van de Organics Workshop in Vancouver over het net te proberen valt. Met Gábor Ivanyos en David Wales is gewerkt aan een algoritme voor het bepalen van het radicaal van een eindig-dimensionale algebra. Het behelst hier zowel een beter begrip van de objecten die Rónyai gebruikte voor een polynomiaal algoritme, als een vereenvoudiging van zijn aanpak (hij moest een lift naar de gehele getallen uitvoeren, wij niet). De resultaten worden gebruikt voor een methode om te zien of twee algebravoorstellingen al dan niet equivalent zijn. In samenwerking met G. Ivanyos, A. Kuronya en L. Ronyai is gekeken naar de Levi decompositie van een Lie algebra in karakteristiek nul. Het is niet bewezen dat het al bestaande algoritme hiervoor polynomiaal is. Door wat wijzigingen aan te brengen kan een polynomiaal algoritme verkregen worden. Verder is een nieuw algoritme voor de berekening van het nilradicaal van een Lie algebra ontwikkeld. Ook is gewerkt aan structuur berekeningen van semsimpele Lie algebras. In samenwerking met S. Elashvili is gekeken naar centralisatoren van klassen van nilpotente elementen in E_8. Het bleek dat deze centralisatoren alle van index 8 zijn. In samenwerking met T. Breuer uit Aachen zijn de corresponderende algoritmen in GAP geimplementeerd. Gewerkt is aan een vermoeden van Deligne betreffende het bestaan van een tensorcategorie waar de representatiecategorieen van de exceptionele groepen en nog enkele andere enkelvoudige algebraische groepen "specialisaties" van zijn. Dit vermoeden is gebaseerd op verrassende patronen die zijn waar te nemen bij de decompositie van de tensormachten van de geadjungeerde voorstellingen van deze groepen. In Comptes rendus zal een artikel verschijnen met de resultaten van de decompositie van de vierde tensormacht. Intussen is ook de vijfde tensormacht uitgewerkt. Het zoeken is (onder andere) naar een combinatorisch model voor de vermoede tensorcategorie. Enkele stappen in die richting zijn inmiddels gezet. In samenwerking met J. van Bon werden diagram-meetkunden van het type Af.G_2 en Af.C_3* bestudeerd. De 7-dimensionale voorstelling van de groepen van type G_2 werden hierdoor op meetkundige wijze gekarakteriseerd, alsmede ook de spinvoorstelling van de groepen van type C_3. De connectie tussen cotriangulaire meetkunden en een klasse van Liealgebra's geïntroduceerd door Kaplanski werd onderzocht. Een karakterisatie van deze Liealgebra's werd verkregen. Als gevolg van deze karakterisatie is de automorfismengroep en de algebra van derivaties van deze


Liealgebra's berekend. Hiermee werd een vermoeden van Rotman en Weichsel verbeterd en bewezen. 3. Combinatorische optimalisering a. Polyhedrale methoden Het onderzoek naar polyhedrale methoden voor discrete seriegrootteproblemen werd voorgezet en zal in 1996 worden afgerond met een promotie. Er werden interessante resultaten geboekt met de toepassing van kolomgeneratiemethoden voor de oplossing van twee- en driedimensionale snijproblemen en van schedulingproblemen op parallelle machines. In het kader van een extern gefinancierd project werd verdere voortgang geboekt met de polyhedrale aanpak van frequentietoewijzingsproblemen. b. Lokale zoekmethoden Het onderzoek van ir. R.J.M. Vaessens werd afgerond met zijn promotie op het proefschrift "Generalized job shop scheduling: complexity and local search". In het kader van een extern gefinancierd project werd een artikel over lokale zoekmethoden voor frequentietoewijzingsproblemen voltooid. De redactie van een boek over lokale zoekmethoden in de combinatorische optimalisering werd voortgezet; het boek zal in 1996 verschijnen. c. Nieuwe modellen en methoden voor routeringsproblemen Twee artikelen over een afstudeerproject over een handelsreizigersprobleem dat optreedt bij de productie van geintegreerde schakelingen, dat de VVS-prijs 1994 won, werden voltooid. Twee afstudeerprojecten op het gebied van de fysieke distributie werden gestart: een project over depotlocatie en transportplanning bij een Zaans bedrijf, en een project over rechtstreeks-vervoerproblemen bij een Eindhovens adviesbureau. d. Nieuwe modellen en methoden voor schedulingproblemen Het onderzoek van drs. M. Wennink werd afgerond met zijn promotie op het proefschrift "Algorithmic support for automated planning boards". Een voor 50% door TNO gefinancierd promotie-onderzoek naar modellen en methoden voor on-line schedulingproblemen maakte goede voortgang. In het kader van twee mede door EIDMA gefinancierde projecten werden belangrijke resultaten bereikt met betrekking tot flow shops met vertragingen en combinatorische benaderingsalgoritmen. Korte projecten met bezoekende onderzoekers leidden tot interessante studies naar modellen voor batch-scheduling en proportionele flow shop, en een nieuwe methode "non-strict vector summation" voor een grotere klasse van scheduling problemen. 4. Coderingstheorie Vectoren van minimaal gewicht in lineaire codes geven een beschrijving van de toegangsstructuren van de bijbehorende schema's om geheimen te (ver)delen. Voor zekere bekende klassen van codes en voor toevalscodes is een karakterizering van deze vectoren gevonden. Sommige voorbeelden zijn ook meer algemeen over eindige ringen (i.p.v. lichamen) bekeken. Nieuwe constructies van niet-lineaire cyclische codes zijn gebruikt om nieuwe families van binaire rijen met lage correlatie, beter dan de tot dusver bekende, te construeren. Onderzocht is de distributie van geheime sleutels over een openbaar kanaal, teneinde dynamisch de deelverzameling van gepriviligeerde gebruikers te kunnen veranderen. Voor grote netwerken leveren block designs de beste en eenvoudigst te implementeren systemen op.


Een verband is aangetoond tussen gegeneraliseerde Hamming gewichtspolynomen en invarianten van matroiden. Dit resulteert in een eenvoudige vorm voor de MacWilliams relaties voor gegeneraliseerde gewichten, en suggereert een manier om bovengrenzen voor de kardinaliteiten van codes af te leiden. Voor b = 4 en b = 5 zijn de parameters van alle optimale, binaire cyclische codes bepaald, die een willekeurige burst ter lengte b kunnen corrigeren. Expliciete voorbeelden zijn gegeven in tabellen voor alle gevallen waarin de existentie stellingen niet werken. Er is een efficient parallel decoderingsalgoritme afgeleid voor optimale, binaire b-burst-correcting, cyclische codes. Dit algoritme maakt gebruik van het feit dat het generator-polynoom van zo'n code gesplitst kan worden in een primitief polynoom p(x) van de graad m en een polynoom e(x) van de graad b-1. De r-de gegeneralizeerde gewichten van de q-aire Reed-Muller codes zijn bepaald. De sleutelobservatie hiervoor is geweest dat het minimum aantal elementen in de support van een subcode van de Reed-Muller code van dimensie r gelijk is aan het aantal elementen in de zgn. schaduw van een bepaalde verzameling A. Dot codes worden gebruikt voor produkt registratie d.m.v. een camera. Een simpele, robuste methode is ontwikkeld om de codes te herkennen. Nieuwe constructies van zgn. square-cyclische codes zijn beschreven. De toestandscomplexiteit van een lineaire code geeft de complexiteit van het decoderen met behulp van het Viterbi algoritme aan. Grenzen aan die complexiteit zijn afgeleid en constructies van codes met een bepaalde complexiteit zijn gevonden. Uitgebreid onderzoek is gedaan naar het zgn. uncoordinated multiple-access kanaal. Nieuwe resultaten aangaande de capaciteit en de cutoff-rate zijn afgeleid. Nieuwe "multilevel" constructies van de Golay code en de Leech lattice zijn beschreven. Deze maken het mogelijk om begrensde-afstands decodeermethodes te formuleren met een geringere effectieve foutencoefficient dan voorheen bekend. Gesloten formules voor de foutaanwijzende veelterm van cyclische codes zijn gevonden. Een hoofdstuk over AG codes voor het handboek van de coderingstheorie is geschreven met T. Høholdt en J.H. van Lint. Een symmetrische versie van de Roosgrens werd afgeleid in samenwerking met I.M. Duursma. Gegeneraliseerde Klein codes zijn onderzocht, in samenwerking met G.-L. Feng en T.R.N. Rao. Asymptotisch goede krommen en codes werden geconstrueerd in samenwerking met H. Stichtenoth. Een hyperbolische grens voor codes werd afgeleid in samenwerking met R.H. Blahut en T. Høholdt. Het bestaan van codes met een duale die linear complementair is werd aangetoond. Irreducibiliteit van varieteiten werd onderzocht m.b.v. Gröbner bases en gewichtsfuncties. Onderzoek is gedaan naar codes opgespannen door kwadratische en Hermitese vormen. Hieruit kwam in het bijzonder een nieuwe ternaire [91,9,54] code.


5. Cryptologie Een nieuwe klasse van algoritmen voor het decoderen van lineaire codes zonder bekende structuur is voorgesteld. Deze algoritmen hebben de kleinst bekende implementatiecomplexiteit voor lange codes. Dit geeft de best bekende aanval op het McEliece cryptosysteem. Er is onderzoek verricht naar secret sharing schema's. Dit zijn schema's waarin onder een groep deelnemers een secret verdeeld wordt in shares zodanig dat bepaalde subgroepen in staat zijn het geheim te reconstrueren door hun shares te combineren. Alle bestaande decompositie constructies zijn veralgemeend. Verder is het dualiteits-resultaat voor complete schema's uitgebreid naar incomplete schema's. Een constructie om unconditional secure group authentication schema's te produceren is gevonden. Deze schema's zijn analoog aan secret sharing schema's met het onderscheid dat niet een geheim maar een geheime authenticatie functie verdeeld wordt. Door shares te combineren kan nu bij een gegeven bericht een handtekening voor een groep deelnemers gevonden worden. De broadcast channel with confidential messages met en zonder public discussion zijn onderzocht. Gander en Maurer's coding gain strategie is geanalyseerd. Verder is gekeken naar enige specifieke situaties en kanalen. Er is sleutel opslag en distributie schema voorgesteld voor een situatie met 1 Centrale Management Faciliteit en meerdere zelfstandige sleuteldistributiecentrales. Een concrete uitwerking van een RSA systeem is gemaakt voor een simpele smartcard (zonder co-processor). Om de rekentijd aanvaardbaar te houden zijn speciale rekenmethodes gebruikt en enige compromissen wat betreft de security van het syteem gesloten. Met behulp van block designs zijn sleutel distributie schemas ontwikkeld voor toepassingen van het type betaal t.v. Hierbij wordt een compromis gesloten tussen het aantal te versturen sleutels en het aantal bij een ontvanger opgeslagen sleutels. 6. Computeralgebra, computers en wiskunde In samenwerking met Heck is een artikel geschreven over het ontwerpen van een contranok voor een garnalenmachine. Een artikel is geschreven over het gebruik van Groebner bases m.b.t. foutenverbeterende codes. Een inleidend artikel over de fundamentele algoritmen voor permutatiegroepen werd geschreven. Deze algoritmen zijn, ten dele, geimplementeerd in Maple en Mathematica. Het padenmodel van Littelmann is bestudeerd en enige algoritmen zijn geïmplementeerd in GAP. Gewerkt is aan het COCO (`coherent configurations') computeralgebrasysteem. Veel tijd is besteed aan projecten die de interactie met een computer behelzen. Nagedacht is over de integratie met bewijsverificatiesystemen, interactieve boeken e.d. De service van de WWW servers is uitgebreid. Samenwerkingen Samenwerking op een van bovenstaande gebieden bestaat onder meer met: S. Ball (London, TUE),


R.H. Blahut, R. Blok (THD), J. van Bon, T. Breuer, C. Colbourn (Waterloo), B. Cooperstein, J. Dinitz, I.M. Duursma, S. Elashvili, G.-L. Feng, A. Heck (CAN), T. Høholdt, G. Ivanyos, A. Kuronya, J.H. van Lint (TUE), F. Mazzocca (Napels), G. Nebe (Aachen), W. Plesken (Aachen), T.R.N. Rao, L. Ronyai (Budapest), N.J.A. Sloane (Bell Labs), H. Stichtenoth (Essen), L. Storme (Gent), T. Szönyi (Budapest), P.H. Tiep (Essen), D.B. Wales (Pasadena)


STEVIN Centrum, verslag 1995 Programmaleiding

:

prof.dr. R.M.M. Mattheij, prof.dr.ir. J. de Graaf, dr.ir. C.W.A.M. van Overveld.

Onderwerpontsluiting ISN : 1202, 1203, 1206, 2202, 2205, 2212 Onderwerpontsluiting NWO : P175, P130, P140, P170 Onderwerpontsluiting NABS : 10.0, 7.0, 7.7 Binnen de faculteit Wiskunde en Informatica wordt in het kader van het Stevin Centrum gewerkt aan een drietal hoofdthema's: 1. Toegepaste Analyse (Wsk) 2. Numerieke Analyse (Wsk) 3. Computer Graphics (Inf) 1. Binnen het hoofdthema Toegepaste Analyse zijn de volgende projecten te onderscheiden: a. Electromagnetisme, golfvoortplanting en diffractietheorie (o.a. in halfgeleiders). b. Interactie tussen thermo-elastische en electromagnetische velden in continue media. c. Problemen die in een industriële context een rol spelen, met name op het gebied van mechanica (elasticiteit, plasticiteit). d. Evolutievergelijkingen. In het bijzonder klassiek-analytisch èn functionaal-analytisch onderzoek aan niet-lineaire (vrije)-randproblemen. e. Elliptische operatoren. In het bijzonder 'niet-gladde' randwaardeproblemen voor 2e orde operatoren in divergentievorm en eigenschappen van kernen voor 'warmte-vergelijkingen' op Lie-groepen met een gewogen subelliptische operator als generator. a. Het onderzoek van de geometrie van de schouder van een verpakkingsmachine, verricht in samenwerking met het IWDE naar aanleiding van vragen vanuit de industrie, is voorlopig afgesloten met een publikatie in SIAM Review, verschenen in de rubriek Case Studies from Industry. Reeds langer werd vermoed dat de symbolische programmeertaal MATHEMATICA een bruikbaar hulpmiddel zou kunnen zijn voor de uitvoering van omvangrijke analytische berekeningen die zich voordoen bij de laag-frequente diffractie aan een obstakel. In het afgelopen jaar is MATHEMATICA gebruikt voor de berekening van de laag-frequente ontwikkeling van de "scattering coefficient" by akoestische of elektromagnetische diffractie aan een cirkelvormige schijf. De resultaten zijn gepubliceerd in een EUT Report; daarnaast zal nog een samenvatting van het rapport verschijnen als artikel in het ACES Journal. Een tweetal artikelen, betreffende accoustische oppervlaktegolven in gelaagde, elastische halfgeleiders, in samenwerking met Prof. B. Maruszewski, Poznan, is verschenen in de in 1995 gepubliceerde Proceedings van een IUTAM-Symposium over golven in vaste media. Een derde artikel is afgerond en zal ter publikatie worden aangeboden aan een internationaal tijdschrift. Voornemens op korte termijn Het verdere onderzoek, waarin MATHEMATICA een essentiële rol blijft spelen, is gericht op de berekening van de convergentiestraal van de laag-frequente ontwikkeling en op het verband tussen convergentiestraal en zgn. SEM-polen van de cirkelvormige schijf. Voorts zal het eerdere onderzoek van de laag-frequente diffractie aan een elliptische schijf weer worden opgevat. Het onderzoek naar halfgeleiders in samenwerking met Maruszewski zal in 1996 worden afgerond. b. Het promotie-onderzoek naar niet-lineaire visco-elastische stromingen, specifiek gericht op instabibiliteiten bij extrusie van polymeersmelts, zal naar verwachting in 1996 worden afgerond. Een artikel betreffende "Stability points of the Poiseuille flow of a KBKZ-fluid" is in 1995 gepubliceerd. Voordrachten over dit onderwerp werden gehouden op een tweetal HCM-meetings (ECMI) in Oxford en Milaan, op een ECMI-conferentie in Boekarest en op het Stevin-symposium in Rolduc, Kerkrade. Aangaande dit onderzoek bestaan, mede via IWDE, intensieve contacten met DOW-Benelux, Terneuzen, die dit onderzoek subsidieert. Verder zijn er op dit gebied nog contacten met DSM en KSLA en, binnen het Stevin-centre, met de polymeergroep van WFW-TUE.


Voornemens op korte termijn Het onderzoek naar the stromingsgedrag van polymeren zal, ook na de geplande promotie, worden voortgezet (via 2e fase-afstudeerders WvdI). c. Met Philips Nat.Lab. is er contact op het gebied van "Damage en scheurvoortplanting in brosse materialen". Een tweetal promotie-onderzoeken wordt begeleid, waarvan er een in februari 1996 zal worden afgerond. Als co-coördinator wordt opgetreden voor een INTAS-project met Armenië (INTAS-94-1210) met als coördinator Prof. G. Maugin, Université Pierre et Marie Curie, Paris. Deelnemers zijn Prof. S. Ambartsumyan, Yerevan State University, en Prof. M. Belubekian, Armenian Academy of Science, beide uit Armenië. Voor IWDE werd, buiten DOW-Benelux, nog gewerkt aan projecten voor BMD (spaakspanningsmeter; spakenmachine) en DAZON (vogelschrikkanon). Van het laatste project is een IWDE-rapport verschenen. Ook het promotie-onderzoek annex SOBU-project 92F: "Golden Ten", in samenwerking met KUB, nadert de afrondingsfase (eind 1996 - begin 1997). Een artikel betreffende de bewegingsvergelijkingen van Golden Ten, en hun asymptotische oplossingen, is ter publikatie ingediend bij een internationaal tijdschrift. Tevens werd een voordracht gehouden op een congres in Stockholm. Voornemens op korte termijn Het Golden Ten-project zal in 1996 worden afgerond. Naar verwachting zal in 1996 het INTAS-project getiteld: "Structural mechanics of electroconductive bodies" effectief worden opgestart. Kleine onderzoeksprojecten zullen incidenteel binnen komen via IWDE (o.a. BMD). d. De door ons bedachte quasi-lineaire versie van de Löwner Kufareev vergelijking blijkt een belangrijk hulpmiddel te zijn bij de studie van de Hopper vergelijking. Dit is een evolutievergelijking voor de tijdsafhankelijke conforme afbeelding van de eenheidsschijf naar een 2-dimensionaal domein dat ingenomen wordt door een vloeistof. Een belangrijk bijzonder geval is een visceuze vloeistof die beweegt onder de invloed van oppervlakte spanning op de rand. Hopper's hypothese over het bestaan van rationale oplossingen is veralgemeend en bewezen. Met door ons gevonden behoudswetten kunnen we voor een klasse van problemen het bestaan van globale rationale oplossingen bewijzen. Etc. etc. Deze resultaten zijn bevat in het proefschrift "Moving boundary problems in relation with equations of Löwner-Kufareev type" waarop Bart Klein Obbink op 1-12-1996 gepromoveerd is. Het functionaal analytisch onderzoek aan problemen voor vrije randen is toegespitst op het verkrijgen van stellingen over existentie, uniciteit en regulariteit van oplossingen van niet-lineaire evolutievergelijkingen voortkomende uit vrije randproblemen in de quasistationaire vloeistofdynamica, zoals Stokes flow en Hele-Shaw flow met oppervlaktespanning als drijvende kracht. De gebruikte methoden zijn heel divers en behelzen elliptische en parabolische PDV, niet-lineaire functionaalanalyse, differentiaalmeetkunde en symmetrie beschouwingen. In 1995 zijn, in samenwerking met prof. Günther van de universiteit Leipzig, enkele resultaten voor Stokes flow in willekeurige ruimtelijke dimensie verkregen. Het betreft hier de evolutie van stervormige gebieden. Voornemens op korte termijn. Verdere uitbreiding, zowel met betrekking tot toepassingen op Hele-Shaw flow als ook voor nietstervormige gebieden lijkt op redelijk korte termijn mogelijk. Begin 1996 zal over dit onderzoek een RANA rapport verschijnen. Eind 1996 zullen de contouren van een proefschrift over dit onderzoek zich duidelijk aftekenen. e. Tweede orde sterk elliptische operatoren met niet gladde begrensde coëfficiënten op een domein met randcondities zijn bestudeerd onder zwakke voorwaarden. Er is bewezen dat een gewogen subelliptische operator geassocieerd met een continue representatie van een Lie groep in een Banachruimte een continue halfgroep genereert. Voor de kern van deze halfgroep zijn Gaussische afschattingen bewezen. Voor de Gårding ongelijkheid zijn vele karakterizeringen gegeven. Deze projecten zijn afgesloten met RANA rapporten.


Voornemens op korte termijn. Optimale regulariteitseigenschappen afleiden voor tweede orde elliptische operatoren met complexe variabele coëfficiënten in termen van de regulariteit van de coëfficiënten. Samenwerking: prof.dr. B.L.J. Braaksma (RU Groningen) prof.dr. A.G. Tijhuis (TUE) prof. E. Heijman (Tel-Aviv University, Tel-Aviv, Israel) dr. M.E.J. Jenken (TUE) dr. H.P. Urbach (Philips Nat.Lab., Eindhoven) dr. N.M. Temme (CWI, Amsterdam) prof. D.S. Jones (University of Dundee, Dundee, Scotland) prof. R.E. Kleinman (University of Delaware, Newark, U.S.A.) prof. M.L. Glasser (Clarkson University, Potsdam, U.S.A.) prof.dr.ir. A.T. de Hoop (TU Delft) prof.dr.ir. H. Blok (TU Delft) prof.dr.ir. P.M. van den Berg (TU Delft) prof. S. Blume (Ruhr-Universität, Bochum, Duitsland) prof. E. Danicki (IPPT PAN, Warschau, Polen) prof. A. Ciarkowski (IPPT PAN, Warschau, Polen) prof. G. Kristensson (Lund Univeristy, Lund, Zweden) dr. N. Ortner (Universität Innsbruck, Oostenrijk) prof. D.W. Robinson (The Australian National University, Canberra, Australië) prof.dr. W. Arendt (Ulm, Duitsland) prof. P. Auscher (Amiens, Frankrijk) prof. E.B. Davies (Londen, U.K.) dr. X.T. Duong (Macquarie, Sydney, Australië) prof. P.E.T. Jørgensen ( Iowa, U.S.A.) prof. A. McIntosh (Macquarie, Sydney, Australië) prof. J. Nourrigat (Reims, Frankrijk) dr. E.-M. Ouhabaz (Noisy-le-Grand, Frankrijk) dr. R. Koopmans (DOW-Benelux) dhr. B. Best (Best Machine Development, Zuid-Oost Beemster) dhr. J. Frissen (DAZON B.V., Maastricht) prof.dr. B.B. van der Genugten (KUB) drs. J.C. de Vos (KUB) prof.dr. G.A. Maugin (Université Pierre et Marie Curie, Parijs, Frankrijk) prof.dr. S.A. Ambartsumyan (Yerevan State University, Yerevan, Armenië) prof.dr. M. Belubekian (Armian Academy of Science,Yerevan, Armenië) prof. B. Marszewski (Technical University Poznan, Poznan, Polen) ir. J.C.W. van Vroonhoven (Philips Nat.Lab., Eindhoven) dr.ir. P.P. Tas (DSM-Geleen) prof.dr. M. Günther (Universität Leipzig, Leipzig, Duitsland) prof.dr. R. Delange (Universiteit van Gent, Gent, België) dr. J. Cnops (Universiteit van Gent, Gent, België) dr. I. Raptis (University of Newcastle upon Tyne, U.K.) dr. Jaime Carvalho e Silva (Universidade de Coimbra, Coimbra, Portugal) prof.dr. G. Jank (RWTH-Aachen, Duitsland) prof.dr. F. Constantinescu (Universität Frankfurt am Main, Duitsland)


2. Binnen het hoofdthema Numerieke Analyse zijn de volgende projecten te onderscheiden: a. Sterk visceuze stromen b. Eindige differentie/volume methoden, in het bijzonder ten behoeve van combustion c. Poreuze media d. Meerrooster methoden, grote stelsels en parallel rekenen e. Differentiaal-algebraïsche vergelijkingen f. Eindige elementen methoden, in het bijzonder bij Navier-Stokes g. Numerieke simulatie van geofysische stromen h. Constructieve approximatie a. In het verslagjaar rondde G.A.L. van de Vorst als post-doc zijn onderzoek aan visceus sinteren van glasdeeltjes af. Er werden een aantal overzichtsartikelen en boekenbijdragen geschreven. Dit succesvolle onderzoek, waarbij veel ervaring is opgedaan met de boundary-element methode wordt helaas niet verder voortgezet. Het thema glas daarentegen heeft verdere uitbreiding gekregen. Zo houdt een AIO zich bezig met morfologie van glas bij persen van bijv. TV schermen en zijn een TWAIO en een afstudeerder tezamen met J.K.M. Jansen en R.M.M. Mattheij aan het onderzoeken hoe de parison, die bij het persen van glazen potten en flessen gevormd wordt, numeriek te simuleren. Naast de Stokes vergelijking, die met een FEM methode wordt opgelost, speelt ook de energie vergelijking een rol. Overwogen wordt een BEM/FEM aanpak. Voornemens op korte termijn Op korte termijn kan een meer realistisch temperatuurafhankelijk stromingsmodel geïmplementeerd worden. Verder verwachten we een uitbreiding van het onderzoek met warmte-overdracht door straling. b. Op het gebied van CFD zijn enkele interessante resultaten behaald. In september promoveerde A.C. Berkenbosch op een numeriek schema voor het oplossen van detonatie problemen (Euler met sterke bronterm). Dit onderzoek was gedeeltelijk ingebed in een groter samenwerkingsverband, "aardgasbranders", met L.P.H. de Goey (WOC) waarbij naast J.H.M. ten Thije Boonkkamp en R.M.M. Mattheij ook nog P.J.J. Ferket en een door Gastec gefinancierde OIO, B. van 't Hof, vanuit Wsk betrokken zijn. Deze laatste heeft een mooi exponentieel conservatief schema ontworpen en beschreven dat nu in vlamsimulaties wordt ingebouwd. Voornemens op korte termijn In de komende tijd zal numerieke analyse van streching, en 1-D tijdsafhankelijke vlammen nader onderzocht gaan worden. c. Het meerfase onderzoek in 1995 betrof het drooggedrag van kleivormen. Hieraan is door een afstudeerder met succes gewerkt. Mede door gezamenlijke actie met andere leden van het Stevin Centrum heeft dit geleid tot een succesvolle TDO-aanvraag, die in 1996 door een OIO in samenwerking met K. Kopinga (N) zal uitgevoerd worden; het betreft vochttransport in metselwerk . Daarnaast is een succesvolle aanvraag gedaan bij het interuniversitair verband RL-TUE (BMGT) voor onderzoek naar zwellingen in biologische materialen. Ook hier zal een OIO in 1996 aan gaan werken. De dagelijkse begeleiding is in handen van E.F. Kaasschieter. Voornemens op korte termijn Het komende jaar zullen de nieuwe OIO-projecten opgestart gaan worden. Naast het ontwikkelen van geschikte modellen zullen in eerste instantie eenvoudige (1-D) simulaties uitgevoerd gaan worden. d. Het onderzoek naar meerroostermethoden heeft een aantal resultaten te zien gegeven. Zo is er veel onderzoek gedaan aan meerroostermethoden die een, voor de praktijk belangrijke, robuustheid eigenschap hebben. Op het multigrid vakgebied staat dit onderwerp momenteel sterk in de belangstelling. Verder zijn niet-lineaire multigrid methoden onderzocht. In het kader van zijn promotie onderzoek heeft P.J.J. Ferket, samen met A.A. Reusken methoden onderzocht om op


samengestelde roosters randwaarde problemen op te lossen. Bij de zgn. LDC methode blijkt dit een snelle iteratie op te leveren. Ten gevolge hiervan kunnen discretisaties op samengestelde, maar locaal uniforme, roosters goed gebruikt gaan worden. Als post-doc heeft R. Stevenson domeindecompositiemethoden voor Poisson problemen onderzocht alsmede parallelle implementaties ervan. Voornemens op korte termijn Robuuste meerroostermethoden zullen verder theoretisch en implementatief onderzocht worden. Verder zal het onderwerp parallel rekenen een (hopelijk krachtige) impuls krijgen. Met enkele afstudeerders zal gewerkt worden aan de verdere implementatie van domeindecompositie methoden. e. Het onderzoek naar DAE komt, wat de promovendus P.M.E.J. Wijckmans betreft, in een afsluitend stadium. Er zijn interessante resultaten bereikt t.a.v. conditie en stabiliteit van index 1 en index 2 problemen. Onder andere is onderzocht wanneer dergelijke problemen in feite een hogere index bezitten (met daarmee numeriek onprettige eigenschappen). Een afstudeerder doet DAE onderzoek op het KSLA, waarbij hyperbolische problemen een rol spelen. Voornemens op korte termijn We verwachten dat de komende tijd een groot deel van de bereikte resultaten in artikelen uitgewerkt zullen gaan worden. f. Eindige elementen, en met name het pakket SEPRAN, spelen bij tal van projecten (waaronder enige van de bovengenoemde) een rol. Meer specifiek is gekeken naar alternatieven voor de penalty methode voor (Navier) Stokes. In het project "Koelingsgaten in turbine bladen", waar M.J. Noot (OIO) samen met J.K.M. Jansen in opdracht van ELDIM aan werkt is naar FEM ook een eindige volume simulatie uitgevoerd met FLUENT. Het lijkt erop dat de turbulenties met meer dan eenvoudige k-εmodellen onderzocht zullen moeten worden; er zijn geen quasi-stationaire oplossingen gevonden. Voornemens op korte termijn De komende tijd zal naast het verder vervolmaken van de code (een enkele simulatie kost vaak nog een week rekentijd) ook verdere analyse van de vergelijking een duidelijke aandacht krijgen. g. Het onderzoek naar contourdynamica van 2-D wervels vordert gestaag. In samenwerking met N wordt hier onderzoek aan gedaan door P.W.C. Vosbeek. Er is een leuk resultaat behaald waarbij tijdsdiscretisatie met een simplectische methode efficiënt uitgevoerd kon worden onder andere door gebruik te maken van Aitken extrapolatie. Voornemens op korte termijn De behaalde resultaten zullen ook voor het β-vlak en wellicht het γ-vlak toegepast gaan worden. h. Constructieve Approximatie Constructieve approximatie is het deel van de approximatietheorie dat zich bezig houdt met het ontwerpen en analyseren van constructieve methoden bij het berekenen en benaderen van functies en transformaties. Spline-approximatie en wavelet-transformaties kunnen als onderdeel van dit vakgebied worden beschouwd. - Het afgelopen jaar is het schrijven van een boek over Splines en Wavelets gestart (auteurs: C. Traas (UT), R. van Damme (UT), H.G. ter Morsche (TUE) dat in de bekende epsilon serie zal verschijnen en is het artikel "On the Chebyshev Norm of Polynomial B-splines in het tijdschrift Journal of Approximation Theory verschenen. - Een AIO van de tweede-fase opleiding Wiskunde voor de Industrie (H. Oltmans) heeft als opdracht van het bedrijf Joh. Enschedé in Haarlem een efficiënt algoritme ontwikkeld voor lijnendetectie i.v.m het coderen van beelden. - In de landelijke werkgroep Spline functies zijn voordrachten gehouden.


Voornemens op korte termijn - Afronden van een artikel over het gebruik van B-splines in de Short-Time- Fourier-transformatie. - Ontwerpen van Box-spline wavelets voor object herkenning in documenten bij Océ in Venlo als begeleiding tweede fase AIO Wiskunde voor de Industrie. Samenwerking: prof. R. März (Humboldt Universität, Berlin, Duitsland) prof. G. Söderlind (Lund Universitet, Lund, Zweden) prof. R. O'Malley (Washington State, Seattle, U.S.A.) prof. R. Klein (Technische Hochschule, Aachen, Duitsland) prof. H. Holden (Technical University, Trondheim, Noorwegen) prof. H. Neunzert (Universität Kaiserslautern, Kaiserslautern, Duitsland) prof. L. Kalachev (University of Montana, Missoula, U.S.A.) dr.ir. M.E. Kramer (KSLA, Amsterdam) dr.ir. G.A.L. van de Vorst (ATO-DLO, Wageningen) ir. M. van Dijk (ELDIM, Lom) ing. J. Goedegebure (Vereenigde Glasfabrieken, Maastricht) prof. G. de With (T/Philips Nat.Lab.) dr. L.P.H. de Goey (W) prof.dr.ir. K. Kopinga (N) dr.ir. L. Pel (N) prof.dr.ir. G.J.F. van Heijst (N) prof.dr.ir. A.A. van Steenhoven (W) dr.ir. J. Rijenga (T) prof. F. Binsbergen (KSLA/T) dr.ir. J. Huyghe (RL, Maastricht) prof. W. Hackbusch (Kiel) prof. J. Fuhrmann (Berlin, Duitsland) prof. Wittum (..., Duitsland) dr.ir. P. Sonnemans (Gastec, Apeldoorn) dr.ir. C.W.A.M. van Overveld (Informatica) dr. J. Laat (Grondmechanica, Delft) prof. J. Blij (Tübingen, Duitsland) prof. H. Yserentand (Tübingen, Duitsland) prof. R. Kornheber (Berlin, Duitsland) dr. K. Hemerik (Inf) prof.dr. C. Traas (UT, Enschede) dr.ir. R. van Damme (UT, Enschede) 3. Binnen het hoofdthema computer graphics zijn de volgende projecten te onderscheiden: a. Grafische algoritmen b. Computer animatie a. In het kader van het werk aan grafische algoritmen is voortgang geboekt (o.a. door de bijdragen van studenten als stage- of afstudeerprojecten) in de volgende richtingen: - implicit surface modellen: - een nieuwe categorie basisfuncties met aantrekkelijke eigenschappen t.a.v. ray-tracing - een set parameteriseerbare 'soft-CSG'-operaties op deze categorie basisfuncties - free-form surface modellering: - de generalisatie van een algoritme voor het afronden van polygonale meshes om te werken voor meshes met willekeurige topologische structuur, waarbij ook cirkelvormige i.p.v. polynomiale randen voortgebracht kunnen worden.


Door 1e fase en 2e fase studenten onder begeleiding van verslaglegger is gewerkt aan de volgende problemen: - de aansturing van deformaties in complexe polygonmeshes door middel van de beweging van kleine zgn. skelet-meshes - de simulatie van de stralengang in een electronenmicroscoop gemodelleerd met de GDP Over een aantal onderwerpen zijn manuscripten in voorbereiding resp. ter publikatie aangeboden aan internationale gerefereede tijdschriften. b. De activiteiten omtrent computeranimatie en de verdere uitbouw van de GDP zijn in een paraplu-project ondergebracht: AD REM (Accessing Distributed Resources via Executable Media). Hierover is een position paper geschreven; het centrale concept van AD REM is het begrip 'executable media' dat momenteel sterk in de internationale belangstelling staat i.v.m. Sun's Java/HotJava systeem. In het verslagjaar heeft Eric Peeters zijn proefschrift over de GDP met succes verdedigd. De recentste ontwikkelingen aan de GDP (deels uitgevoerd door H. van de Wetering en C. Huizing) zijn: - verbeterd geheugenmanagement - communicatie-primitiva om multi-user GDP applicaties te ondersteunen - vereenvoudigde invoering van nieuwe class-libraries op basis van C++-classes - realistische demo-applicaties, m.n. algoritme animatie, een assemblage-cel met 3-D robot, transportband en bewerkingsmachine en een kermisattractie - een verbeterde opzet voor de behandeling van rigid body dynamica waarbij de constraint beschrijving en de numerieke integratie methode van elkaar ontkoppeld worden. Buiten de context van de GDP is door van Overveld een interactief animatie-systeem ontwikkeld waarmee vlakke meetkundig constructies ingevoerd en real-time gemanipuleerd kunnen worden. Dit systeem dient als aanloop naar een interactief systeem voor interactieve 3-D meetkunde waarvan door een afstudeerder onderzocht wordt of het op de GDP geimplementeerd kan worden. Daarnaast is veel energie gestoken in de ontwikkeling van een software-bibliotheek ('GBOB') waarmee geometrische datastructuren gerepresenteerd kunnen worden ten behoeve van het verdere ontwikkelingswerk in animatie en geometrische modellering. Op basis van GBOB is onder andere een nieuwe versie van onze geometrische modeller gebouwd. Voornemens op korte termijn - consolidatie van de dynamica functionaliteit van de GDP - voortgang met botsingsdetectie en -afhandeling - het management van geometrische constraints - het creeeren van een aantal realistische applicaties op de GDP - de port van zowel GDP als GBOB naar OpenGl/Motif platforms om beide systemen device-indpendent te maken - geschikt maken van de GDP om het VRML-input format te lezen Daarnaast moet een begin gemaakt worden met de inzet van computer graphics expertise t.b.v. het GRID-project, alsmede mogelijk in enkele andere toepassingsgebieden (e.e.a. afhankelijk van de binnen de faculteit W&I op te starten onderwijsvernieuwings en studeerbaarheidsverbeteringsprojecten). Samenwerking: - in SOBU-verband: KUB (Tilburg), IPO, secties IS en PA (eindhoven) - advisering: faculteit W, N, TUE - software ondersteuning (GDP): faculteit IO, TUD - VU Academisch Ziekenhuis (Amsterdam) - vakgroep Analyse (in context van Stevin Centre: dr. H.G. ter Morsche: gezamenlijke opzet van een college Computational Imaging; prof.dr. R.M.M. Mattheij: ontwikkeling van de opzet van GRID en verdergaande samenwerking tussen Numerieke Analyse en Informatica)


-

Prof. B. Wyvill van de universiteit van Calgary. Stork Boxmeer: contract research betreffende kleurenquantisatie en digitale beeldbewerking t.b.v. textielindustrie (toestemming is verleend om het project een jaar voort te zetten) Roto Smeets de Boer Hilversum: in-house cursus digitale beeldbewerking (cursus zal in 1996 voor de derde achtereenvolgende keer gegeven worden). Philips Natlab, waar van Overveld sinds september '95 een adviseurschap bekleedt.


Tinbergen Instituut, verslag 1995 Programmaleiding

:


n.v.t. 5302, 2599 Milieu-economie S180 7.0

Dr. J. van Geldrop en dr. C. Withagen zijn in 1994 benoemd tot external research fellow van het Tinbergen Instituut. Hieruit vloeit voort dat zij actief deelnemen in de activiteiten van de onderzoeksgroepen die werkzaam zijn op het gebied van de economische theorie en op het gebied van de internationale en ontwikkelingseconomie. Dit komt tot uitdrukking in het bijwonen van seminars en het leveren van een bijdrage aan de discussion papers en de reprints van het Tinbergen Instituut. Er is onderzoek verricht op het terrein van de algemeen evenwichtstheorie en op het gebied van de milieu-economie. Op het eerste terrein zijn grote vorderingen geboekt in het bestuderen van economieën met een oneindig-dimensionale goederenruimte (mede in samenwerking met dr. S. van Eijndhoven). Begin 1995 valt een preprint op dit gebied te verwachten. In 1995 is een reprint uitgebracht van "General equilibrium in an economy with exhaustible resources and an unbounded horizon" (J. van Geldrop en C. Withagen) Journal of Economic Dynamics and Control 18, pp.1011-1035 , reprint 369. Voor wat betreft de milieu-economie is vooral gewerkt aan het aanpassen van het nationale inkomen als maatstaf voor duurzaamheid. Zie "On the concept of green national income" (C. Withagen en N. Vellinga) TI discussion paper 4- 95-238. Ook is gepubliceerd op het gebied van economische groei en milieu: "Pollution, Abatement and Balanced Growth" in Environmental and Resource Economics 5, pp. 1-8 (TI reprint 474). Tevens zijn er enige papers voor de discussion paper series aangeboden die momenteel worden herzien en in het lopende jaar zullen verschijnen.


IPA, verslag 1995 Programmaleiding

:


prof.dr. J.C.M. Baeten 1203 P175 10.0

1. Beknopte Inhoudelijke Beschrijving van het Programma De belangrijkste karakterisering van het binnen IPA te verrichten onderzoek is de fundamentele aanpak, daarbij geïnspireerd door problemen die in de praktijk spelen. Het onderzoek binnen de onderzoekschool omvat drie hoofdthema's: de Algoritmen en Complexiteit, de Formele Methoden en de Software Technologie. Deze vakgebieden vormen de monodisciplinaire kernen van onderzoek binnen de onderzoekschool en worden gekarakteriseerd door de voor ieder van deze thema's kenmerkende stijl van werken. In principe betreffen het blijvende samenwerkingsverbanden tussen onderzoekers die binnen de aangegeven thema's werkzaam zijn en zij vormen als zodanig de werkgebieden van de onderzoekschool. Naast (of beter, in combinatie met) deze hoofdthema's zijn er drie speerpunten van onderzoek. Deze speerpunten dienen als een (interdisciplinaire) clustering van bestaand onderzoek maar ook als een basis voor nieuwe samenwerking binnen IPA. De drie speerpuntprogramma's zijn Software Quality and Production, Wide Area Distributed Systems en Embedded Systems. · Algoritmen en Complexiteit Algoritmen vormen van oudsher de bouwstenen waaruit programmatuur is opgebouwd. Elke techniek van informatieverwerking is gebaseerd op precieze algoritmische principes die in programmatuur uitgewerkt moeten worden. Het resultaat van het onderzoek naar algoritmen is soms kant en klaar inpasbare programmatuur, maar vaker wordt gestreefd naar algemene theorie voor klassen van algoritmische vraagstukken en een analyse van de mogelijkheden en onmogelijkheden voor hun praktische (lees: efficiënte) oplosbaarheid. Het ontwerp van algoritmen vereist een eerste modelleringsslag in een programmeerprobleem en maakt de keuzen zichtbaar in de mogelijke berekenings- of verwerkingswijzen die elk voor zich diep kunnen ingrijpen op de prestatie van de uiteindelijke programmatuur in de praktijk. Het onderzoek (c.q. de analyse) van algoritmen speelt daarmee een fundamentele rol in de ontwikkeling van efficiënte programmatuur. Het onderzoek richt zich op de ontwikkeling van modellen en methoden die een realistische analyse en vaststelling van de complexiteit van algoritmen mogelijk maakt. Het gebied van het algoritmenonderzoek kan onderverdeeld worden in een aantal hoofdgebieden: 1. het ontwerp en de analyse van sequentiële algoritmen, met nadruk zowel op de algemene technieken van datastructurering als op de vraagstellingen van brede toepassingsgebieden. Ook wordt hier de complexiteitstheorie ontwikkeld voor concrete klassen van algoritmische problemen, om de kenmerken van optimale algoritmen te achterhalen. 2. het onderzoek van de algoritmische mogelijkheden van nieuwe computer- of structuren, waarbij berekenings bijv. de berekeningscomplexiteit van parallelle systemen (parallelle en gedistribueerde algoritmen), van 'massively parallel systems' (zoals neurale netwerken) of zelfs van geheel nieuwe berekeningsconcepten (genetisch programmeren, machine learning) aan de orde is. Het onderzoek richt zich ook op het ontwerp en de analyse van algoritmen voor de nieuwe berekeningsstructuren en de bijbehorende complexiteitstheorie. 3. de experimentele algoritmiek, waarin het gebruik van algoritmen wordt getest in de praktijk en de beste vormen van 'algoritme engineering' in specifieke toepassingen worden onderzocht.


Een andere indeling van het onderzoeksgebied is mogelijk uitgaande van de toepassingsgebieden, zoals: de systeemsoftware (bijv. het ontwerp van efficiënte algoritmen voor communicatie en coördinatie), de support-software (bijv. het ontwerp van algoritmen voor de computer graphics en de robotica), de 'computational science' (bijv. het ontwerp van methoden voor parallelle computers en de 'high performance computing'), de 'operations research' (bijv. het ontwerp van algoritmen voor 'combinatorische optimalisering'), en de kunstmatige intelligentie (van neurocomputing tot 'computational learning'). De nadruk ligt op de ontwikkeling van efficiënte methoden met algemene toepasbaarheid in bestaande en toekomstige hard- en software entourages. · Formele Methoden In de begintijd van het gebruik van computers stonden de numerieke en administratieve toepassingen op de voorgrond. Hoe de programmering plaats vond en het redeneren over de correctheid van de programma's, was vaak een zaak van secundair belang. Met het groeien van het belang van een veel groter aantal gebieden waar computers toegepast worden, de groeiende samenhang tussen systemen en de toenemende maatschappelijke afhankelijkheid van correct functionerende systemen, neemt het belang van de formalisatie sterk toe. Vragen die daarbij aan de orde komen zijn onder meer: 1. hoe in een (programmeer)taal uit te drukken wat er dient te gebeuren (specificatie) 2. hoe de betekenis van dergelijke talen vast te leggen (semantiek) 3. hoe programma's in dergelijke talen te schrijven (methodologie) · Software Technologie Hier richten we ons op de problemen die direct samenhangen met de daadwerkelijke constructie van programmatuur. We onderscheiden daarbij drie deelgebieden: 1. het hulpmiddelen-aspect, bijv. de generatie van executeerbare programma's uit een formele beschrijving en de bouw van software-systemen, die activiteiten op het gebied van de algoritmen en formele methoden ondersteunen 2. het produkt-aspect, d.w.z. het beantwoorden van de vraag hoe men algoritmische oplossingen samen kan stellen tot een samenhangend, efficiënt werkend geheel. We duiden dit ook wel aan met de term software-architectuur. 3. het produktie-aspect, waarbij de processen die spelen bij de constructie van programmatuur bestudeerd worden. Speerpunten Software Quality and Production Software is een factor van toenemend economisch belang. Het speelt een cruciale rol in de concurrentiepositie van veel bedrijven. Dankzij de gestage daling van de prijs/prestatie verhouding van de hardware, zijn nu de programma's (de 'software') de kritische factor. De kwaliteit van de software beïnvloedt in grote mate de prestatie van bedrijven. Onder kwaliteit van software verstaan we hier gebruikersvriendelijkheid, correctheid, efficiëntie, 'portability' en betrouwbaarheid. Door de toegenomen kennis op het gebied van computers zowel binnen de bedrijven als onder het algemene publiek zullen deze zich meer en meer bewust worden van de functionaliteit en de betrouwbaarheid van software produkten. Als een gevolg daarvan zullen hogere eisen aan de kwaliteit van software gesteld worden. Wide Area Distributed Systems Met de komst van goedkope en betrouwbare communicatie tussen machines is er ook een hele klasse van problemen actueel geworden die vroeger slechts in afzondering of vanuit een puur theoretisch standpunt bekeken werden. Eén van de belangrijkste kenmerken van de huidige tijd is dat - net zoals het niet langer mogelijk is één enkele machine in afzondering te beschouwen - het niet langer mogelijk is om individuele problemen in afzondering te bestuderen. In het bijzonder wanneer veel verschillende machines (met ieder zijn eigen operating systeem) met elkaar samenwerken, moeten veel problemen tegelijkertijd opgelost worden. Onderzoeksonderwerpen die daarbij naar voren komen zijn 'inter operability' (de soepele samenwerking tussen verschillende machines en


systemen in een netwerk), 'state maintenance' (het doorzichtig maken van de toestand van de omgeving voor een gebruiker) en 'self-organisation' (hoe kan een individuele component (systeem) zichzelf aanpassen aan veranderingen in zijn omgeving (netwerk)). Embedded Systems Embedded Systems zijn computer systemen die een integraal onderdeel vormen van een groter systeem, zoals een regelaar van een centrale verwarming of een vliegtuig. In het algemeen wordt een embedded systeem gebruikt voor het controleren (en sturen) van een industrieel of fysisch proces. Sensoren verzamelen informatie uit de omgeving die vervolgens door het embedded system verwerkt wordt waarna het een signaal uitzendt naar de actoren, ter sturing van het mechanische proces. Dit betekent dat bij het ontwerp van een embedded system (en het redeneren erover) altijd de omgeving betrokken moet worden. In informatica-termen zijn embedded systemen dus gedistribueerde reactieve systemen. Daarnaast speelt 'real-time' een cruciale rol in embedded systemen. Een paar belangrijke (onderzoeks)onderwerpen op het gebied van embedded systemen zijn de verlengde levensduur van produkten (een embedded system moet net zolang mee kunnen als het systeem waar het een onderdeel van is), de interactie met de omgeving, de produktiviteit en de betrouwbaarheid. 2. Bereikte Resultaten van IPA in 1995 IPA heeft in 1995 de jaarlijks terugkerende Introductiedagen en Terugkomdagen georganiseerd. De Terugkomdagen hadden als thema 'Programmatuurkunde en Algoritmiek in Praktijk' en werden gehouden op 9 en 10 maart 1995 in Veldhoven. De Introductiedagen hadden als thema 'Program Verification for the Working Computer Scientist' en werden gehouden van 16 tot en met 18 oktober in Egmond aan Zee en Amsterdam (CWI). De Introductiedagen werden gevolgd door Terugkomdagen, die als thema hadden 'Using Theorem Provers/Proof Checkers for formalising Correctness Proofs of Programs' (19 -20 oktober, Amsterdam (CWI)). Daarnaast is ter gelegenheid van de oprichting van IPA een Oprichtingsbijeenkomst gehouden. Door IPA gesponsorde gasten in 1995 waren Prof. Shirazi, november 1995, gast van Prof.dr.dipl.ing. D.K. Hammer (TUE) en S. Smolka (SUNY Stony Brook, USA), juni 1995, gast van Prof.dr. J.C.M. Baeten. In het kader van de nationale en internationale positionering van IPA is druk gewerkt aan het leggen van contacten met zusterinstellingen en de industrie. Samen met de Deense onderzoekschool BRICS (Basic Research in Computer Science) en de Finse onderzoekschool TUCS (Turku Centre for Computer Science) zal een jaarlijks terugkerende bijeen-komst worden georganiseerd met als doel education of researchers. De vorm van deze bijeenkomsten zal het midden houden tussen een internationale conferentie en een workshop met tutorials. IPA zal de eerste bijeenkomst organiseren in november 1996. Verder is er samen met BRICS, TUCS, RHUL (Royal Holloway University of London) en INPG (Institut National Polytechnique de Grenoble) een aanvraag voor een TMR netwerk (Training and Mobility of Researchers) ingediend bij de EG en tevens een aanvraag om in combinatie met dit netwerk een serie Europese zomerscholen te organiseren. Met enkele bedrijven zijn contacten gelegd voor sponsoring en het opzetten van gezamenlijke onderzoeksprojecten.


Bereikte resultaten per onderzoeksgroep Sectie PA, Groepen Rem, Hilbers Ontwerpen van parallelle programma's 1. Het onderzoek in de ontwerpmethode van parallelle programma's die gebaseerd is op input/output-relaties is in 1995 voortgezet. Voor de prestatieanalyse van deze programma's is het formalisme uitgebreid met een maat voor het energiegebruik. Er wordt thans gewerkt aan ontwerpmethoden die specifiek zijn gericht op het verkrijgen van energiezuinige programma's. 2. Om de grenzen van de input/output-gebaseerde methode te verkennen zijn een aantal problemen bij de hand genomen die traditioneel op een toestand-gebaseerde wijze worden opgelost. Het betreft hier blok-berekeningen en berekeningen met lokale variabelen. Deze problemen lijken ook zeer goed oplosbaar in het input/output-formalisme. De echte grens van de methode lijkt pas bereikt te worden bij data-afhankelijk gedrag. Implementeren van parallelle programma's op multicomputers 1. De communicatie bibliotheek ECL (Eindhoven Communication Library) is geïmplementeerd op zowel de transputer systemen als de Power Xplorer van de vakgroep. Deze bibliotheek combineert een krachtig interface met een lage overhead en ondersteunt op deze wijze het maken van overdraagbare parallelle programma's. In het kader van een industriële toepassing is ook een implementatie gerealiseerd voor de Texas Instruments C40 processor. Op basis hiervan is een parallel programma ontworpen en geïmplementeerd wat met behulp van twee 2-dimensionale beelden van een scene, een nauwkeurig 3-dimensionaal beeld kan opbouwen. In het vervolg van dit project hiervan zal worden gekeken naar een uitbreiding van de bibliotheek, zowel van de interface als van het aantal platforms dat wordt ondersteund. 2. In samenwerking met de faculteit Chemische Technology van de TUE wordt onderzoek gedaan naar Monte Carlo methoden voor het simuleren van katalytische reacties. Als eerste studie is een parallel programma voor de simulatie van een specifieke reactie geschreven. Vervolgens is een meer algemeen sequentieel programma ontwikkeld wat in een volgend stadium moet worden omgezet tot een parallel programma. 3. Vanuit de TUE wordt een project begeleid bij KSLA (Shell Amsterdam) waarin een bibliotheek wordt ontwikkeld waarmee parallelle file i/o wordt ondersteund. De interface is een uitbreiding op het C-interface voor standaard i/o. De bibliotheek biedt krachtige primitiva voor het distribueren en vergaren van gegevens en is geschikt voor systemen met gedistribueerd geheugen en een Single Program, Multiple Data model van programmeren. Asynchrone schakelingen 1. In de zomer van 1995 eindigde het OMI/EXACT project (ESPRIT 6143), waarin als subcontractor van Philips studie is gemaakt naar de industriële toepasbaarheid van asynchrone schakelingen. In dit verband is vooral gewerkt aan single-rail implementaties van handshake schakelingen. In de loop van '96 zal het proefschrift van Ad Peeters hierover verschijnen. Verder is in 1995 gewerkt aan nieuwe implementaties van control-componenten. Het EXACT-project was zeer succesvol. Het OMI Management Office was zeer teleurgesteld dat Philips geen vervolgproject wilde aanvragen. 2. Het onderzoek naar het testen van asynchrone schakelingen vordert goed. Rik van de Wiel verwacht in 1996 zijn proefschrift hierover af te ronden. 3. De groep Parallellisme en Algoritmen ontwikkelt en bestudeert de ontwerpomgeving DEDIC (Design Environment for Delay-Insensitive Circuits). De nadruk ligt hierbij op het inventariseren van de problemen, die bij de ontwikkeling van zo'n omgeving een rol spelen, en op het vaststellen van welke vrijheden er zijn om deze problemen op te lossen; we zijn niet in de eerste plaats geïnteresseerd in het bouwen van een omgeving, die ons in staat stelt om snelle, kleine of energie-zuinige ontwerpen te maken. Wij stellen de nauwe samenwerking met Philips Research Eindhoven bijzonder op prijs.


Tot nog toe hebben wij ons vrijwel uitsluitend toegelegd op het eerste stuk van de ontwerpomgeving: - de definitie van SuperVokel SuperVokel is een parallelle programmeertaal waarin communicatie-primitieven om data via kanalen te verzenden en te ontvangen aanwezig zijn. - de definitie van HSC (HandShake Circuits) is een licht-gewijzigde versie van een door een Philips Research gedefinieerde voorloper van HCL (Handshake Circuit Library); HCL is een bestanddeel van het DICY-project van Philips Research. - de vertaling van SuperVokel-programma's naar HSC-circuits. We hebben als intermediair de taal Vokel gedefinieerd. Vokel is een parallelle programmeertaal (zoals SuperVokel) echter zonder enige structurele hiërarchie (zoals HSC). - de analyse van HSC-circuits. We hebben de grafische interface GraphEdit en de simulator Hcsim ontwikkeld. Verder hebben we de compiler Hscl gebouwd; Hscl kan gebruikt worden om HSC-circuits naar HCL-circuits te vertalen en omgekeerd. In 1995 hebben versie 3.0 van DEDIC ontwikkeld; in versie 3.0 zit een uitgebreide versie van SuperVokel, waarin array-indexering met gebruikmaking van variabelen mogelijk is. Verder kan de DEDIC-omgeving gebruikt worden via een gebruikersvriendelijke user-interface. De groep Parallellisme en Algoritmen ontwikkelt en bestudeert de ontwerpomgeving DEDIC (Design Environment for Delay-Insensitive Circuits). De nadruk ligt hierbij op het inventariseren van de problemen, die bij de ontwikkeling van zo'n omgeving een rol spelen, en op het vaststellen van welke vrijheden er zijn om deze problemen op te lossen; we zijn niet in de eerste plaats geïnteresseerd in het bouwen van een omgeving, die ons in staat stelt om snelle, kleine of energie-zuinige ontwerpen te maken. Wij stellen de nauwe samenwerking met Philips Research Eindhoven bijzonder op prijs. Tot nog toe hebben wij ons vrijwel uitsluitend toegelegd op het eerste stuk van de ontwerpomgeving: - de definitie van SuperVokel SuperVokel is een parallelle programmeertaal waarin communicatie-primitieven om data via kanalen te verzenden en te ontvangen aanwezig zijn. - de definitie van HSC HSC (HandShake Circuits) is een licht-gewijzigde versie van een door een Philips Research gedefini-eerde voorloper van HCL (Handshake Circuit Library); HCL is een bestanddeel van het DICY-project van Philips Research. - de vertaling van SuperVokel-programma's naar HSC-circuits. We hebben als intermediair de taal Vokel gedefinieerd. Vokel is een parallelle programmeertaal (zoals SuperVokel) echter zonder enige structurele hiërarchie (zoals HSC). - de analyse van HSC-circuits We hebben de grafische interface GraphEdit en de simulator Hcsim ontwikkeld. Verder hebben we de compiler Hscl gebouwd; Hscl kan gebruikt worden om HSC-circuits naar HCL-circuits te vertalen en omgekeerd. In 1995 hebben versie 3.0 van DEDIC ontwikkeld; in versie 3.0 zit een uitgebreide versie van SuperVokel, waarin array-indexering met gebruikmaking van variabelen mogelijk is. Verder kan de DEDIC-omgeving gebruikt worden via een gebruikersvriendelijke userinterface. VLSI-programmeren voor energiezuinigheid Dit is een AIO-project dat door Hans van Gageldonk wordt uitgevoerd op het Nat.Lab. van Philips. Als test case voor onze ideeën op het gebied van energiezuinige programma's werkt hij aan een eenvoudige controller. De eerste resultaten zullen in de loop van 1996 beschikbaar komen. Scheduling-technieken voor multi-mediaspelers Dit is een AIO-project dat door Ramon Clout wordt uitgevoerd op het Nat.Lab. van Philips. Het gaat hier om off-line scheduling, waarbij het de kunst is om de regelmaat van de audio- en videoverwerking zoveel mogelijk uit te buiten.


Algoritmen en datastructuren 1. In het verslagjaar is het onderzoek op het gebied van leaf trees afgerond. Als grotere toepassingen van de ontwikkelde decompositiemethode is deze met succes toegepast op het klassieke probleem: de (dynamische) berekening van de contour van een collectie rechthoeken onder toevoegingen en/of verwijderingen van rechthoeken. Er is een classificatie van implementaties van diverse types priority queues vastgelegd. Daarnaast is een nieuwe implementatie, gebaseerd op leaf trees van double ended mergeable priority queues ontworpen. Deze is optimaal qua tijd en ruimte en veel eenvoudiger dan bestaande oplossingen. Een publikatie hierover in 1996 ligt voor de hand. 2. Er is een aanvang gemaakt met het onderzoek naar methoden voor het ontwerpen van objectgeoriënteerde programmaconstructies. 3. Er is een real-time garbage collection schema ontworpen voor acyclische pointerstructuren. Hierbij is de hoeveelheid gealloceerd geheugen nooit meer dan de maximaal benodigde hoeveelheid geheugen. De garbagecollectie is zodanig verdeeld dat allocaties en de-allocaties van geheugen in constante tijd plaatsvinden. Een publikatie hierover wordt in 1996 verwacht. Sectie PA, Groep Aarts Our research is concerned with the design and analysis of models and algorithms for combinatorial optimization problems in planning and design. Central issues in this respect are the development and complexity analysis of appropriate combinatorial models, and the design of heuristic algorithms that can find good solutions to the problems raised by these models. The central issue of our application domain is resource constrained scheduling and the industrially relevant applications we have studied include multi-media server systems, hardware software co-design, mapping of video algorithms onto massively parallel processors, high-level synthesis of video systems, production planning, and handwritten character recognition. Local search is the central issue in our studies of heuristic algorithm, which includes topics as simulated annealing, constraint satisfaction, genetic algorithms, and neural networks. For the analysis of new ideas for these techniques we often use parallel implementations on large multi-processor systems such as the Parsytec GCel (with 512 nodes) or the Parsytec PowerXplorer (with 32 nodes) of the SARA computing center. Much of the work is carried out in close collaborations with the groups of prof. Lenstra (TUE), prof. Wessels (TUE), and with the Philips research laboratories in Eindhoven. Clearly, there is also a close collaboration with the groups of profs. Hammer, Hilbers and Rem (all TUE). We have developed implementations of local search algorithms that belong to best in the world. For the traveling salesman problem, the Steiner tree problem on graphs, and the job shop scheduling problem we are recognized world record holders in the sense that our algorithms can find the best approximative solutions to these problems for given amounts of running times. In addition, we have successfully transferred our knowledge of heuristic search to the problem of handling industrially relevant decision situations such as the scheduling of multi-media servers, the problem of mapping video algorithms onto multi-processor systems, problems in the field of the high-level synthesis of VLSI systems, and the problem of recognizing on-line handwritten characters. Our more theoretical work has contributed to the complexity analysis of feed-forward neural networks, the probabilistic analysis of local search, the modeling of periodic scheduling problems, and in the development of effective consistency checking algorithms. Sectie PA, Groep Hemerik Taxonomieen van Implementatiemethoden Dit onderzoek heeft geresulteerd in een drietal taxonomieen van algoritmen op de volgende gebieden: - Patroonherkenning in strings - Constructie van eindige automaten


- Minimalisatie van eindige automaten Op grond van deze taxonomieen zijn twee toolkits van algoritmen geconstrueerd in de vorm van C++ class libraries. Tevens zijn uitgebreide benchmarks uitgevoerd, met een aantal verrassende resultaten. Al deze resultaten zijn vastgelegd in het proefschrift van Bruce W. Watson. Het onderzoek heeft tevens geresulteerd in afleidingen en implementaties van een hele klasse van sublineaire algoritmen voor multiple keyword matching in strings. Daarover is gerapporteerd in een rapport van Watson en Zwaan. De geconstrueerde toolkits zijn vrij beschikbaar via ftp. Zie punt g. Typetheorie In het verslagjaar is voornamelijk gewerkt aan de uitbreiding van het systeem λωL in de richting van een praktisch bruikbare programmeertaal. In bijzonder is onderzocht hoe constructies uit objectgeoriënteerde talen uitdrukbaar zijn in λωL. De resultaten zijn vastgelegd in een rapport van Zwanenburg. Een artikel van Hemerik geeft een eenvoudige inleiding op dit onderwerp. Hemerik en Franssen (AIO) zullen verder werken aan ontwerp en implementatie van het systeem in de vorm van een geïntegreerde programma- en bewijseditor. Sectie WP, Groep Backhouse De theorie van reductivity (well-foundedness relatief aan een datatype) is verder ontwikkeld. Een paper hierover is gepresenteerd bij de conferentie Mathematics of Program Construction en een journal article is inmiddels geaccepteerd voor publikatie. Voortgang is ook geboekt bij de categorie theorie als constructieve tralie theorie. Toevoegingen aan de al door ons afgeleide stellingen zijn de zgn. monad decompositie stelling. Een monograph hierover is in voorbereiding; een eerste versie is al beschikbaar gemaakt op de web. Veel voortgang is geboekt mbt commuting relators (wanneer twee data structuren kunnen worden omgedraaid). Een specificatie is gevonden voor het begrip "commuting relators'' waardoor bepaalde gewenste algebraïsche eigenschappen vanzelfsprekend worden. Het is bewezen dat bekende constructies van commuting relators toch aan deze zeer sterke specificatie voldoen. Deze onderwerpen heb een allemaal betrekking op de ontwikkeling van een algebra van datatypen. Ontwikkeling van het MathSpad system gaat door. MathSpad is een innovatieve structure editor voor document preparation. Het unieke van MathSpad is de "stencil'' mechanisme die twee "views'' van een document geeft: de screen view en de output view. Door de flexibiliteit van de mechanisme kan MathSpad worden gebruikt om documenten in allerlei markup talen te maken -- in het bijzonder LaTeX maar ook troff en html, bijvoorbeeld. Het systeem is voor het eerst officieel aangekondigd bij de comp.os.linux.announce newsgroup aan het eind van oktober 1995. Tussen oktober 1995 en eind december 1995 is het systeem maar liefst circa 300 keer met succes geïnstalleerd. Het systeem is beschreven als 'a wonderful tool'. Sectie TT, Groep Hammer Construction of Object-Oriented Real-Time Systems Taxanomie en evaluatie van talen voor de constructie van object-georiënteerde real-time systemen (Dieter Hammer en Onno van Roosmalen). Om tot de definitie van een geschikte taal voor de constructie van OORTS (Object Oriented Real-Time Systems) te komen, is het eerst nodig om zoveel mogelijk bestaande ontwerp methoden en talen te evalueren. Voor dit doel is een taxonomie m.b.t. de objectgeoriënteerde, de concurrency, de real-time, de fault-tolerance, de allocatie en de algemene characteristieken ontwikkeld. Deze taal is toegepast op twee talen : Ada 95 en Deal. Aan de evaluatie van andere talen en ontwerp methoden wordt gewerkt. Real-time extensies van (object-georiënteerde) talen (Onno van Roosmalen, Jozef Hooman). Het doel van dit onderzoek is een timing constraint specificatie methode voor real-time programma's te


ontwikkelen die programma's en programma onderdelen onafhankelijk houd van het onderliggende executie platform. Concreet betekent dit dat de timing constraints zo zijn geformuleerd dat de semantiek van het programma niet afhankelijk is van bijvoorbeeld de executie snelheid van de processoren, de distributie van het programma over de processoren, de scheduling methode die wordt toegepast. De eerder voorgestelde methode voor het vastleg gen van real-time constraints in programma's is verder onderzocht op zijn geschiktheid. Daar toe zijn de volgende stappen ondernomen: 1. Er is een simpele concurrente taal gedefinieerd met deze timing extensies. 2. Met behulp van deze taal is een standaard processbesturingsprobleem uit de literatuur uitgewerkt. 3. De feasibility van het construeren van schedule op verschillende manieren is aangetoond. Het ligt in de bedoeling de correctheid van het programma, ook met betrekking tot de vereiste tijdigheid, formeel te bewijzen uit de semantiek van de individuele programma statements. Rpc-implementatie (samen met Pim Lemmens) Er is verder gewerkt aan het ontwerp en de implementatie van een RPC mechanisme voor DEAL. E.e.a. zal worden vastgelegd in een publikatie. Tools onderzoek (Onno van Roosmalen) In het kader van een nieuw gestart initiatief dat heeft vorm gekregen in een "Software Technology Expertise Center" van de Vakgroep Informatica, zijn verschillende studies naar software ontwikkel tools uitgevoerd. Deze studies zijn verricht in opdracht van derden, zodat deze inspanningen bijna volledig extern gefinancierd werden. Het doel van dit soort onderzoeken is: 1. Een goed inzicht te krijgen in de huidige stand van zaken met betrekking tot ontwerpmethodes en de ondersteuning daarvoor. 2. Ideeën te ontwikkelen met betrekking tot verbetering van de methodes en eventueel voorstellen te doen in de richting van een "ideale" methode. 3. Informatie te verschaffen aan derde met betrekking tot de bovenstaande onderwerpen. Betekenis van timing annotaties (Rob Hoogerwoord en Onno van Roosmalen) Uiteindelijk moet dit onderzoek leiden tot inzicht in hoe real-time programma's systematisch kunnen worden gespecificeerd en ontworpen. Formele specificatie en verificatie van gedistribueerde real-time systemen (Jozef Hooman) Ook aspecten van fout-tolerantie zijn daarbij bestudeerd. Verder is er intensief gewerkt met de interactieve proof checker PVS (Prototype Verification System), als ondersteuning bij bovengenoemde activiteiten. Werk met Y. Lakhneche (Kiel) aan een integratie van Metric Temporal Logic en de Duration Calculus is afgerond middels een artikel in een tijdschrift. Werk met P. Zhou op het gebied van de formele verificatie van fout-tolerante algorithmen is afgerond met een tijdschrift artikel over de verificatie van een atomic broadcast protocol. Een al eerder ontwikkeld eigen real-time formalisme, gebaseerd op Hoare tripels, is toegepast op een aantal voorbeelden. Verder is een hoofdstuk geschreven voor het boek "Real Time Systems: "Specification, Verification and Analysis", editor Mathai Joseph. Hiervoor is een mine pump control voor beeld uitgewerkt. Er is onderzoek gedaan naar het gebruik van de interactieve proof checker PVS voor de formele verificatie van (real-time) systemen. Een aantal activiteiten in dit verband: - Het eigen real-time formalisme is ingebed in PVS en met J. Vitt (Kiel) is een besturingssysteem gespecificeerd en geverifieerd in PVS. Als voorbeeld is gekozen voor het "Steam-boiler control specification problem". Dit werk is gepresenteerd op een Dagstuhl seminar en een artikel is ter publikatie ingediend. - Een specificatieprobleem, voorgesteld door van Broy en Lamport in het kader van een Dagstuhl seminar, is volledig uitgewerkt in PVS. Het is ingediend voor publikatie in de proceedings van dit seminar. Static Scheduling Scheduling model en algoritmen (Dieter Hammer, Erik Luit, Paul van Gorp) DEDOS garandeert dat deadlines van HRT taken gerespecteerd worden m.b.v. statische (off-line) scheduling. Tijdens het promotieonderzoek van J.P.C. Verhoosel is een statische scheduler ontwik


keld. In het afgelopen jaar is het SION project "Hard Real-Time Scheduling for DEDOS" gestart. De doelen van dit project zijn de uitbreiding van de scheduling algoritmen zodat de volledige functionaliteit vereist voor DEDOS ondersteund wordt en het verbeteren van de performance van de scheduler. De bestaande HRT scheduler is geëvalueerd en het scheduling model dat aan de scheduler ten grondslag ligt is herzien naar aanleiding van deze evaluatie. Run-time ondersteuning voor statische scheduling (Erik Luit) Statische scheduling vereist ondersteuning vanuit het operating systeem door een on-line scheduler om o.a. de juiste taak op het juiste tijdstip op te starten en te onderbreken. Er is onderzocht hoe een eerder ontwikkeld prototype on-line scheduler ingebouwd moet worden in het operating systeem ter verbetering van de efficiëntie. Een mechanisme om HRT taken op de juiste punten te onderbreken is verder uitgewerkt. Distributed Algorithms and Dynamic Scheduling Real-time databases (Peter van der Stok en Maarten Bodlaender) Scheduling mechanismes voor real-time databases worden geanalyseerd en ontworpen. Met name wordt rekening gehouden met de analyseerbaarheid en het real-time gedrag van nieuw ontworpen schedulers. Gedistribueerde algoritmen (Peter van der Stok, Dick Alstein en Alexandra Janssen) De DEDOS protocol stack is verder uitgewerkt en geïmplementeerd. Formele specificatie en verificatie (Jozef Hooman) Zo is werk aan een real-time arbitratie protocol (van de Futurebus) afgerond met een publikatie. Een voorbeeld van het Philips Nat. Lab., het ACCESS.bus protocol, is gedeeltelijk uitgewerkt in PVS. Dit heeft geleid tot de presentatie (en publikatie) op een conferentie. Voor het zogenaamde "causal delivery" protocol is een (bekend) algoritme formeel afgeleid. Verder zijn, mede voor het onderwijs, notities geschreven over "progress, deadlock, and individual starvation" en over toepassingen van de "split binary semaphore". Kloksynchronisatie (Erik Luit) Zowel de scheduler als diverse communicatie protocollen veronderstellen dat de klokken binnen het systeem nauwkeurig synchroon lopen. Hiertoe is in voorgaande jaren een kloksynchronisatie protocol ontwikkeld dat slechts infrequent geëxecuteerd hoeft te worden doordat klokken gecorrigeerd worden voor lokale drift. Dit protocol is gegeneraliseerd naar meer algemene netwerk typologieën. Tevens is een hiërarchische versie van het protocol ontwikkeld dat gecombineerd kan worden met het hiërarchisch membership protocol. Requirements Engineering Systematisch afleiden van de specificaties van gedistribueerde real-time systemen uit het te ondersteunen proces (Dieter Hammer en Jozef Hooman) Embedded systems have to support a production or usage process. This asks for a top- down approach that starts from a, possibly reengineered, business process. In the past, however, the designers of embedded systems used to start from a functional break-down of the environment. This is a static and structure-oriented view as opposed to a dynamic and process-oriented one. In addition, the design was was often driven by technological possibilities and choices and did not pay enough attention to the requirements of the process to be supported and to the users. This is a considerable drawback for the validation of a system against the requirements of the business process. In addition, this approach becomes very problematic if the environment changes or the design should be reused with different requirements. Another complication is that in the construction of embedded systems often many disciplines are involved that each use their own methods and tools. This leads to additional design faults caused by miscommunication and translation problems. What is neede are uniform methods that support the construction of embedded systems from the modelling of the supported process down to the implementation. Because of the possibility to formally specify abstractions at various levels of refinement, object-oriented methods might be a promising candidate. For the validation of complex embedded systems, also executable specifications play an important role because simulation is often the only language the user can


easily understand. Sectie FM, Groep Baeten Model Checking De nadruk van het onderzoek in het verslagjaar heeft gelegen op het gebied van automatische verificatie methoden; met name de 'model cheking'. Resultaten zijn gepresenteerd op de PSTV conferentie dit jaar en op het Israël Symposium on the Theory of Computing and Systems. Tevens zijn resultaten als tijdschriftartikel ingediend c.q. geaccepeteerd. De op de PSTV conferentie gepresenteerde methode is in de AT&T Spin verifier geïmplementeerd. In de afgelopen jaren hebben we een raamwerk geformuleerd voor het gebruik van abstracte interpretatie technieken in model checking; e.e.a. in samenwerking met de universiteit van Oldenburg en het Technion. We hebben experimentele resultaten gerapporteerd over de automatische verificatie van de 'Production cell'; een standaard verificatie benchmark. De hierbij gebruikte verificatie tool is een symbolische model checker voor StateCharts uitgebreid met abstractie technieken. De verkregen resultaten illustreren dat m.b.v. dit soort technieken substantiële reducties in verificatie-tijd en -ruimte te verkrijgen zijn. Daarnaast hebben we in het kader van het NUFFIC project 'Model checking and abstract interpretation' ons raamwerk uitgebreid naar de abstractie van reactieve systemen met globale constraints. Hiermee is een fundametele beperking weggenomen voor de toepassing van abstractie technieken. Het SOBU project 'Automated Verification of Computer Systems' beoogt o.a. de generalisatie van partiële orde reductie technieken voor de automatische verificatie van getimede systemen en eigenschappen. De formulering van een theoretisch kader voor zulke extensies is nagenoeg voltooid. Als contrapunt tot het hierboven beschrevene wil ik niet onvermeld laten het onderzoek aan deontische logica's m.b.v. dynamische logica technieken. Process algebra In 1995 is het raamwerk van procesalgebratheorieën uitgebreid met tijd vervolmaakt, en zijn al enige toepassingen gerealiseerd. Compleetheid van theorieën en uitbreidingen met abstractie kregen veel aandacht. In een seminarium werd voor het eerst een compleet overzicht verkregen. Onderzochte toepassingen waren buffers, een leader election protocol, een circuit en de I2C-bus van Philips. In samenwerking met sectie IS onderzochten we verbanden tussen procesalgebra en noninterleaving semantiek. We rapporteerden over verbanden van procesalgebra met data flow theorie, door het toevoegen van een feedback operator aan procesalgebra. Procesalgebra beschrijft voornamelijk toestandsovergangen, en abstraheert van toestanden. Toch is het in vele gevallen mogelijk aspecten van toestanden te observeren. We rapporteren een beschrijving hiervan in procesalgebra. Een voortgaand project met RUL en CWI onderzoekt hogere orde processen en mobiliteit. In 1995 kwam een overzichtsartikel van concrete procesalgebra uit als een hoofdstuk in het Handbook of Logic in Computer Science. Hierin worden een aantal generieke resultaten bewezen in algemene SOS theorie, die vervolgens in vele afzonderlijke theorieën gebruikt kunnen worden. Op deze manier kan een modulaire opbouw van de theorie aan kracht winnen door toepassing van generieke stellingen gebaseerd op operationele regels.


Type Systems De fijnstructuur van reductie in (getypeerde) lambda calculus is onderzocht en mogelijke uitbreidingen van type systemen met temporaliteit en standaard-wiskundige constructies zijn bestudeerd. Een leidende vraag hierbij is in hoeverre op basis van type theorie een algemeen bruikbaar systeem voor bewijsverificatie en/of kennisrepresentatie te ontwerpen is. Door Laan worden de hedendaagse ontwikkelingen in de type theorie in een historisch kader geplaatst. De samenwerking met dr. F. Kamareddine (Univ. van Glasgow) is voortgezet, met name door Nederpelt, Bloo en Laan. Kamareddine heeft in augustus en september de TUE bezocht en Bloo en Laan hebben de Univ. van Glasgow bezocht. Dit onderzoek heeft zich gericht op de fijnstructuur van reductie en een analyse van Russells oorspronkelijke type theorie. Verder is door Bloo en Geuvers gewerkt aan expliciete substitutie, de eerste ook in samenwerking met K. Rose (DIKU, Kopenhagen). Geuvers heeft samengewerkt met Prof. dr. H. Barendregt, dr. G. Barthe en drs. M. Stephanova (KUN), tot 1 september middels een detachering van 2 dagen per week (ESPRIT-BRA project 'Types for Proofs and Programs'), met name op het gebied van mogelijke uitbreidingen van Pure Type Systems om deze een grotere praktische flexibiliteit te geven. Dit heeft onder andere geleid tot presentaties op de ESPRIT-BRA Workshop 'Types for Proofs and Programs' (Turijn, Italië), de 'Workshop on Higher Order Algebra and Term-rewriting', HOA'95, en de 'Computer Science Logic Conference', CSL'95 (beide in Paderborn, Duitsland). Borghuis en Nederpelt hebben in het kader van het Denk project samengewerkt met IPO en KUB. De eerste heeft in het kader van zijn project 'temporaliteit in type theorie' gekeken naar Priorean tense logics, geïnterpreteerd in modal pure type systems. Sectie FM, Groep Feijs Het onderzoek naar de formele grondslagen van Interworkings dat Mauw en Reniers in opdracht van Philips uitvoeren heeft geresulteerd in een verfijning van de semantiek van Interworkings. Het werk aan Message Sequence Charts (MSC) binnen de International Telecommunication Union (ITU) heeft diverse resultaten opgeleverd. Ten eerste is de door Mauw en Reniers voorgestelde semantiek door de ITU geaccepteerd als onderdeel van standaard Z.120. Het werk aan de statische semantiek van MSCs heeft geleid tot een voorstel dat naar verwachting medio 1996 door de ITU zal worden geaccepteerd. Enkele voorstudies zijn van grote invloed geweest op de uitbreiding van de standaard (MSC'96) welke ook in 1996 ter goedkeuring voorgedragen zal worden. Ter validering van de door Mauw en Reniers ontwikkelde theorie is geëxperimenteerd met het (semi-)automatisch vervaardigen van prototype implementaties van MSC tools. Hierbij is gebruik gemaakt van de ASF+SDF Meta omgeving. D'Argenio en Mauw hebben het onderzoek naar de "delayed choice" operator afgerond. Ook de bijdrage aan het phi-SDL project van Middelburg (KPN) en Bergstra (UvA/RUU) is afgerond. De verdere ontwikkeling van de PSF-Toolkit heeft geresulteerd in een aantal uitbreidingen en verbeteringen. Teneinde de toekomstige ontwikkelingen van de PSF-Toolkit beter op de gebruikers te kunnen afstemmen is een symposium georganiseerd waarbij zowel de industrie als de academische wereld vertegenwoordigd waren. 3. Samenwerkingen met andere instellingen en industrie Instellingen IPO Katholieke Universiteit Nijmegen, Universiteit van Twente, Rijksuniversiteit Utrecht, Universiteit van Amsterdam, Centrum voor Wiskunde en Informatica, Rijksuniversiteit Leiden, ITK, Letteren Katholieke Universiteit Brabant, Manchester University, Dept. of Computer Science, UK


Southbank University, Dept. of Computer Science, Londen, UK University of Glasgow, UK. New Jersey Institute of Technology, USA, University of Waterloo, Canada, University of Clausthal, Duitsland, Christian-Albrechts-Universitaet, Kiel, Duitsland, Univ. of Oldenburg, Duitsland, GMD, Duitsland, Institute of Cybernetics, Tallinn, Estland, CERN, Zwitserland, INRIA, Frankrijk, Technion, Israel, Romanian Academy, BRICS, Aarhus, Denemarken, Industrie Philips Nat.Lab., Philips Interactive Media Systems, Shell Research, Amsterdam, Hollands Signaal, Bank MeesPierson, CAP Volmac, KPN, International Telecommunication Union (ITU), AT&T-GIS, AT&T Bell labs, Sun Microsystems, SUNY Stony Brook, USA, IBM Yorktown Heights, NY, Voornemens op korte termijn In april 1996 (15 - 16) organisatie van de IPA Terugkomdagen in Veldhoven, met als thema 'Verschillende Gezichten van de Algoritmiek'. In november 1996 (25 - 29) organisatie van een internationale 'tutorial school' met als doel "education of researchers", samen met BRICS (Basic Research in Computer Science) en de Finse onderzoekschool TUCS (Turku Centre for Computer Science). Sectie PA, Groepen Rem, Hilbers Onder leiding van Philips, en in samenwerking met de Universiteit van Amsterdam (prof. Hertzberger) en de Faculteit Elektrotechniek van de TUE (prof. Stevens) zal een door Economische Zaken gesteund project op het gebied "Multi-Media Systeemarchitectuur" van start gaan. Research project op het gebied van Computer Simulaties van Chemische Processen, samen met de groep van Van Santen (Faculteit Technische Scheikunde TUE). Sectie PA, Groep Hemerik In samenwerking met dr. R.P. Nederpelt (TUE) en prof.dr. H.C.M. de Swart is een project opgezet met de titel "Een ontwikkelomgeving voor correct programmaontwerp". Dit project wordt gesubsidieerd via het SOBU (Samenwerkingsorgaan Brabantse Universiteiten). Per 1 januari 1996 is ir. M. Franssen als AIO op dit project aangesteld. Sectie TT, Groep Hammer Requirements Engineering (Dieter Hammer) zie onder 'Bereikte resultaten per onderzoeksgroep', Sectie TT. Specificatie en verificatie van gedistribueerde, hiërarchische, algoritmen voor real-time en fout-


tolerante toepassingen (Jozef Hooman). Dit zal vooral in samenwerking met P. van der Stok geschieden. In '96 zal dit werk versterkt worden door de komst van een aio die op dit gebied zal gaan werken. Tools onderzoek (Onno van Roosmalen) In het kader van een nieuw gestart initiatief dat heeft vorm gekregen in een "Software Technology Expertise Center" van de Vakgroep Informatica, zijn verschillende studies naar software ontwikkel tools uitgevoerd. Het doel van dit soort onderzoeken is: 1. Een goed inzicht te krijgen in de huidige stand van zaken met betrekking tot ontwerpmethodes en de ondersteuning daarvoor. 2. Ideeën te ontwikkelen met betrekking tot verbetering van de methodes en eventueel voorstellen te doen in de richting van een "ideale" methode. 3. Informatie te verschaffen aan derde met betrekking tot de bovenstaande onderwerpen.


SIKS, verslag 1995. Programmaleiding

:


prof.dr. K.M. van Hee, dr. P.M.E. De Bra 1203 P175 10.0

1. Beknopte inhoudelijke beschrijving. Binnen de vakgroep Informatica wordt door de sectie Informatiesystemen onderzoek verricht binnen de onderzoekschool SIKS, die inmiddels officieel is opgericht. (Alle colleges van bestuur hebben de samenwerkingsovereenkomst ondertekend.) Het SIKS onderzoek beslaat twee deelgebieden: Formele Specificaties en Databases 1.a Formele Specificaties Het onderzoek naar executeerbare specificaties is naast de verdere uitontwikkeling van het ExSpect gereedschap twee nieuwe richtingen uitgegaan. Ir. T. Basten is onder begeleiding van prof. Baeten en prof. Van Hee bezig aan een onderzoek naar de vergelijkingspunten tussen het Petri-net formalisme dat bij het specificeren in ExSpect wordt gebruikt en de Proces-Algebra's die in de sectie Formele Methoden en de onderzoekschool IPA worden bestudeerd. Aan dit onderzoek werken dr. ir. W. Van der Aalst en dr. M. Voorhoeve mee. Dr. Somers leidt het onderzoek naar mogelijkheden tot parallelle executie van ExSpect modellen. Samen met dr. O. Van Roosmalen heeft hij de ontwikkeling van software engineering tools onderzocht. Ook in 1995 is nog veel energie geïnvesteerd in de ontwikkeling van een cursus voor de Open Universiteit, waarin Modelleren en Specificeren van Informatiesystemen wordt aangeleerd met behulp van het specificatieformalisme van ExSpect, en uiteraard ook met de ExSpect software. Prof. Van Hee en dr. W. Van der Aalst hebben hun onderzoeksinspanningen op het gebied van Workflow Management systemen opgevoerd. Er is een samenwerkingsproject met het deelgebied databases opgestart, om door middel van de ExSpect en van voor World Wide Web ontwikkelde technologie een prototype Workflow systeem te ontwikkelen. 1.b Databases Het onderzoek in het kader van object-georiënteerde database modellen en vraagtalen is afgerond. De promoties van ir. J. Hidders en drs. R. Post worden in 1996 verwacht. In de toegepaste sfeer hebben prof.dr. J. Paredaens, dr. P. De Bra en ir. C. Hoskens verder onderzoek verricht naar user-interfaces voor geografische informatiesystemen, in het kader van het MAGNUM project, een SION project waaraan een post-doc werkt aan de UT, twee oio's aan de UvA en een oio (C. Hoskens) aan de TUE. In dit multi-media database project worden nieuwe technieken onderzocht voor geografische informatiesystemen. De TUE heeft in dit project het onderwerp user-interfaces op zich genomen. In het hypertext onderzoek zijn de mogelijkheden voor collaborative authoring in World Wide Web onderzocht door dr. P. De Bra, dr. A. Aerts en dr. F. Dignum. Er is een systeem ontwikkeld, DReSS, dat het mogelijk maakt een WWW server uit te breiden tot een multi-user hypertext authoring systeem. Dit systeem wordt in samenwerking met Schlumberger (te Bladel) verder uitontwikkeld.


Daarnaast is de combinatie van WWW server technologie met object-oriented databases onderzocht, teneinde de retrieval mogelijkheden in document bases van HTML of SGML documenten te verbeteren. Door ir. E. Mickley (van het IVO) is een object-geori_nteerd systeem voor opslag en retrieval van SGML documenten gerealiseerd in Gemstone, onder begeleiding van dr. P. De Bra, en aan de TUE is een opslagsysteem voor HTML documenten ontwikkeld met behulp van de object-georiénteerde database Ode (van AT&T). In 1995 is nog beperk onderzoek verricht naar de toepassingen van deontische logica, met name bij de formalisering van communicatie tussen samenwerkende systemen. Dit onderzoek zal een rol spelen bij het samenwerkingsproject dat tussen de verschillende deelonderzoeksgebieden binnen de sectie Informatiesystemen is opgestart, om een prototype workflow systeem te ontwerpen en bouwen, met behulp van WWW technologie (en het DReSS systeem) voor de documentverwerking, en ExSpect voor de aansturing van de processen. In 1995 is dr. G.J. Houben voltijds gedetacheerd geweest bij BSO Eindhoven, en heeft derhalve niet aktief aan het database en hypermedia onderzoek kunnen meewerken. 2. Samenwerkingen Binnen het Human Capital and Mobility programma van de EU wordt samengewerkt met de universiteiten van Hamburg, Paris VI, Torino, Vienna en Zaragoza, in het MATCH project. Dr. W. Van der Aalst is gedeeltelijk gedetacheerd naar de faculteit Bedrijfskunde van de TUE voor onderzoek aan het Smart Card project, een ICES project naar de effecten van de invoering van smart cards op de containerlogistiek. Binnen Tempus zijn in het CUSE project de universiteiten van Brighton, Karlsruhe, Eindhoven en Boedapest aktief. De TUE brengt kennis in op het gebied van executeerbare specificaties (ExSpect). Cap Volmac, het Frits Philips Institute for Quality Management en de TUE werken samen in het Vitaal project, waarin eveneens ExSpect wordt ingebracht voor formele specificaties. In het SION MAGNUM project werken de UTwente, UvA en TUE samen aan de multimedia database technologie (en in het bijzonder de geografische informatiesystemen). De TUE onderzoekt hierin het user-interface aspekt. Een samenwerking met Suurland Falkplan is in voorbereiding om plannen en toeristische gidsen via het Internet aan te bieden en te voorzien van een eenvoudig interface als van een geografisch informatiesysteem. Met Schlumberger wordt samengewerkt aan de mogelijkheden om World Wide Web te gebruiken voor de interne document-verspreiding. Hierbij wordt het aan de TUE ontwikkelde DReSS systeem ingezet. Een samenwerking met het CWI was in voorbereiding, waarin dr. P. De Bra voor 40% wordt gedetacheerd, om een onderzoeksteam op het gebied van World Wide Web en database technologie op te starten. (Deze samenwerking gaat in 1996 effectief van start) 3. Voornemens op korte termijn. Onder leiding van dr. P. De Bra wordt het onderzoek van de sectie Informatiesystemen meer geunificeerd, door middel van een onderzoeksproject naar de mogelijkheden om met behulp van ExSpect, WWW en databasetechnologie een prototype workflow systeem te ontwikkelen. Dit prototype zal in eerste instantie worden ingezet bij de aansturing van het onderwijs in de software engineering en de hypermedia systemen.


De onderzoeksinzet van alle vaste wetenschappelijke medewerkers van de sectie is bij dit project vereist. In nauwe samenwerking met Bakkenist en prof. Van Hee zullen nieuwe toepassingsmogelijkheden van ExSpect worden onderzocht. Workflow systemen vormen hierbij een belangrijk doel. Door samenwerking met het CWI zal het onderzoekspotentieel op het gebied van hypermedia technologie en databases worden versterkt. De combinatie van WWW met database technologie zal in die samenwerking worden onderzocht.


BIJLAGE A VOORTGANG ONDERZOEK. Lotgevallen W&I 1995 p.46

Recommend Documents