VF programma: DISCRETE STRUCTUREN 3

Wetenschapsgebied NWO: P110, T 180

Toepassingsgebied NABS: N025

A. Eindige meetkunde

1. (Eindige) meetkunde en designtheorie
- In samenwerking met A. Kasikova en D. Pasechnik werd de classificatie van meervoudige uitbreidingen van de uitgebreide gegeneraliseerde hexagons uit de Suzuki reeks voltooid.

- Uitbereidingen van gegeneraliseerde achthoeken werd bestudeerd.

- Verder vooruitgang werd geboekt met betrekking tot de theorie van blocking sets in eindige Desarguesische projectieve vlakken. Resultaten samen met Simeon Ball en Tamas Sz_nyi over meervoudige blocking sets zijn echter inmiddels achterhaald door recent onderzoek (1995) samen met Tamas Sz_nyi en Leo Storme.

- In samenwerking met A.A. Bruen en D. Wehlau werden blokkerende petten onderzocht.

- Regelmatige lijnsystemen waarin elke twee lijnen een hoek φ maken met een cos φ = 0 of ± 1/3 en de connectie met even unimodulaire roosters werden onderzocht.

- De classificatie van regelmatige veelvlakken in een quaternion ruimte werd tot een artikel verwerkt.

- In samenwerking met J. van Bon en H. van Maldeghem werden hyperbolische lijnen in gegeneraliseerde veelhoeken bestudeerd.

- In samenwerking met J. van Bon werden diagram-meetkunden van het type Af.G₂ bestu­deerd.

- Inbeddingen van gegeneraliseerde veelhoeken en bijna-veelhoeken in projectieve ruimten zijn onderzocht.

- De connectie tussen cotrangulaire meetkunden en een klass van Lie algebra's geïntrodu­ceerd door Kaplanski werd onderzocht.

- Het computerspel "button madness" werd geanaliseerd en bordgrootten waarvoor het spel te winnen is ongeacht de beginpositie werden behaald onder 1000000.

- Er werd bewezen dat er geen spread van lijmen in PG(3,q) bestaat die louter tangenten aan een elliptische kwadriek bevat. Dit resultaat zal (vermoedelijk) deel gaan uitmaken van een omvangrijker artikel samen met de Australiër Nicholas Hamilton.

- Samen met Attila Sali werden alle perfecte somverzamelingen in Abelse groepen bepaald.

- De toelaatbare 2-partities van E₆, E₇ enE₈ zijn bepaald.

- Inbeddingen van F _4,1 in E _6,1 zijn onderzocht.

- Enkele universele inbeddingsdimensies zijn bepaald.

- In samenwerking met I. Kaplansky, B.D. Mckay en J.J. Seidel is en wordt gewerkt aan het probleem van de bepaling van maximale determinanten van matrices van oneven orde met nullen op de hoofddiagonaal en elders ±1.

- In samenwerking met R.M. Wilson werden p-rangen van zekere matrices behorend met symmetrische groepen onderzocht.

- In samenwerking met M. Mulder werd bewezen dat bij {0,2}-grafen het samenhangsgetal gelijk is aan de valentie.

- Zeker wortelgrafen zijn onderzocht.

- Alle (hoogstwaarschijnlijke) afstandsreguliere grafen met valentie 4 werden gevonden.

- De hoeveelheid informatie beschikbaar via de "distance regular graphs server" is sterk uitgebreid.
3. Theorie van groepen en Lie algebra's
- Geheelheids-en aritmetische vragen voor voorstellingen van eindige groepen in algebraï­sche groepen werden onderzocht.

- De baanstructuur van GL (4,k) werkend op een 16-dimensionale vectorrruimte voor k een lichaam van karakteristiek 3 is volledig bepaald. In het bijzonder is vastgesteld dat er eindig veel banen zijn.

- De Lie algebra's voortgebracht door extreme elemenenten (speciale nilpotente elementen van index 3) zijn bestudeerd. In het geval van tenminste vier voortbrengers is vastgesteld dat de dimensie van het voortbrengsel eindig is. In het geval van ten hoogste drie voort­brengers is precies bekend welke Lie algebra's optreden.

- De contouren van het interactieve boek project ACELA zijn nader gespecificeerd.

- Voor eindige-dimensionale Lie algebra's zijn algoritmen voor standaardproblemen

(als het bepalen van het oplosbare en nilpotente radicaal) onderzocht en geïmplen-

teerd.

- De eerste schetsen zijn gemaakt voor een project betreffende kanonieke bases, quantum groepen en voorstellingen van Lie algebra's.

- Preciese uitspraken worden gedaan over de kwaliteit van het decodeeralgoritme van een code, dat bestaat uit het decoderen t.a.v. alle nevenklassen van een deelcode van de code en daarna de overlevenden te vergelijken.

- Twee oplossingen worden voorgesteld om in het geval van een (d,k)-rij synchronisatie weer te herstellen.

- Een begrensde-afstand decodeeralgoritme voor de Nordstrom-Robinson code wordt beschreven met een lagere complexiteit dan tot nu toe bekend.

- Door gebruik te maken van multi-level beschrijvingen van het Lech rooster en van Golay codekunnen deze structuren met minder operaties gedecodeerd worden dan tot nu toe bekend.

- In samenwerking met Petr Lisonek werden de optimale lineaire codes van kleine lengte geklassificeerd. (Voor het q-aire geval tot dimensie 3, voor het ternaire geval tot dimensie 4 en minimum afstand 12 en in speciale gevallen bij grotere dimensie.)

- Een theoretisch bewijs werd gevonden voor de uniciteit van ternaire [69,5,45] codes.

- Een 1-1 verband werd gevonden tussen projectieve codes en twee-gewicht-codes. Een generalisatie hiervan leverde nieuwe ternaire codes op.

- Uitbereidingsstellingen voor ternaire lineaire codes zijn gevonden. Hiermee kon het niet-bestaan van codes met bepaalde parameter sets worden aangetoond (hetgeen verbeteringen op de tabel opleverde). Ook het niet-bestaan van ternaire codes met parameters [40,5,25] is aangetoond. Met een constructiemethode afgeleid van de quasicyclische zijn diverse nieuwe codes gevonden die verbeteringen opleverde voor de tabel.

- Een tabel geproduceerd voor de maximale Lee-afstand van Z₄-lineaire codes tot lengte 16.

- Stellingen over blocking sets werden uitgebreid ten behoeve van toepassigen in de code­ringtheorie.

- Het paralleliseren van het decoderen van (eerste orde) Reed-Muller codes werd onder­zocht.

- Optimale b-burst-verbeterende codes werden bestudeerd. Onderzocht werd de decodering van zulke codes, en hoe deze decodering geparalleliseerd kan worden.

- In samenwerking met N.J.A. Sloane werd (en wordt) gewerkt aan onder- en bovengrenzen voor de minimum afstand van binaire, ternaire en quaternaire lineaire codes.

- De hoeveelheid informatie beschikbaar via de "lineair code server" is sterk uitgebreid.
1A. Algebraisch-meetkundige coderingstheorie
- Samen met Tom Høholdt werd een overzichtsartikel "On the decoding of algebraic-geome­tric codes" geschreven.

- De proceedings van het congres "Arithmetic, Geometry and Coding Theory-4" werden uitgegeven.

- De Hamming-gewichten van zekere hyperelliptische codes werd onderzocht.

- Grenzen voor de lengte van blok codes met parameters [n,k,n - k] zijn bepaald.

Research is gedaan aan het coderen voor netwerken, zoals heteenrichtingskanaal met terug­koppeling, en het tweerichtingskanaal. Het doel is de effecten te begrijpen die niet alleen door ruis maar ook door andere gebruikers veroorzaakt worden, en codes te ontwerpen die efficiente transmissie van gegevens in netwerken mogelijk maken.

In het verslagjaar is programmatuur ontwikkeld om het effect van diverse strategien te simu­leren. De met behulp hiervan gevonden resultaten over de waarschijnlijkheid van decodeer­fouten en de strategien die de volle kanaalcapaciteit benutten zijn ter publicatie aangeboden aan de IEEE Transactions on Information Theory.
Voorts is onderzocht hoe, voor een algemeen kanaal, de strategieparameters gekozen moeten worden om de overdrachtssnelheid te maximaliseren, en hoe dicht de volle kanaalcapaciteit benaderd kan worden.
Een nieuwe ondergrens voor het capaciteitsgebied van het binaire vermenigvuldigkanaal werd gevonden, en nieuwe codes en strategien werden geconstrueerd voor zo'n kanaal met vertra­ging. Aangetoond werd dat terugkoppeling het capaciteitsgebied kan vergroten. Deze resulta­ten werden gerapporteerd op het Benelux Symposium on Information Theory in Louvain la Neuve en het IEEE 1994 International Symposium on Information Theory in Trondheim.
De studie van "save up" strategien werd voortgezet. Hierover werd bericht op de EIDMA Winter Meeting on Coding Theory, Information Theory and Cryptology in Veldhoven. Het ontwerp van coderingsstrategien (met behulp van de AXE software) is vrijwel voltooid.
De capaciteit van het timing jitter kanaal werd gevonden. Voorts werden met behulp van een zgn "dependence balance" grens bovengrenzen gevonden voor het capaciteitsgebied van kanalen met meervoudige toegang en terugkoppeling, en voor twee weg kanalen met enkele uitvoer.
2. Cryptografie
- Een evoluatie is gemaakt van CryptoWorks, een component van een betaaltelevisiesysteem van Philips.

- Een decompositie constructie voor onvolledige secret sharing schemas is ontwikkeld. Deze is een generalisatie van alle tot nu toe bekende decompositie constructies.

- Aangetoond is dat de dualiteits stelling voor perfecte secret sharing schemas ook voor onvolledige secret sharing schemas geldt.

- Een klasse onvoorwaardelijk veilige groepsauthenticatie schemas gebaseerd op lineaire perfecte secret schemas is geconstrueerd.

- Onderzoek is verricht naar coding gain strategieën voor het binaire symmetrische broad­cast kanaal met vertrouwelijke boodschappen en openbare feedback; bestaande ideeën

kunnen gegeneraliseerd worden.

- Een implementatie van een zero-knowledge protocol is uitgewerkt voor de Philips DX-2 smart card.

- Een onderzoek is begonnen hoe BIB-designs gebruikt kunnen worden voor broadcast encryptie.

Wetenschapsgebied: P110

Toepassingsgebied: N076, N070, N10
Beknopte inhoudelijke beschrijving van het programma
Het VF-programma Programmeren houdt zich bezig met diverse aspecten van het program­meren: ontwerpen van algoritmen en datastructuren, programmeertalen en implementatieas­pecten. Het programma is verdeeld in drie projecten:
Project 1
In het project ALPHA wordt onderzoek verricht op het gebied van lambda calculi, typetheo­rie en programmeertalen. Er wordt een algemene en unificerende theorie van getypeerde lambda calculi opgesteld. Op basis van die theorie worden programmeertalen en programma­logica's ontworpen en bijbehorende programmeermethoden ontwikkeld. Tevens wordt een systeem geimplementeerd voor de geintegreerde ontwikkeling van programma's en bewijzen.

Project 2

Dit project behelst onderzoek naar de fundamentele aspecten van programmeren. Hieronder vallen het ontwikkelen van technieken voor en het evalueren van diverse programmeerstijlen (relationeel, functioneel, logisch, sequentieel, parallel, object georiënteerd), het ontwikkelen van geschikte notaties voor specificaties en programma's, en het formuleren van heuristieken voor het ontwerpen van (correcte en efficiënte) programma's. Ook het redeneren over en het ontwerpen van ingewik­kelder datastructuren is onderwerp van onderzoek. Tenslotte vormt de ontwikkeling van een op de relationele calculus gebaseerde theorie van datatypen een belang­rijk onderzoeksthema.

De ontwikkeling van Lambda_Omega_L wordt voortgezet door Zwanenburg, waarbij de nadruk zal liggen op begrippen en constructies uit object georienteerde talen, zoals data abstractie, classes en inheritance.

Doordat veel van deze constructies in Lambda_Omega_L definieerbaar zijn, kunnen hun eigenschappen uit die van de elementaire constructies afgeleid worden. Het doel is om langs deze weg tot specificaties en bewijsregels van object georiënteerde talen te komen.
De ontwikkeling van het Lolita systeem heeft onder andere geleid tot een familie van struc­tuureditors. Hoewel eigenlijk bedoeld voor de manipulatie van programma's en bewijzen, blijken deze ook toepasbaar op heel andere terreinen. Zo is in samenwerking met het bedrijf MediaWare een project gestart, waarbij op basis van de Lolita editor generieke documentedi­tors ontwikkeld worden.

Nederpelt heeft zijn samenwerking voortgezet met mevr. F. Kamareddine (Univ.van Glas­gow) op het gebied van typensystemen, in het bijzonder op het gebied van Pi reductie. Mevr. Kamareddine heeft een werkbezoek gebracht aan de TU in de maanden juli en augustus. Dit bezoek werd gefinancierd door NWO en door BRA Esprit. Nederpelts werk aan het boek Selected Papers on Automath is afgesloten met de publicatie ervan. Ter gelegenheid daarvan heeft hij samenmet Geuvers een symposium georganiseerd: The Influence of Automath (6 oktober) met sprekers Barendregt (KUN), Huet (Inria, Paris) en Constable (Cornell, USA).

Het werk aan typensystemen is voorspoedig verlopen. Geuvers heeft o.a. een nieuw normali­satiebewijs gegeven dat korter en inzichtelijker is dan de bestaande bewijzen. Twan Laan heeft Russells typentheorie met moderne systemen in verband gebracht, Roel Bloo heeft gewerkt aan de fijnstructuur van de lambda calculus, i.h.b. de gegeneraliseerde reductie en de substitutie en Paula Severi heeft terminatie bestudeerd (samen met Femke van Raamsdonk, VU) en typeringsalgoritmen voor pure typensystemen. Tijn Borghuis heeft zijn onderzoek op het gebied van modale typensystemen afgerond met een proefschrift. Hij is in december '94 gepromoveerd. Hij zal in SOBU dienst blijven als toegevoegd onderzoeker om te werken aan temporele typensystemen.
Project 2: Implementatiemethoden
Op basis van de eerder ontwikkelde taxonomieen van algoritmen voor patroonherkenning en voor constructie en minimalisatie van eindige automaten zijn in het verslagjaar enige toolkits van algoritmen ontwikkeld. De toolkits zijn in feite C++ class libraries van in totaal ongeveer 18.000 regels code. Zowel taxonomieen als toolkits zijn via het Internet beschikbaar gesteld. Voor beide bestaat grote belangstelling.

Uit ontvangen reacties van gebruikers blijkt dat ze over de hele wereld gebruikt worden in universiteiten en bedrijven (o.a. Wordperfect, Ford, Digital en Motorola). De taxonomieen worden vooral gebruikt in het onderwijs en als naslagwerk. De toolkits worden gebruikt in onderwijs, onderzoek en bij de ontwikkeling van andere programmatuur. De toepassingen betreffen onder andere compilerconstructie, chipontwerp en patroonherkenning in DNA­moleculen.

De in het jaar 1993 geboekte vorderingen zijn voortgezet. De methode om stellingen in de tralietheorie om te zetten in constructieve stellingen in de categorietheorie is toegepast [1] op de zogenaamde "beautiful theorem" van Dijkstra and Scholten. De zo gevonden stelling generaliseert een aantal bekende stellingen; het bewijs daarvan is ook veel simpeler.

Een nieuwe manier om de relationele semantiek van recursief gedefinieerde programma's te geven is ontworpen [2]. Deze manier is niet alleen eenvoudiger dan de gangbare, maar tevens algemener. De theorie nodigt uit om een nieuwe en interessante operator op programma's te introduceren. Deze zogenaamde "fair choice" operator valt, wanneer toegepast op gegaran­deerd eindigende programma's, samen met de bekende non deterministische keuze operator. De nieuwe operator verschilt van deze laatste doordat het resultaat eindigt als dit het geval is voor een van de operanden. De fair choice operator is wel implementeerbaar, maar kan in de gangbare relationele semantieken niet goed worden behandeld. De nieuwe theorie laat echter een simpele en elegante behandeling toe.
[1] R.C. Backhouse and M. Bijsterveld, Category Theory as Coherently Constructive Lattice Theory: An Illustration, Department of Mathematics and Computing Scien­ce, Eindhoven University of Technology,Computing Science Note 94/43, p. 35, 1994.
[2] H. Doornbos, A relational model of programs without the restriction to Egli­Milner monotone constructs, IFIP Transactions: Programming concepts, methods and Calculi, p. 363 382, Editor: Olderog, North Holland 1994.
Onderzoek naar datatypes (in het bijzonder monads) en datatype transformaties is in verband gebracht met de ontwikkeling van database query languages met meerdere datatypen [3].
[3] E. Boiten, P. Hoogendijk. A database calculus based on strong monads and partial functions, gepresenteerd op MOP, 25 januari 1995.
Graafalgoritmen.

In het verlengde van het onderzoek naar graafalgoritmen, waarover in [1] en [2] is gerappor­teerd, is gekeken naar een efficiente aanpak van vraagstellingen over bepaalde contextvrije grammatica's (Knuth, [3]). Dit algemene probleem blijkt goed te passen in het formalisme van [1], en naar verwachting zal het formalisme van [2], na generalisatie, tot een zeer compacte afleiding leiden, die bruikbaar is voor een brede klasse van graafalgoritmen. Dit zal op termijn leiden tot een publikatie. Ook kan daarbij gebruik gemaakt worden van de gevonden abstracte beschrijving van het verband tussen inductie en well foundedness in termen van verzamelingen, waarvan de resultaten zijn neergelegd in [4].

Ook dient nog vermeld te worden een onderwijsgebonden onderzoek naar een verantwoorde beschrijving van het gebruik van abstracte datatypen in een functionele taal, gericht op direkte toepasbaarheid, dat in '94 is opgestart.
[1] J.P.H.W. van den Eijnde, "Conservative fixpoint functions on a graph" in: R.S. Bird, C.C. Morgan and J.C.P. Woodcock eds., "Mathematics of Program Construction, 2nd International Conference, June/July 1992", vol. 669 LNCS, pag. 80 100, Springer Verlag, 1993.
[2] Roland C. Backhouse, J.P.H.W. van den Eijnde, A.J.M. van Gasteren, "Calculating path algorithms", Science of Computer Programming 22 (1994), pag. 3 19.
[3] D.E. Knuth, "A generalization of Dijkstra's algorithm", Information Processing Letters 6 (1977), pag. 1 5.

[4] J.P.H.W. van den Eijnde, "Calculating with induction using sets", intern rapport TUE, 24 pagina's, augustus 1994.

Het onderzoek naar het gestructureerd afleiden van datastructuren en bijbehorende program ma's is voortgezet. Er zijn diverse toepassingen van "leaf trees" ontwikkeld. Een algemene verhandeling over leaf trees is gegeven in [2]. Het onderzoek van Kloks op het gebied van graafalgoritmen heeft tot diverse publicaties geleid, waaronder [3,4,5,6]. Hierbij worden klassen grafen onderzocht, waaronder de zogenaamde grafen met begrensde boombreedte, met algoritmen die voor in het algemeen NP moeilijke problemen toch polynomiale oplossing en toelaten. Verder heeft Bijlsma een afleiding van een unificatiealgoritme geconstrueerd die aanzienlijk netter en systematischer is dan in de literatuur op dit gebied gebruikelijk is [1].

intern rapport AB51a, T.U. Eindhoven, 1994, 15 pp.

E. R. Olderog (editor), Programming Concepts, Methods and Calculi,

Elsevier Science (North Holland), 1994, pp.3 17.
[3] J.S. Deogun, T. Kloks, D. Kratsch, H. Mueller, On vertex ranking for permutation and other graphs, in:

P. Enjalbert et al. (editors), Proc. 11th Ann. Symp. on Theoretical Aspects of Com­puter Science (STACS '94), LNCS 775, Springer Verlag, 1994, pp. 747 758.

P. Enjalbert et al. (editors), Proc. 11th Ann. Symp. on Theoretical Aspects of Com­puter Science (STACS '94), LNCS 775, Springer Verlag, 1994, pp. 759 785.

Proc. of the Intern. Workshop on Graph Theoretic Concepts in Computer Science WG'94.

Proc. of the Intern. Workshop on Graph Theoretic Concepts in Computer Science WG'94.

Op het deelgebied functioneel programmeren is de behandeling van de wiskundige fundering van het functioneel programmeren afgerond [2].

Er is voorbereidend werk verricht voor het schrijven van een leerboek over functioneel programmeren, waarvan voltooiing in 1995 wordt verwacht; voorstudies hiervoor zijn bij­voorbeeld [3,4,5]. Verder is onderzoek gedaan aan technieken voor functionele­programmainversie, met een toepassing op de constructie van expressieparsers; een publicatie hierover is in voorbereiding. Samen met een afstudeerder is verkennend onderzoek uitgevoerd naar object georienteerd programmeren [6].

Het onderzoek van Bijlsma heeft geleid tot een classificatie van alle (zogenaamde) junctive predicate transformers [1]. Samen met Nederpelt werkt hij verder aan het voor logici toe­gankelijk maken van de predicatenrekening van Dijkstra en Scholten; dit project loopt nog.

Het onderzoek van Feijen, de ontwikkeling van een ontwerpdiscipline voor parallelle pro­gramma's, gebaseerd op de theorie van Owicki Gries, vertoont goede voortgang. Er is samen met twee afstudeerders aan dit project gewerkt, waarbij met name het werk van van der Sommen vermeldenswaard is [7]. De resultaten van dit project worden in de komende twee jaar gepubliceerd in de vorm van een boek.
[1] A. Bijlsma, C.S. Scholten. Point free substitution.

Computing Science Note 94/38, T.U. Eindhoven, 1994, 10 pp.

(ter publicatie aangeboden aan Science of Computer Programming.)
[2] R.R. Hoogerwoord. On the foundations of functional programming: a programmer's point of view.

Computing Science Note 94/26, T.U. Eindhoven, 1994, 54 pp.

intern rapport rh202, T.U. Eindhoven, 1994, 8 pp.

intern rapport rh217, T.U. Eindhoven, 1994, 12 pp.

intern rapport rh208, T.U. Eindhoven, 1994, 7 pp.

intern rapport rh213, T.U. Eindhoven, 1994, 8 pp.

afstudeerverslag, T.U. Eindhoven, 1994, 82 pp.