VF-programma: PARALLELLISME

Wetenschapsgebied NWO: P110

Toepassingsgebied NABS: N076, N077, N070, N10
Beknopte beschrijving van het programma
Het VF-programma Parallellisme van de vakgroep Informatica bestaat uit twee projecten:

1. Ontwerp en implementatie van parallelle programma's.

2. Specificatie, verificatie en reïficatie van parallelle systemen

Project 1 legt zich toe op het ontwerpen van parallelle programma's die bestaan uit onderling communicerende processen, en op het implementeren van deze programma's op processornetwer­ken en als VLSI-chips. Project 1 bestaat zodoende weer uit drie deelprojec­ten:

1.1 Ontwerpmethoden (afleiden van parallelle programma's uit formele specificaties)

1.2 Netwerk-implementaties (implementeren van parallelle programma's op processor­net­werken)

1.3 VSLI-implementatie (implementeren van parallelle programma's als vertragings ongevoeli­ge schakelingen)
Project 2 houdt zich bezig met de concurrency, met name de specificatie, verificatie en reïfica­tie van parallelle, gedistribueerde en embedded systemen m.b.v. formele methoden. Het project bestaat uit twee deelprojecten:

2.1 Assertionele methoden.

2.2 Algebraïsche methoden.

In beide deelprojecten staat de theorie van concurrente en tijdkritische systemen centraal.

In dit deelproject is een ontwerpmethode voor parallelle programma's ontwikkeld die is gebaseerd op input/output relaties en communicatie gedragingen. Deze methode is vastge­legd in een rapport "Lecture Notes in Parallel Programming". De methode voldoet goed voor lineaire en boom gestructureerde systemen. Thans wordt gewerkt aan uitbreidingen naar andere typen van systemen.

Omdat we de ontwerpmethode niet alleen willen toepassen op VLSI en processornetwerken, is een door Philips gesponsorde AIO (R. Clout) begonnen onderzoek te doen naar hardwa re/software architecturen voor multimediaspelers. Met Philips worden gesprekken gevoerd om dit gezamenlijke onderzoek, wat personele inzet betreft, uit te breiden. Verder is er een vrij hechte samenwerking met de faculteit Werktuigbouwkunde ontstaan op het gebied van modelleren, specificeren en simuleren van industriele systemen. De in dit deelproject ontwik­kelde notatie voor parallelle programma's is in onderlinge samenwerking omgevormd tot de taal chi, welke binnen W veel wordt gebruikt.

Operational Semantics and Generalized Weakest Preconditions.

Science of Computer Progamming 22, 1994, pp. 137-155.
Deelproject 1.2: Netwerk implementaties

Met een aantal bedrijven en instellingen wordt er samengewerkt in het gebruik van transputer systemen voor technisch wetenschappelijk rekenwerk [2]. Naast de Shell zijn dat o.a. ES­TEC/ESA in Noordwijk (computer vision ten behoeve van navigatie in de ruimte), Joanneum Research in Graz, Oostenrijk (computervision), NLR in Amsterdam (o.a. iteratieve matrixsol-

vers) en CERN in Zwitserland (toepassingen in de hoge energie fysica). Voor de uitvoering van deze projecten is (in samenwerking met Shell) de ECL (Eindhoven Communication Library) ontwikkeld. Deze bibliotheek verhoogt de portabiliteit van parallelle programma's en neemt de afhankelijkheid van transputers en transputernetwerken weg. Hij is inmiddels beproefd op vier verschillende typen processors (transputer, Power Xplorer, Power Challenge, C40).

In het verslagjaar is naast de twee transputersystemen een (snel) Power Xplorer systeem van Parsytec in gebruik genomen. Voorlopig heeft dit netwerk slechts vier processors. Er wordt naar gestreefd fondsen te verwerven om dit systeem uit te breiden. Met de faculteit Scheikun dige Technologie (Jansen, Van Santen) is er een samenwerking waarin parallelle programma's worden ontworpen voor het simuleren van katalyse reacties aan oppervlakken. In het bijzon­der worden Monte Carlo methoden bestudeerd. Beide faculteiten brengen een AIO in (bij ons: J. Segers).

Simulating the self-assembly of Gemini (Dimeric) surfactants.

Science, Vol.266, 1994, pp. 254-256.
Deelproject 1.3: VLSI implementaties

Dit deelproject is grotendeels uitgevoerd binnen het ESPRIT OMI project EXACT, waarin o.a. wordt samengewerkt met Philips (Nat. Lab.), IMEC (te Leuven) en de universiteit van Manchester. Doel van het project is de industriele toepasbaarheid te onderzoeken van vertra­gingsongevoelige schakelingen. In het verslagjaar verscheen het proefschrift van T. Verhoeff [3]. Hierin wordt een model gegeven van vertragingsongevoelige schakelingen dat gebaseerd is op het "testing paradigm". Dit heeft niet alleen de modelvorming voor dit soort systemen sterk vereenvoudigd, maar de voortgangseisen zijn nu voor het eerst ook goed meegemodel­leerd. In samenwerking met Groningen en Southbank (Londen) wordt ook het verband met handshake algebra bestudeerd [4].

De resulterende "single rail" chips blijken niet alleen zuiniger, maar ook kleiner en sneller te zijn. In de loop van 1995 zal het proefschrift van A. Peeters over dit werk verschijnen. Binnen de samenwerking met Philips wordt verder gewerkt aan energie zuinige programmeer-tchnieken (door H. van Gageldonk), aan een FPGA (field programmable gate array) back end en aan testevaluatie en  generatie (FPGA en testen door R. van de Wiel).

A. Bailey heeft in het kader van EXACT o.a. gewerkt aan de optimalisatie van control com­ponenten [6].
In het verslagjaar is onder leiding van H. Schols door vijf mensen gewerkt aan de ontwerpom geving voor vertragingsongevoelige schakelingen DEDIC. Hiervan is nu een eerste versie operationeel.

[3] T. Verhoeff:

A theory of delay-insensitive systems. Promotor: prof.dr. M. Rem. Co-promotor: dr.ir. J.T. Udding. Eindhoven, 20 mei 1994, pp. 150.
[4] Josephs, M.B.; Lucassen, P.G.; Udding, J.T.; Verhoeff, T.:

Formal Design of an Asynchronous DSP Counterflow Pipeline: A Case Study in Handshake Algebra.

Technical Report SBU-CISM-94-06, South Bank University, School of Computing, Information Systems, and Mathematics, 1994, pp. 15.

Proceedings Async94.

Asynchronous Circuits for Low-Power: A DCC error Corrector.

IEEE Design and Tests of Computers 11, (2), 1994, pp. 22-32.
[6] Optimisation of Handshake Control Circuits; EXACT Deliverable:

EXACT­/C.3/EUT/m30/D1.

samengesteld door Baily, A.M.; Josephs, M.B.; Peeters, A.M.G.; Vercauteren, S.; Ykman-Couvreur, C., 1994.
Project 2. Specificatie, verificatie en reificatie van parallelle systemen
Deelproject 2.1 Assertionele methoden

De heroriëntatie op automatische verificatie methoden heeft zich afgelopen jaar versterkt. De samenwerking met de groep van prof. Damm (Oldenburg) op het gebied van symbolische modelchecking is voortgezet en resultaten zijn gepubliceerd in de CAV94 proceedings [1]. Onderzoek naar de generalisatie van abstracte interpretatiemethoden naar reactive systemen werd gerapporteerd op PROCOMET [2]. Op het gebied van explicit state enumeratie werd in samenwerking met Bell Labs de zogenaamde partiële orde state reductie methode voor LTL gegeneraliseerd naar CTL; deze generalisatie is geïmplementeerd in de AT&T spin verifier [3]. Tevens is in samenwerking met Bell Labs een efficient satisfiability algorithme voor LTL ontwikkeld; dit algorithme wordt wellicht door AT&T gepatenteerd. Tenslotte, wordt verslag gedaan van de verificatie van een cache consistency algorithme m.b.v. een aantal verschillen­de verificatie methoden [4].

Model Checking Using Adaptive State and Data Abstraction.

Proceedings of the 6th int. Conference on Computer Aided Verification, CAV, Stanford, CA, USA, LNCS 818, Springer Verlag, 1994, pp. 455-468.
[2]. Dams, D.; Grumberg, O.; Gerth, R.:

Abstract Interpretation of Reactive Systems: abstractions preserving CTL*,CTL* and CTL.

Proceedings of the IFIP TC 2 Working Conference on Programming Concepts, Methods and Calculi, (PROCOMET), San Miniato, Italië. North-Holland, 1994, pp. 573-592.

[3]. Gerth, R.; Kuiper, R.; Peled, D.; Penczek, W.:

A Partial Order Approach to Branching Time Logic Model Checking.

Computing Science Report 94/53, EUT, Eindhoven, 1994, pp. 20.

Verifying sequential consistent memory.

Computing Science Report 94/44, EUT, Eindhoven, 1994, pp. 160.
Deelproject 2.2 Algebraïsche methoden

Het onderzoek van Baeten richt zich op procesalgebra's met tijd [1,2] en op de incorporatie van features van andere theorieen in procesalgebra, zoals feedback [3], nondeterministische keuze (BB94partial) [4], relatie met logica [2,5]. Samen met Verhoef is een overzicht afge­rond van procesalgebra's zonder abstractie, dat zal verschijnen als hoofdstuk in het Handbook of Logic in Computer Science. Verhoef onderzoekt verder algemene eigenschappen van operation theorieen en ExSpect, promovendus Vereijken onderzoekt systemen met tijd, met name hybriede systemen, i.s.m. fac. W.. Blanco rondt een proefschrift af over processen en data, met een centrale rol voor de toestandsoperator.

Van Deursen is een nieuwe post doc die procesalgebra's voor mobiele processen gaat onder­zoeken (in het kader van SION project HOOP).
Mauw verricht samen met promovendus Reniers onderzoek op het gebied van Interworkings en Message Sequence Charts. Het onderzoek naar Interworkings vindt plaats in nauwe samenwerking met Philips. In een interne Philips rapportage is van een deel van dit onderzoek verslag gedaan. Bij het onderzoek naar MSCs wordt binnen de standaardiseringscommissie van de International Telecommunication Union (ITU) gewerkt aan de semantiek van deze taal. Dit heeft geleid tot een draft recommendation en diverse publicaties[6,7,8,9,10]. In samenwerking met Baeten is onderzoek gedaan naar de compositie van MSCs [11]. Het onderzoek naar de statische semantiek is dit jaar gestart en zal naar verwachting ook tot een recommendation van de ITU leiden. Een boek over MSCs is in voorbereiding.

Daarnaast is in samenwerking met Bergstra (UvA) en Middelburg (PTT) een onderzoek aangevangen naar de semantiek van de taal SDL.

Mauw en Mulder hebben een artikel geschreven waarin een probleem met betrekking tot de beslisbaarheid van procesalgebra wordt opgelost [12]. Van het onderzoek naar leader election protocollen in samenwerking met Brunekreef (UvA), Katoen (UT) en Koymans (Philips) is verslag gedaan op de ACP94 conferentie [13].

Het werk aan de PSF Toolkit heeft geresulteerd in versie 0.9.4, bevattende een aantal uitbrei­dingen en verbeteringen van de vorige versie. Dit werk is uitgevoerd in samenwerking met Diertens (UvA), Van Wijk, Mulder en Peters.

Real time process algebra with infinitesimals.

In: Ponse, A., Verhoef, C., Vlijmen, S.F.M. van (eds.), Algebra of Communicating Processes, Proceedings ACP94, Utrecht, Workshop in Computing, Springer Verlag 1995, 1994, pp. 148-187.
[2] Baeten, J.C.M.; Bergstra, J.A.; Bol, R.N.:

A real time process logic.

In: Gabbay, D.M., Ohlbach, H.J., (eds.), Proceedings ICTL'94, Bonn, Lecture Notes

in Artificial Intelligence, LNCS 827, Springer Verlag, 1994, pp.

Process algebra with propositional signals.

Rapport LGPS 123, vakgroep Toegepaste Logica, Universiteit Utrecht, 1994.

Computing Science Report 94/49, vakgroep Informatica, EUT, Eindhoven, 1994, pp. 25.

Process algebra with partial choice.

In: Jonsson, B., Parrow, J. (eds.), Proceedings CONCUR'94, Uppsala, Lecture Notes in Computing Science 836, Springer Verlag, 1994, pp. 465-480.
[5] Baeten, J.C.M.; Bergstra, J.A.; _tef_nescu, Gh.:

Process algebra with feedback.

Rapport P9419, vakgroep Programmatuur, Universiteit van Amsterdam, 1994.

Computing Science Report 94/30, vakgroep Informatica, EUT, Eindhoven, 1994,

pp. 22.
[6] Mauw, S.; Reniers, M.A.:

An Algebraic Semantics of Basic Message Sequence Charts.

The Computer Journal, Vol. 37, no. 4, 1994, pp. 269-277.

Computing Science Report 94/17, EUT, Eindhoven, 1994, pp. 9.

ITU-TS Q9/10 Temporary Document 9008, joint rapporteurs meeting, april 1994,

pp. 9.
[7] Mauw, S.; Reniers, M.:

An Algebraic Semantics of Message Sequence Charts.

Computing Science Report 94/23, EUT, Eindhoven, 1994, pp. 43.

ITU-TS Q.9/10 Temporary Documemt 9009, joint rapporteurs meeting april 1994, pp. 43.
[8] Mauw, S; Reniers, M.:

Formalization of static requirements for Message Sequence Charts.

ITU-TS Q.9/10 Temporary Document 9010, joint rapporteurs meeting april 1994,

pp. 21.
[9] Mauw, S.; Reniers, M.:

Modifications to requirements.

ITU-TS Q.9/10 Temporary Document 9011, joint rapporteurs meeting april 1994,

pp. 2.
[10] Mauw, S.; Meulen, E.A. van der:

Generating tools for Message Sequence Charts.

ITU-TS Q.9/10 Temporary Document 60, study group 10 meeting, oktober 1994,

pp. 34.

Delayed choice: an operator for joining Message Sequence Charts.

Formal Description Techniques, VII, Participants's Proceedings, 1994, pp. 327-342.

Computing Science Report 94/35, vakgroep Informatica, EUT, Eindhoven, 1994,

pp. 15.

ITU-TS Q9/10 Temporary Document 58, Study group 10 meeting, oktober 1994,

Regularity of BPA-systems is decidable.

In: Jonsson, B; Parrow, J. (eds.), Proceedings CONCUR'94, Springer Verlag LNCS 836, 1994, pp. 34-47.

Computing Science Report 94/27, EUT, Eindhoven, 1994, pp. 14.

Algebraic specification of dynamic leader election protocols in broadcast networks.

In: Ponse, A.; Verhoef, C.; Vlijmen, S.F.M. van, (eds.), Algebra of Communicating Processes Proceedings of ACP94, Springer Verlag, 1994, pp. 338-358.
In oktober 1994 verscheen in de Springer Verlag FACIT serie (Formal Aspects of Compu­ting) het boek "Notations for Software Design" dat door Feijs samen met Jonkers en Middel­burg geschreven is.

Vanaf September 1994 is Feijs begonnen met onderzoek op het gebied van industriele forma­lismen (SDL, TTCN, IW, MSCs, COLD).

Het lange termijn doel is eraan bij te dragen dat een groter deel van de (industriele) software met behulp van formele methoden ontwikkeld wordt. In het bijzonder richt het in 1994 door Feijs begonnen werk zich op TTCN en op de omzetting van IW (interworkings) naar SDL.
Samenwerkingen

- Procesalgebra: UvA, UU

- Philips Research, PTT Research

- Hybrede systemen: fac. W (Roorda)

- diverse partners in ITU

- HOOP: RUL, CWI

- diverse partners in CONCUR 2
1.6 VF-programma: INFORMATIESYSTEMEN 2
VF-code: TUE.INF.303.90.26
Programmaleiding: prof.dr.ir. J.C. Wortmann (Bdk/BISA); prof.dr. K.M. van Hee(­WskI/I), prof.dr.ing. D.K. Hammer (WskI/I); prof.dr. J. Wessels (WskI/B&S)
Wetenschapsgebied ISN: 1203, 1207, 3304

Wetenschapsgebied NWO: P170, P160, S190

Toepassingsgebied NABS: N083, N076, N070, N10
Beknopte inhoudelijke beschrijving van het programma

1. Informatiesystemen vanuit bedrijfskundig perspectief

1.1 Ontwerpmethodologie voor informatiesystemen

1.2 Menskundige en organisatie-aspecten van de automatisering

1.3 Informatiesystemen in produktie en logistiek

1.4 Computer Integrated Manufacturing

2. Informatiesystemen vanuit informatica perspectief

2.1 Formele specificaties

2.2 Robuuste Technische Informatiesystemen

2.3 Database systemen

2.4 Computergraphics en user interface management systemen

2.5 Kennissystemen

3. Informatiesystemen vanuit besliskundig perspectief
Voortgang van het onderzoek
Algemeen
Project 1: Informatiesystemen vanuit bedrijfskundig perspectief
Zie bijdrage van de faculteit Bedrijfskunde
Project 2: Informatiesystemen vanuit informatica perspectief
Deelproject 2.1   Formele specificaties.

Dit betreft onderzoek in het kader van het ExSpect project [1,4,7]. ExSpect is een spe­cificatie formalisme gebaseerd op hierarchische gekleurde Petri netten met tijd, een functio­nele taal en een binair datamodel.

Er zijn generieke modellen ontwikkeld voor het beschrijven van workflow management systemen [3] en tevens is een bibliotheek van componenten voltooid waarmee dergelijke systemen gesimuleerd kunnen worden.

Samenwerkingen:

NS en Bakkenist Management Consultants: dienstrooster planning; DONS project.

Philips Natlab: software process modelling.

INRO TNO en TUE BDK: Smart Card project. Een ICES­project naar de effecten van de invoering van smart cards op de containerlogistiek.

Bakkenist Managament Consultants, TUD, TNO, Rabo: Workflow management systemen.

Gewerkt wordt aan het koppelen en intelligenter maken van dergelijke systemen.

Cap Volmac en Philips Institute for Quality Management: project Vitaal (projectbeheersing).

TNO TPD en TUD: parallelle executie van Petri netten.

Using Interval Timed Coloured Petri Nets to Calculate Performance Bounds.

In: Haring, G., Kotsis, G. (eds.), Proceedings of the 7th International Conference of Modelling Techniques and Tools for Computer Performance Evaluation, Vol. 794, LNCS, Springer Verlag, New York, 1994, pp. 425-444.
[2] Aalst, W.M.P. van der:

Modelling and analysis of production systems using a Petri net based approach.

In: Boucher, T.O., Jafari, M.A., Elsayed, E.A. (eds.), Proceedings of the conference on Computer Integrated Manufacturing in the Process Industries, East Brunswick, USA, 1994, pp. 179-193.
[3] Aalst, W.M.P. van der; Hee, K.M. van; Houben, G.J.:

Modelling workflow management systems with high-level Petri nets.

In: Michelis, G. de., Ellis, C., Memmi, G. (eds.) Proceedings of the second Work­shop on Computer Supported Cooperative Work, Petri nets and related formalisms, 1994, pp. 31-50.
[4] Aalst, W.M.P. van der; Hee, K.M.:

Integrated systems modelling: an object oriented approach. In: Dubois, E., Hartel, P., Saake, G. (eds.), Proceedings of the workshop on Formal methods for Information System Dynamics, Vol. 94-33, Memoranda Informatica, Universiteit van Twente, 1994, pp. 1-12.

The DONS Rail Scheduling System.

In: Case Studies Tutorial, 15th International Conference on Application and Theory of Petri Nets, 1994, pp. 1-12.
[6] Drimmelen, M.J. van; Rampersad, H.K.; Somers, L.J.:

Simulating robotic assembly cells: a general model using Coloured Petri nets.

International Confernece on Data and Knowledge Systems for Manifacturing and Engineering, 1994, pp. 368-382.

[7] Hee, K.M. van:

Information Systems Engineering: a formal approach.

Cambridge University Press, 1994, pp. 421.

Simulation of the Building Process.

1st European Conference on Product and Process Modelling in the Building Industry, Dresden, 1994.
Deelproject 2.2: Robuste Technische Informatiesystemen
Project 2.2.1 DEDOS (Dependable Distributed Operating System)

DEDOS executie omgeving.

Het onderzoek naar de basisversie van het kloksynchronisatie algoritme is afgesloten. Er is een begin gemaakt met het onderzoek naar uitbreidingen van het algoritme en naar een hierarchi sche versie van het algoritme.

Uitgebreide simulaties zijn met behulp van ExSpect gedaan om de efficientie van concurrency control algoritmen te meten afhankelijk van verschillende parameter waarden. Een veel uitgebreider onderzoek is nodig om een goed inzicht te krijgen in de prestatie beïnvloedende aspekten van deze algoritmen. Dit heeft geresulteerd in een door STW gefinancieerd project:

"Construction and performance of real time transactions" dat samen met de vakgroep Beslis­kunde en Stochastiek wordt uitgevoerd.

In het kader van het Images 2000 zijn twee eindrapporten opgesteld handelend over de basic guidelines voor de kabinetstruktuur aanbevolen voor de europese commerciele luchtvaart industrie en over de communicatie tussen de verschillende componenten van het gedistribu­eerde computer controle netwerk dat geimplementeerd wordt op de voorgestelde kabinets­truktuur.

Het deelproject foutbestendigheid is afgesloten met de promotie van H. Schepers. De daarin geformuleerde inzichten in de specificatie en het gedrag van foutentolerante systemen is van invloed geweest op de DEDOS ontwerpbeslissingen.
DEDOS ontwikkelomgeving

Wij achten het van essentieel belang dat aan een operating systeem dat de executie van gedistibueerde real time toepassingen ondersteunt, een gedegen ontwikkelstrategie en ontwik­kelmethode voor programma's ten grondslag ligt. Daarom hebben we de laatste jaren ook op dit vlak onderzoek gedaan.

Het afgelopen jaar zijn er een aantal belangrijke vorderingen gemaakt in dat onderzoek. Een belangrijk aspect van niet real time toepassingen is de machine onafhankelijkheid van pro­gramma's. Het is belangrijk voor de herbruikbaarheid van programma's ze te formuleren in programeertalen waarvan de betekenis vaststaat zonder dat aan een specifieke machine moet worden gerefereerd. Dit aspect is minstens zo belangrijk voor real time programma's, echter, de executieduraties van programma statements zijn van nature machine afhankelijk. Daarom hebben we een tijd annotatie geintroduceerd voor programma statements waaraan, machine onafhankelijk, een betekenis kan worden toegekend.
Het ontwikkeltraject wordt dan opgedeeld in twee fasen. In de eerste fase wordt een (multi) programma ontworpen en in DEAL (DEdos Application Language) inclusief de timing annotaties geprogrammeerd. In de tweede fase wordt de executables gegenereerd. In deze fase wordt ook nagegaan of voor het gekozen executieplatform een executie schedule kan worden gevonden die de timing eisen zoals die zijn vastgelegd in het programma realiseert.

Momenteel wordt het onderzoek voortgezet met de verdere ontwikkeling van een real time programmeer methodiek en een formele semantiek voor de geintroduceerde timing annotaties.

De objecten moeten dan via "near" ofwel "remote" procedure invocaties communiceren afhankelijk van de uiteindelijke objectdistributie. Een remote procedure call (RPC) imple­mentatie is ontwikkeld die de DEAL preprocessor transparant genereert op de door distributie geenste plaatsen in de applicatie.

ontwikkeld. Enerzijds is onderzocht hoe het begrip inheritance kan worden veralgemeend zodat de soms onnatuurlijke beperkingen op de toelaatbaarheid van object georienteerde schema's worden vermeden.

Anderzijds is in de toegepaste sfeer gekeken naar structuren voor ruimtelijke objecten [6,7,]. Dit onderzoek ligt in het verlengde van het in 1994 opgestarte MAGNUM project, een SION project waaraan een post doc werkt aan de UT, twee aio's aan de UvA, en een aio aan de TUE. In dit multi media database project worden nieuwe technieken onderzocht voor geogra­fische informatiesystemen. De TUE heeft in dit project het onderwerp user interfaces op zich genomen.

In het hypertext onderzoek [4] zijn experimenten uitgevoerd die de relatie opspoorden tussen de structuur van hyperdocumenten, navigatiehulpmiddelen en het browsing gedrag van de gebruiker [5]. Op basis van dit onderzoek is een optimale heuristiek opgesteld voor het zoeken naar informatie in gedistribueerde hypertexts. Deze heuristiek [3] is toegepast in het eerder ontwikkelde zoekgereedschap voor het World Wide Web, waarvan een verbeterde versie zowel stand alone als geintegreerd in Mosaic zijn beschikbaar gesteld op het Internet [1,2].

"Information Retrieval in the World Wide Web:

Making Client Based Searching Feasible",

First WWW Conference, Geneva.

(http://www.cern.ch/PapersWWW94/reinpost.ps)

Jounal on Computer Networks and ISDN Systems, nr 27, pp 183 192, Elsevier Science BV.

"Searching for Arbitrary Information in the World Wide Web:

the Fish Search for Mosaic",

Second WWW Conference, Chicago.

(http://www.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/debra/article.html)
[3] P. De Bra, G.J. Houben, Y. Kornatzky, R. Post,

"Information Retrieval in Distributed Hypertexts",

Proc. RIAO 94 Conference, pp. 481 492, New York.
[4] P. De Bra, G.J. Houben, Y. Kornatzky,

"A Formal Approach to Analyzing the Browsing Semantics of Hypertext",

Proc. CSN 94 Conference, pp. 78 89, Utrecht.
[5] P. De Bra, G.J. Houben, J. De Vocht, Y. Kornatzky,

"Retrieval of Hypertext Structures",

Proc. Stinfon 94 Conference, pp. 103 118, Tilburg.
[6] Paredaens, J.:

On the Foundations of Spatial Databases.

Dixiemes Journees de Bases de Donnees Avancees, Clermont-Ferrant, 1994,

pp. 297-302.

Towards a theory of Spatial database Queries.

Principles of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Minneapolis, 1994, pp. 267-278.
Deelproject 2.4: Computergraphics en user interface management systems
Project 2.4.1 Grafische algoritmen
In het kader van het werk aan grafische algoritmen is voortgang geboekt in de volgende richtingen:

- Implicit surface modellen:

- adaptieve triangulatie algoritmen

- CSG-operaties op voxel-based polygonalisatie

- Interpolatie constraints en topologische (structuur) -constraints

- Free-form surface modellering:

- Een systeem voor het 'painten' van gradient velden voor het aanbrengen van detaillering in dubbelgekromde oppervlakken

- Free-form deformaties op polygonmeshes in de context van interpolatie constraints en normaalvector constraints

- Topologische operaties op polygon meshes

- 'Inflatie' van polygon skeletons naar getesseleerde manifolds

- Shrink-wrapping van implicit surfaces voor arbitraire topologieen

Het werk van Eric Peeters aan de GDP is zover gevorderd dat zijn proefschrift in eerste versie gereed is. De laatste toevoegingen hieraan waren:

- Inverse kinematica

- Dynamica van starre lichamen met punt-- en lijnscharnieren

- High-performance visualisatie
Tevens is aan het WALT systeem verdere vooruitgang geboekt aan de dynamische simulatie door een verbeterde botsafhandeling, 'soft' rigidity, en point-to-curve constraints.

Ter demonstratie is de productie van enkele animaties ter hand genomen (die in MPEG-formaat aan de internationale internet-gemeenschap ter beschikking gesteld worden). Een van de animaties betreft hier de combinatie van dynamische simulatie met implicit surfaces.

- In SOBU-verband: KUB (Tilburg), IPO, secties IS, TI (Eindhoven)

- Advisering: faculteit W, TUE

- Software ondersteuning (GDP): faculteit IO, TUD

- VU Academisch Ziekenhuis (Amsterdam)

- Vakgroep Analyse (in context van Stevin Centre: dr. H. ter Morsche: gezamenlijk schrij­ven van een boek over geometrisch modelleren; prof.dr. B. Matthey: gezamen-

lijke aanvraag NWO voor hardware ondersteuning)

- Prof. B. Wyvill en prof. P. Prusinkiewicz van de universiteit van Calgary

- Stork Boxmeer: contract research betreffende kleurenquantisatie en digitale beeldbewer­king t.b.v. textielindustrie

- Roto Smeets de Boer Hilversum: in-house cursus digitale beeldbewerking

Het werk aan locale zoekalgoritmen omvat in de eerste plaats het ontwerpen van parallelle implementaties. Voor een drietal problem, te weten het handelsreizigersprobleem, het Steiner tree probleem op grafen en het job shop scheduling probleem, zijn gedistribueerde buurruim­testructuren en speciale data structuren ontworpen, waarmee implementaties van verschillen­de

locale zoekalgoritmen op de parallelle machines gerealiseerd zijn. Vooral voor het handelsrei­zigersprobleem en het Steiner tree probleem op grafen zijn met deze implementaties uitste­kende resultaten verkregen die aantonen dat de deze implementaties tot de beste ter wereld behoren, zowel naar rekentijd als naar de qualiteit van de verkregen oplossing gemeten.
Ander onderzoek op dit gebied richt zich op een probabilistische analyse van strikte verbeteringsalgoritmen voor een speciale versie van de twee-verwisselingsbuurruimte voor het handelsreizigersprobleem.

Uit een vergelijking van de analystisch verkregen resultaten met empirische resultaten blijkt dat het huidige probabilistische model de werkelijkheid goed beschrijft. Het lijkt vooralsnog niet haalbaar deze resultaten uit te breiden naar meer realistische buurruimtestructuren voor Euclidische probleeminstanties.

Het onderzoek aan constraint satisfaction technieken heeft zich toegespitst op het ontwikkelen van efficiente domeinreductiealgoritmen voor gegeneraliseerde job shop scheduling proble-

men en op het uitwerken van een aantal praktijkstudies. Een empirische analyse van de domeinreductiealgoritmen heeft uitgewezen dat met deze aanpak constraint satisfaction algoritmen kunnen worden ontworpen die resultaten vinden voor het job shop scheduling probleem die vergelijkbaar zijn met die verkregen met de best bekende benaderingsalgorit­men voor dit probleem.
Verder is aangetoond dat deze constraint satisfaction technieken ook bruikbaar zijn voor gegeneraliseerde job shop scheduling problemen. De praktijk studies zijn uitgevoerd voor een viertal beslissingssituaties, te weten tentamenroosterplanning, lesroosterplanning, productie­scheduling van ovens, en productieplanning van verpakkingslijnen. Al deze studies zijn ontleend aan bestaande bedrijfssituaties. De resultaten geven aan dat het mogelijk is met constraint satisfaction technieken redelijke oplossingen te vinden. Het is echter ook duidelijk dat er nog een aantal belangrijke problemen moeten worden opgelost. Het betreft hierbij vooral het vergroten van de efficientie van de huidige implementaties en het afleiden van de beperkingen die gebruikt worden in constraint satisfaction technieken.
Het boven omschreven werk vormt de kern van het proefschrift van Wim Nuijten [4], waarop hij in december 1994 gepromoveerd is. Voorts heeft het werk geleid tot een aantal publicaties in vaktijdschriften [5,6,7].
Neurale Netwerken

Het werk aan neurale netwerken vindt plaats in samenwerking met de groep van prof. Wes­sels van de vakgroep Besliskende en Stochastiek, en omvat een studie van de complexiteit van meerlaagsperceptrons en de toepassing van meerlaagsperceptrons op seriegroottebepa­lingsproblemen. De complexiteitsstudie is afgerond met de promotie van Patrick Zwietering [8] en heeft geleid tot een aantal publicaties in vaktijdschriften [9,10].

Het werk aan seriegroottebepalingsproblemen gebruikt resultaten uit de complexiteitsstudie en laat zien dat het mogelijk is neurale netwerken te construeren voor deze problemen die gebruik maken van voorkennis en die om kunnen gaan met onzekerheid met betrekking tot de vraag naar een product gezien in de tijd.
[1] Aarts, E.H.l., P.J.M. van Laarhoven, J.K. Lenstra, and N.L.J. Ulder,

A computational study of local search algorithms for job shop scheduling,

ORSA Journal on Computing 6(2)(1994)118  125.
[2] Aarts, E.H.L., J.K. Lenstra, and R.J.M. Vaessens

Local Search for Job Shop Scheduling,

Abstract of the Congres on Operations Research and Artificial Intelligence, Utrecht, January 1994, pp.12  20.
[3] Verhoeven, M.G.A., and E.H.L. Aarts,

A parallel Lin Kernighan algorithm for the traveling salesman problem (extended abstract), in: G.R. Joubert, D. Trystram, F.J. Peters, and D.J.Evans (eds.), Parallel Computers: Trends and Applications, Elsevier Science B.V., 1994, pp.559  562.

Time and Resource Constrained scheduling,

PhD. Thesis, Eindhoven University of Technology, 1994.
[5] Nuijten, W.P.M., and E.H.L. Aarts,

Constraint satisfaction for multicapacitated job shop scheduling,

in: A. Cohn (ed), dings of the 11th European Conference on

Artificial Intelligence, Wiley, 1994, pp. 635  639.

A computational study of constraint satisfaction for multicapacitated job shop sche­duling,

Proceedings of the Fourth International Workshop on Project Management and Scheduling, Leuven, July 1994, pp. 166  173.
[7] Nuijten, W.P.M., G.M. Kunnen, E.H.L. Aarts, and F. Dignum,

Examination time tabling: a case study for constraint satisfaction,

Proceedings ICAI'94, Workshop on Constraint Satisfaction Issues Raised by Practi­cal Applications, August 1994, pp. 11  19.
[8] Zwietering, P.J.,

The Complexity of Multi Layered Perceptrons,

PhD. Thesis, Eindhoven University of Technology, 1994.
[9] Aarts, E.H.L. P.H.P. Stehouwer, J. Wessels, and P.J. Zwietering,

Neural networks for combinatorial optimization,

Proceeedings of the 3rd IFIP WG7.6 Working Conference on Optimization Based- Computer Aided Modelling and Design, Prague, May 1994, 280  292.
[10] Zwietering, P.J., E.H.L. Aarts, and J. Wessels,

The minimal number of layers of a perceptron that sorts,

Journal of Parallel and Distributed Computing 20(1994)380  387.
Project 2: Deontische Logica
Het onderzoek in het gebied van de deontische logica dat gedaan is in 1994 valt uiteen in twee delen. Het eerste deel heeft betrekking op de ontwikkeling en uitbreiding van de logica zelf ten behoeve van de toepassing in flexibele en cooperatieve informatiesystemen en reactive schedulingsystemen. Een belangrijk aspect hierbij is de introductie van acties in de logica. Deze uitbreiding geeft vele mogelijkheden om allerlei traditionele problemen van de deonti­sche logica op te lossen. Een representatief artikel voor dit gebied is [1].

Het tweede deel van het onderzoek is het gebruik van deontische logica bij de formalisering van communicatie tussen samenwerkende systemen. Er wordt met behulp van communicatie theorie een aantal typen boodschappen onderscheiden die elk een eigen type effect hebben. De effecten blijken op een natuurlijke manier met deontische logica te kunnen worden be­schreven.

Een representatief artikel op dit gebied is [2].
[1] Dignum, F., J. J.Ch. Meyer, and R. Wieringa.

Contextual permission. a solution to the free choice paradox.

In A. Jones and M. Sergot, editors, Second International

Workshop on Deontic Logic in Computer Science, pages 107  135, Oslo, 1994.

Communication and deontic logic.

and R. Feenstra, editors, Working papers of the Int. Workshop on Information Sys­tems  Correctness and Reusability, Amsterdam, 1994, pp. 408  422,
1. Scheduling
a. TOSCA
Er is, en wordt nog, gewerkt aan artikelen met J. Korst en B. Veltman, die eerder in het kader van het onderhavige onderzoek zijn gepromoveerd. Met name is verder gewerkt aan een beschrijving van TOSCA, een scheduling tool ontwikkeld door Veltman.
b. Anticiperende en adaptieve planning met neurale netwerken
Dit onderzoek concentreert zich op het gebruik van neurale netwerken in onzekere plannings­situaties. In het bijzonder is gekeken naar de toepassing van meerlaags perceptrons in on-line lotsizing situaties. Dit heeft geleid tot een (decompositie)techniek, waarbij een meerlaags perceptron op grond van het verleden een bepaalde planningssituatie classificeert, waarna op eenvoudige wijze de bijbehorende lot size beslissing kan worden uitgerekend. [1, 2, 3]
References :

[1] Aarts, E.H.L., H.P. Stehouwer, J. Wessels and P.J. Zwietering:

1994, Neural networks for combinatorial optimization.

Memorandum COSOR 94-29, Eindhoven University of Technology. (To appear in: Proceedings 3rd Working Conference on Optimization-Based Computer-Aided Modelling and Design, Prague).

1994, Exact solution and learning of binary classification problems with simple perceptrons.

Memorandum COSOR 94-10, Eindhoven University of Techno-logy, Faculty of Mathematics and Computing Science.
[3] Stehouwer, H.P., E.H.L. Aarts and J. Wessels:

1994, On the applicability of neural networks for production planning under uncert­ainty. Memorandum COSOR 94-32, Eindhoven University of Technolgy, Faculty of Mathematics and Computing Science.

problemen in die context. Boeiende resultaten betreffen de generalisatie van kritieke pad methoden naar min cost flow formuleringen en de inzet van hierop gebaseerde insertie in local search frameworks.