Curriculum Vitae J.M. Robson

Fonction: Professeur Etablissement actuel: Université Bordeaux I, depuis 1 janvier 1995 Adresse: 22, Domaine de Rivasseau, 33370 Pompignac. Date et lieu de naissance: 24 July 1946, Horsforth, U.K. Diplômes: 1967 B.A. Honours 1 (Mathématiques), Oxford 1968 Diploma in Advanced Mathematics, Oxford 1975 M.A., Oxford 1975 M.Sc., Oxford Titre de dissertation : Structure Type Definitions in Programming Lan-

guages 1982 Ph.D., Australian National University Titre de thèse : Worst Case Fragmentation of Dynamic Storage Allocation

Strategies 1995 B.A. (Langues étrangères), Australian National University.

Bourses: Postmastership (scholarship), Merton College, Oxford. Senior Scholarship, Wolfson College, Oxford. Sujets principaux de recherches: Complexité de calcul, analyse d’algorithmes,

algorithmique parallèle, automates, langages formels.

Postes antérieurs 1971 : Lecturer, Department of Computer Studies, Lancaster University. 1977 : Lecturing Fellow, Department of Computer Science, ANU 1980 : Lecturer, Department of Computer Science, ANU. 1984 : Senior Lecturer, Department of Computer Science, ANU 1984 : Visiting Associate Professor, University of Waterloo SERC Research Fellow, University of Warwick 1989 : Professeur invité, Laboratoire Informatique Théorique et Program-

mation, Institut Blaise Pascal

1991 : Professeur Louis Néel, Laboratoire de l’Informatique du Parallelisme, Ecole Normale Supérieure de Lyon

1994 : Professeur associé, Université de Nice-Sophia Antipolis

Subventions de recherches

1993: Australian Research Council, Parallel Algorithms for NP-complete problems

1994: Centre for Information Science Research, Parallel Algorithms for NP-complete problems

1998: Responsable du projet Alliance, Combinatoire et Algorithmique, avec l’université de Liverpool

Conférencier invité à des colloques

Greek French Computer Science Meeting, Delphi, 1989. Computer Science and Logic Seminar, Dagstuhl, 1991. Journées Polyominos et Pavages, Paris XII-Val de Marne, 1991. Chilean Computer Science Conference, Santiago,1991. Average Case Analysis of Algorithms Seminar, Dagstuhl, 1995 J. M. Robson Liste de travaux (complète jusqu’au 10 mai 2000)

1. Generation of Random Permutations, Communications of the ACM, 1969, p.634.

2. An Estimate of the Store Size Necessary for Dynamic Storage Allocation, Journal of the ACM, 1971, pp.416-423.

3. An Improved Algorithm for Traversing Binary Trees Without Auxiliary Stack, Information Processing Letters, 1973, pp.12-14.

4. Bounds for Some Functions Concerning Dynamic Storage Allocation, Journal of the ACM, 1974, pp.491-499.

5. Garbage Collection with Limited Stack Size, comptes rendus de la Algol 68 Implementation Conference, University of Manitoba, 1974, Congressus Numerantium XI, pp.228-233.

6. A Simple Solution to the Interleaved Memory Bandwidth Problem, Information Processing Letters, 1975, pp.125-126.

7. A Bounded Storage Algorithm for Copying Cyclic Structures, Communications of the ACM, 1977, pp.431-433.

8. Worst Case Fragmentation of First Fit and Best Fit Storage Allocation Strategies, Computer Journal, 1977, pp.242-244.

9. The Height of Binary Search Trees, Australian Computer Journal, tome 11, No. 4, 1979, pp.151-153.

10. A New Proof of the NP Completeness of Satisfiability, Comptes rendus du 2nd Australian Computer Science Conference, 1979, pp.62-69.

11. The Emptiness of Complement Problem for Semi Extended Regular Expressions Requires c^{n} Space, Information Processing Letters, tome 9, No. 5, 1979, pp. 220-223.

12 Baer’s Weight Balanced Trees do not Have Bounded Balance, comptes rendus du 3rd Australian Computer Science Conference, Australian Computer Science Communications, tome 2, No. 1, 1980, pp.195-204.

13. N by N Chess is NP-hard, Tech. rapport TR-CS-80-08, D.C.S., A.N.U., 1980, 7 pages.

14. Storage Allocation is NP-hard, Information Processing Letters, tome 11, No. 3, 1980, pp.119-125.

15. Storage Allocation is P-space-hard, Tech. rapport, TR-CS-80-17, D.C.S., A.N.U., 1980, 25 pages.

16. Another Intractable Game on Boolean Expressions, Tech. rapport TR-CS-81-02, D.C.S., A.N.U., 1981, 16 pages.

17. Optimal Storage Allocation Decisions Require Exponential Time, comptes rendus du 4th Australian Computer Science Conference (Computer Science section of 1981 ANZAAS Conference), Australian Computer Science Communications, tome 3, no.1, 1981, pp.162 172. Aussi rapport TR-CS-81-03 Computer Science Dept. A.N.U.

18. The Asymptotic Behaviour of the Height of Binary Search Trees, Australian Computer Science communications, tome 4, No. 1, 1982, pp.88-98.

19. Worst Case Fragmentation of Dynamic Storage Allocation Algorithms, thèse Ph.D. ANU, 1981.

20. Exponential Time Decision Problems Relating to KO-like Transition Rules, TR-CS-82-02, D.C.S., A.N.U. 1982, 11 pages.

21. N by N checkers is Exptime Complete, rapport TR-CS-82-12, D.C.S., A.N.U., aussi SIAM Journal of Computing, tome 13, No. 2, 1984, pp.252-267.

22. The Complexity of GO, rapport TR-CS-82-14, D.C.S., A.N.U., aussi comptes rendus de IFIP World Computer Congress 1983, pp. 413-417.

23. Is Chess more Complex than GO? Australian Computer Science Communications, tome 5, no.1, 1983, pp.279-284.

24. Fast Probabilistic RAM simulation of Single Tape Turing Machine Computations, Information and Control, tome 63, nos 1/2, 1984, pp.67-87.

25. Combinatorial Games with Exponential Space Complete Decision Problems, en comptes rendus de Mathematical Foundations of Computer Science 1984, (Springer).

26. Algorithms for Maximum Independent Sets, Journal of Algorithms, tome 7, 1986, pp.425-440.

27. Alternation with Restrictions on Looping, Information and Control, tome 67, 1985, pp.2-11.

28. Deterministic Simulation of a Single tape Turing machine by a Random Access Machine in Sub-linear Time, en comptes rendus du Ninth Australian Computer Science Conference (1986), aussi Information and Computation, tome 99, 1992, pp 109-121.

29. Linear Size Formulas for Non-deterministic Single Tape Computations, en comptes rendus de 11th Australian Computer Science Conference (1988).

30. Separating Strings with Small Automata, Information Processing Letters, 1989, tome 30, pp.209-214.

31. Some Languages of Generalised Star-Height One, LITP, rapport 89-62, 9 pages.

32. Strong Time Bounds: Non-Computable Bounds and a Hierarchy Theorem, Theoretical Computer Science, tome 73 (1990), pp. 313-317.

33. Random Access Machines with Multi-Dimensional Memories, Information Processing Letters, 1990, tome 34, no 5, pp. 265-6.

34. An O(T log T) Reduction from RAM computations to Satisfiability, Theoretical Computer Science, tome 82 (1991), pp. 141-149.

35. RAM with compact memory: a realistic and robust model of computation, avec E. Grandjean, Les Cahiers du Laboratoire d’Informatique de l’Université de Caen, 90-8, aussi comptes rendus du 4th Workshop on Computer Science Logic, (Springer), 1990.

36. The Analysis of Multidimensional Searching in Quad-trees, avec G. Gonnet, P. Flajolet et C. Puech, comptes rendus du second ACM-SIAM Symposium on Discrete Algorithms, aussi publié comme Analytic Variations on Quadtrees, Algorithmica, tome 10 (1993), pp. 473-500.

37. A Distributed Algorithm for Generating X+Y in Order, Rapport 91-19 du Laboratoire de l’Informatique du Parallélisme, Ecole Normale Supérieure de Lyon.

38. Sur le pavage de Figures du Plan par des dominos, Rapport 91-18 du Laboratoire de l’Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, aussi comptes rendus des ‘Journées Polyominos et Pavages’ Université Paris XII-Val de Marne, 1991.

39. More languages of generalised star height 1, Theoretical Computer Science A, tome 106, (1992), pp.327-335.

40. Parallel Algorithms for NP-Complete Problems (Preliminary Report), comptes rendus du XI International Conference of the Chilean Computer Society.

41. Transitive Closure in Parallel on a Linear Network of Processors, Parallel Processing Letters, tome 2, no 2, (1992), pp.195-203, avec M. Gastaldo et M. Morvan.

42. On the Generation of Random Binary Search Trees, avec L. Devroye, SIAM J. Computing, tome 24 no 6, (1995), pp. 1141-1146.

43. Separating Words with Machines and Groups, RAIRO Informatique Théorique, vol 30, 1, (1996) pp. 81-86.

44. Tiling Figures of the Plane with two Bars, a Horizontal and a Vertical one, avec D. Beauquier, M. Nivat et E. Remila, Computational Geometry, 5, (1995), pp.1-25.

45. On Linear Programming, Graph Isomorphism and NP-Complete Problems, rapport TR-CS-93-03, D.C.S., A.N.U., 1993.

46. Fast and scalable, yet practical parallel algorithms for knapsack-like problems, avec A. Ferreira, Journal of Distributed and Parallel Computation, 39, (1996), pp. 1-13.

47. Automaticity II: Descriptional Complexity in the Unary Case, avec C. Pomerance et J. Shallit, Theoretical Computer Science, 180, (1997), pp. 181-201.

48. Strategy and Complexity of the Game of “Squares”, avec Floriaan Breuer, Bulletin of the London Mathematical Society, 30, (1998), pp. 274-282.

49. On the Concentration of the Heights of Random Binary Search Trees. ICALP 97, LNCS 1256 (Springer), pp. 441-448.

50. Efficient Simulations by Queue Machines, avec H. Petersen, ICALP 98, LNCS 1443 (Springer), pp. 884-895, version finale soumise à SIAM J Comput.

51. On Quadratic Word Equations, avec V. Diekert, STACS 99, LNCS 1563 (Springer), pp. 217-226.

52. Quadratic Word Equations, avec V. Diekert, en “Jewels are forever – Contributions on Theoretical Computer Science in Honor of Arto Salomaa”, Juhani Karhumäki, Hermann Maurer, Gheorghe Paun et Grzegorz Rozenberg, Springer, 1999, pp. 314-326,

53. Separating Words with Small Grammars, avec J. Currie, H. Petersen et J. Shallit, Journal of Automata, Languages and Combinatorics 4 (1999), pp. 101-110.

54. Graph Ambiguity and Pseudo-primality, rapport du LaBRI, RR1201/98.

55. Deterministic Radio broadcasting, avec B. Chlebus, L. Gasieniec, et A. Ostlin, à paraître, ICALP2000.

56. On Recognizing Cayley Graphs, avec L. Barrière, P. Fraigniaud, C. Gavoille et B. Mans à paraître, ESA2000.

Travaux en cours

57. Hard Tiling Problems with Simple Tiles, avec C. Moore, soumis à Discrete & Computational Geometry.

58. Improved Maximum Independent Set Algorithms: Preliminary Report, DIMACS workshop on Faster Exact Solutions for NP-complete Problems, http://dept-info.labri.u-bordeaux.fr/ robson/.

59. Ambiguity of Cubic, Bipartite and Planar Graphs.

60. Constant Bounds on the Moments of the Height of Binary Search trees, soumis à Theoretical Computer Science.

61. On Functions and Relations Induced by Colouring Rules, réponse à une question de M. Nivat.

62. Optimal Parallel Algorithms for Certain Two-Processor Scheduling Problems, avec E. Albacea.

63. Analysis of a parallel version of Quicksort.

64. Linear programming problems with integer solutions.

65. Pavage avec ensembles de barres.

66. Complexité du temps de calcul de diffusion et échange total vagabonds.

67. The Threshold for 3-Colourability, avec M. Zito et L. Gasieniec.

Encadrement

Doctorants

Eli Albacea: Complexity of Sequential and Parallel Algorithms Steve Edwards: Implementing Programming Languages through executable

intermediate language generation Said Assoufi: Arbres Binaires de Recherche

Mémoires DEA Sami Eldika: Enumération stochastique d’objets combinatoires

Mémoires (Honours): une moyenne de 1 par an de 1971 à 1994 dont un échantillon des plus récents:

Sam Taylor: A loop invariant tutor Bill Keating: Iwama’s method for SAT Robert L. Cohen: The distance between polygons Peter Fletcher: MISFit2: The generation of algorithms to find maximum

independent sets in graphs