Publications (Complete List)
Jan van Leeuwen
Department of Information and Computing Science
Utrecht University, Utrecht, the Netherlands
Version: May 2014
(Proceedings, handbooks, special issues etc are marked by ∗∗.)
1970
“Facts about stack-automata, related devices and their languages”, Abstract No. 2 (Survey), Seminar on Automata Theory and Mathematical Linguistics, Dept. of Mathematics,
University of Utrecht, Utrecht, Spring 1970.
“The general theory of translation”, Abstract No. 6 (Survey), Seminar on Automata Theory
and Mathematical Linguistics, Dept. of Mathematics, University of Utrecht, Utrecht, Spring
1970.
“Automata, transducers, recognizers”, Abstract No. 6a (Survey), Seminar on Automata
Theory and Mathematical Linguistics, Dept. of Mathematics, University of Utrecht, Utrecht,
Spring 1970.
“Short introduction to the mathematical theory of linear sequential machines”, Abstract
No. 12 (Survey), Seminar on Automata Theory and Mathematical Linguistics, Dept. of Mathematics, University of Utrecht, Utrecht, Spring 1970.
“Brackets and parentheses in the theory of context-free languages”, Abstract No. 6 (Survey), Seminar on Automata Theory and Mathematical Linguistics, Dept. of Mathematics,
University of Utrecht, Utrecht, Winter 1970.
1971
“On compositions of semi-groups”, Notices Amer. Math. Soc. 18 (1971), 405, 71 T-A56.
“Grammatica’s en Lindenmaier’s model voor cellular development”, Research Communication (ERCU-102-0), Electronisch Rekencentrum, University of Utrecht, Utrecht, Spring 1971.
“Canonical restrictions of Lindenmayer languages”, Proc. IVth Int. Congr. for Logic, Methodology and Philosophy of Science, Bucharest, Romania, 1971.
“Rule-labeled programs - a generalization of the notion of context-free grammar”, Abstract
No. 1, Seminar on Syntactical and Semantical Problems in Theoretical Computer Science,
1
Dept. of Mathematics, University of Utrecht, Utrecht, 1971.
1972
“Rule-labeled programs”(A study of a generalization of contextfree grammars and some classes of formal languages), Ph.D. Thesis, Utrecht, 1972.
“A note on uniform Lindenmayer languages”, techn. memorandum, Dept. of Computer
Science, University of California, Berkeley, 1972.
“Unary developmental systems and languages”, (with G.T. Herman, K.P. Lee, and G. Rozenberg), Technical Report, Dept. of Computer Science, State University of New York at
Buffalo, Buffalo, 1972.
1973
“Characterization of unary developmental languages”, (with G.T. Herman, K.P. Lee, and
G. Rozenberg), Discrete Mathematics 6 (1973) 235-247.
“Rascal”(A programming language for finite automata), (with Th.A. Zoethout, et al.), LOCOS 4, Dept. of Mathematics, University of Utrecht, Utrecht, 1973.
“Pre-set push-down automata and OL-grammars”, Techn. Report 10, Dept. of Computer Science, Univ. of California, Berkeley, 1973.
“On the efficient validation of execution-sequences of simple recursive and parallel programmschemata”, presented at the Symp. on Complexity of Sequential and Parallel Numerical Algorithms, Carnegie-Mellon Univ. Pittsburgh, 1973.
“F-iteration languages”, techn. memorandum, Dept. of Computer Science, University of
California, Berkeley, 1973.
“Hyper-AFLs and all preset push-down automaton languages are indexed”, techn. memorandum, Dept. of Computer Science, Univ. of California, Berkeley, 1973.
“The halting-problem for Turing assemblers”, (with R.M. Baer) Techn. Report 23, Dept.
of Computer Science, Univ. of California, Berkeley, 1973.
“Planar realizations of networks”, Buffalo 1973 (submitted to Discrete Mathematics).
“On the fixpoints of monogenic functions in free monoids”, Report, Dept of Computer Science, State University of New York, Buffalo, 1973, revised: Techn. Report, Mathematical
Centre, Amsterdam, 1975, also in: Semigroup Forum 10 (1975) 315-328.
1974
2
“An intrinsic generalization of B¨
uchi’s theorem for regular canonical systems”, Buffalo, 1973,
Abstract presented at the Computer Science Conference, Detroit, February 12-14, 1974.
“A partial solution of the reachability problem for vector-addition systems and some applications”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing,
Seattle, April 30 - May 2 (1974, 303-309.
“The tape-complexity of context-independent developmental languages”, Proceedings of the
Conference on Biologically Motivated Automata Theory, Mc.Lean, VA, June 19-21, 1974,
revised version: Journal of Computer and System Sciences 11 (1975) 203-211.
“A generalization of Parikh’s theorem in formal language theory”, Technical Report No. 71,
Buffalo, 1974, also in the Proceedings of the 2nd Colloquium on Automata, Languages and
Programming, Saarbr¨
ucken, July 29 - August 2, 1974, Springer Lecture Notes in Computer
Science 14, pp. 17-26.
“An improved bound for detecting looping configurations on deterministic pda’s”(with C.
Smith), Technical Report 67, Buffalo, 1974, Information Processing Letters 3 (1974) 22-24.
“Notes on preset pushdown automata”, Proceedings of the Conference on Developmental
Languages, Aarhus, Denmark, Springer Lecture Notes in Computer Science 15 (1974) 177188.
“Microprogrammable random access stored program machines”, (together with C. Smith),
SIGACT NEWS 6 (1974) July issue pp. 23-32.
“A decomposition theorem for hyper-algebraic extensions of language families”, (together
with D. Wood), Technical Report No. 74/6, Mc. Master University, Hamilton, Ontario,
1974, revised version: Theor. Computer Science 1 (1976) 199-214.
“An improvement of the Hadian-Sobel bound for selecting the t-th largest of n elements”(with
P.J. Eberlein and John Moore), Buffalo, 1974 (in preparation).
“Reconsidering a problem of M. Ward”, Notes on Logic and Computer Science (LOCOS)
No. 8, University of Utrecht, Utrecht, 1974, published in: 18th Anniv. Volume of the Fibonacci Quarterly, 1980.
“Symposium on Biologically Motivated Automata Theory: report”, Utrecht, 1974, SIGACT
NEWS 6 (1974) October issue, pp. 9-10.
“The membership question for ETOL languages is polynomially complete”, Notes on Logic
and Computer Science (LOCOS) No. 9, University of Utrecht, Utrecht, 1974, in: Information
Processing Letters 3 (1975) 138-143.
“Efficiently computing the product of two binary relations”, Notes in Logic and Computer Science (LOCOS) No. 10, University of Utrecht, Utrecht, 1974, in: Int. J. Computer
Mathematics 5 (1976) 193-201.
3
“A forgotten connection between tag systems and parallel rewriting”, SIGACT NEWS 6
(1974) October issue, pp. 19-20.
“Extremal properties of non-deterministic time-complexity classes”, Notes in Logic and Computer Science (LOCOS) No. 11, University of Utrecht, Utrecht, 1974, in: E. Gelenbe & D.
Potier (Ed.): International Computing Symposium 1975, North Holland/American Elsevier,
Amsterdam (1975) 61-64.
∗∗ “Introduction to the analysis of computer-algorithms”, (lecture notes in Dutch), Notes
in Logic and Computer Science (LOCOS) No. 12, University of Utrecht, Utrecht, 1974.
“Fast algorithms for non-singular matrices”, Notes in Logic and Computer Science (LOCOS)
No. 19, University of Utrecht, Utrecht, 1974.
“The complexity of set-merging with less than a linear number of FINDS”, Notes in Logic and Computer Science (LOCOS) No. 21, University of Utrecht, Utrecht, 1974.
1975
“Infinite chains of hyper-AFL’s”, (together with P.R.J. Asveld), Techn. Memorandum, Twente Technological University, 1975.
“Aspects of general complexity in hyper-algebraic families”, Notes in Logic and Computer Science No. 23, University of Utrecht, Utrecht, (1975), presented at the Conference on
Languages and Development, Noordwijkerhout, April 1-6 (1975).
“A study of complexity in hyper-algebraic families”, Techn. Report, Mathematical Centre, Amsterdam (1975), in A. Lindenmayer & G. Rozenberg (Ed.): Automata, Languages,
and Development, North Holland Publ. Comp. (1975).
“On the non-vanishing terms in a product of multivariate polynomials”, Techn. Report,
Mathematical Centre, Amsterdam, 1975.
“The halting problem for linear Turing Assemblers”, (with R.M. Baer), revised version, Techn.
Report, Mathematical Centre, Amsterdam, 1975, in: Journ. of Computer and System Sciences 13 (1976) 119-135.
“Deterministically recognizing EOL-languages in time 0(n-to-the-3.81)”, Techn. Report, Mathematical Centre, Amsterdam, 1975.
“Computing a polynomial and all its derivatives in a small number of multiplications and
no division”, presented at the Dutch Mathematical Congress, Utrecht, 1975.
“An improved bound on the number of multiplications and divisions necessary to evaluate a polynomial and its derivatives”, (with L.S. de Jong), SIGACT NEWS 7 (1975), Summer
4
issue, pp. 32-34.
“Een beschouwing over de afdeling Informatica”, (in Dutch) Internal report, Mathematical Centre, Amsterdam, 1975.
“Some elementary proofs of lower-bounds in complexity”, (with P. van Emde Boas), Techn.
Report, Mathematical Centre, Amsterdam, 1975, revised version in: J. Lin. Algebra and
Appl. 19 (1978) 63-80
“An algebraic theory of formal languages”, contributed paper, Vth Int. Congress for Logic, Methodology, and Philosophy of Science, London, Ontario (1975).
1976
“The complexity of vector-products”(with D. Dobkin), Information Processing Letters 4
(1976) 149-154.
“On finding lowest common ancestors in less than logarithmic average time”, presented at
the symposium on Recent Results and New Directions in Algorithms and Complexity Theory,
Carnegie-Mellon University April 7-9, 1976.
“One way machines using a checking stack”, Techn. Report 108, Dept. of Computer Science, State University of New York, Buffalo (1976).
“Recursively enumerable languages and van Wijngaarden grammars”, Techn. Rep. 112,
SUNY at Buffalo (1976), Indagationes Mathematicae 80 (1977) 29-39.
“Lectures on the complexity of data-organization (recent directions)”, chapter 2 in J.W.
de Bakker (Ed.): 2nd Advanced Course on Foundations of Computer Science, MC Tract 81
(1976) 37-147, Mathematical Centre, Amsterdam.
“On the construction of Huffman-trees”, in S. Michaelson, R. Milner (Eds.): Automata,
Languages and Programming (Proceedings of the 3rd Colloquium, Edinburgh, July 20-23,
1976), Edinburgh University Press (1976) 382-410.
“Variations of a new machine-model”, Conference-record 17th Annual IEEE Symp. on Foundations of Computer Science, Houston, Texas (Oct. 25-27, 1976), pp. .. - ...
“Effective constructions in well-partially-ordered free monoids”, Techn. Rep. 203, The Pennsylvania State University (1976), in: Discrete Math. 21 (1978) 237-252.
“A regularity condition for parallel rewriting systems”, SIGACT NEWS 8 (1976) 24-27 (also
SIGACT NEWS 9 (1977) 9).
“What makes some program-optimization problems hard”, Techn. Rep. 206, The Pennsylvania State University (1976).
5
“Testing for a Grundy-numbering is NP-complete”, Techn. Rep. 207, The Pennsylvania
State University (1976).
“A generalization of star chains”, Techn. Rep. 209, The Pennsylvania State University (1976).
“An extension of Hansen’s theorem for star chains”, Techn. Rep. 211, The Pennsylvania
State University (1976), J. Reine u. Angew. Math. 295 (1977) 202-207.
“Evaluating a polynomial and its reverse”, memorandum, The Pennsylvania State University
(1976), SIGACT NEWS, Spring 1978.
1977
“Inequivalence of program segments and NP-completeness”, Techn. Rep. 217, The Pennsylvania State University (1977).
“On the analysis of some halving procedures for binomial grouptesting”(with C.G. Pfeifer
and Peter Enis), Techn. Rep.. 77-5, University of Maryland B.C. (1977) (submitted to Biometrika).
“On the complexity of decision trees, the quasi-optimizer, and the power of heuristic rules”(with N.V. Findler), Techn. Rep., SUNY at Buffalo (1977), Inf. and Contr. 40 (1979)
1-19.
“Deciding associativity for partial multiplication tables of order 3”(with P.W. Bunting and D.
Tamari), Techn. Rep. 219, The Pennsylvania State University (1977), Math. of Computation
32 (1978) 593-605.
“Stack automata and classes of nonnested macro languages”(with J. Engelfriet and E. Meineche Schmidt), Techn. Rep. 221, The Pennsylvania State University (1977), revised as Techn.
Rep. RUU-CS-77-2, University of Utrecht (1977), also JACM 27 (1980) 96-117.
“Report on the 4th International Colloquium on Automata, Languages, and Programming”,
EATCS Bulletin 3, 1977, pp. 10-12.
“Alternative path compression techniques”(with Th. van der Weide), Techn. Rep. RUUCS-77-3, University of Utrecht (1977) (presented at Oberwolfach).
∗∗ “Introduction to database systems”(210 p., in Dutch), Techn. Rep. RUU-CS-77-4, University of Utrecht (1977).
1978
“A useful lemma for contextfree programmed grammars”, Techn. Rep. RUU-CS-78-1, Uni-
6
versity of Utrecht (1977), Acta Informatica 11 (1979) 373-386.
“Compromising statistical databases with a few known elements”, Techn. Rep. RUU-CS78-2, University of Utrecht (1978), Inf. Proc. Letters 8 (1979) 149-153.
“Linear time generation of a new fixed length data-compression code”, Techn. Rep. RUUCS-78-3, University of Utrecht (1978).
“File-optimalization through migration of records”(in Dutch), in J.C. van Vliet (ed.), Colloquium Capita Datastructuren, MC Syllabus 37, Mathematical Centre, Amsterdam (1978),
pp. 187-206.
“Move rules and trade-offs in the pebble game”(with P. van Emde Boas), Techn. Rep. RUUCS-78-4, University of Utrecht (1978), Proc. 4th GI Conference on Theoretical Computer
Science, Springer Lect. Notes in Comput. Sci. 67 (1979) 101-112.
“The composition of fast priority queues”, Techn. Rep. RUU-CS-78-5, University of Utrecht
(1978) (presented at the GI Jahrestagung, TU Berlin, 1978), abstract in: GI-8.Jahrestagung,
Informatik-Fachberichte vol 16, Springer-Verlag, Berlin, 1978, p. 337.
1979
“On program efficiency and algebraic complexity”, Techn. Rep. RUU-CS-79-1, University of Utrecht (1979), Informatik Spektrum 3 (1980) 172-180.
∗∗ “Computers and Information Processing”(186 p, in Dutch), Techn. Rep. RUU-CS-792, University of Utrecht (1979).
“Rapid subtree identification revisited”(with M.H. Overmars), Techn. Rep. RUU-CS-79-3,
University of Utrecht (1979) (outline presented at the 15th Dutch Math. Congress, Eindhoven, 1979).
“A classroom note on computing products in finite-dimensional algebras”(with H. Alt), EATCS Bulletin 8 (june 1979) pp. 14-17.
“Report on STOC 79”, EATCS Bulletin 8 (june 1979), pp. 57-63.
“A family of similarity measures between strings”(with N.V. Findler), IEEE Transact. on
Pattern Analysis and Machine Intelligence, vol. PAM-1 (1979) 116-118.
“The complexity of complex division”(with H. Alt), Proceedings FCT 79, Wendisch-Rietz,
1979.
“The complexity of basic complex operations”(with H. Alt), Techn. Rep. RUU-CS-79-4,
University of Utrecht (1979), Computing 27 (1981) 205-215.
7
“Squaring a 2 x 2 matrix”, EATCS Bulletin 9 (oct. 1979), pp. 11-13.
“Dynamization of decomposable searching problems”(with D. Wood), Techn. Rep. RUUCS-79-5, University of Utrecht (1979), Inform. Proc. Letters 10 (1980) 51-56.
“The measure problem for rectangular ranges in d-space”(with D. Wood), Techn. Rep. RUUCS-79-6, University of Utrecht (1979), J. of Algorithms 2 (1981) 282-300.
“Maintenance of configurations in the plane”(with M.H. Overmars), Techn. Rep. RUUCS-79-9, University of Utrecht (1979).
“Two general methods for dynamizing decomposable searching problems”(with M.H. Overmars), Techn. Rep. RUU-CS-79-10, University of Utrecht (1979), Computing 26 (1981)
155-166.
1980
“Further comments on Bykat’s convex hull algorithm”(with M.H. Overmars), Inf. Proc.
Letters 10 (1980) 209-212.
“Dynamic systems of static datastructures”(with H. Maurer), Bericht 42, Inst. f. Informationsverarb., TU Graz, 1980.
∗∗ “Foundations of Computer Science III”, part 1: MC Tract 108, Part II: MC Tract 109
(edited with J.W. de Bakker), Mathem. Centre, Amsterdam 1980.
“The single chip computer”(in Dutch), contribution in P. Slaa (ed.), De Chips Revolutie,
Rep. Studium Generale, RU Utrecht, 1980, pp. 3-26.
“Some principles for dynamizing decomposable searching problems”(with M.H. Overmars),
Techn. Rep. RUU-CS-80-1, University of Utrecht (1980), Inf. Proc. Lett. 12 (1981) 49-53.
“Dynamic multi-dimensional data-structures based on quad- and k-d trees”, (with M.H. Overmars), Techn. Rep. RUU-CS-80-2, University of Utrecht (1980) (outline presented at the 16th
Dutch Math. Congress, Nijmegen, 1980), Acta Informatica 17 (1982) 267-285.
“Triangulating a star-shaped polygon”(with A.A. Schoone), Techn. Rep. RUU-CS-80-3,
University of Utrecht (1980).
“Reducing 3DM to CLIQUE and HAMILTONIAN CIRCUIT”(with M.J. Fischer), EATCS
Bulletin 11, 1980, p. 15-19.
“Multi-dimensional algorithms and datastructures: bibliography”(with H. Edelsbrunner, Graz),
EATCS Bulletin 11, 1980, p. 46-74.
“Report on STOC 80”, EATCS Bulletin 11, 1980, p. 145-152.
8
“Dynamically maintaining configurations in the plane”(with M.H. Overmars), Proc. 12th
Annual ACM Symp. Theory of Computing, Los Angeles, 1980, p. 135-145.
∗∗ “Automata, Languages and Programming: Seventh Colloquium”Springer Lecture Notes
in Computer Science, vol. 85 (edited with J.W. de Bakker), Springer-Verlag, Heidelberg, 1980.
“Notes on Maintenance of configurations in the plane”(with M.H. Overmars), Techn. Rep.
RUU-CS-80-5, University of Utrecht (1980).
“Dynamization of decomposable searching problems yielding good worst case bounds”(with
M.H. Overmars), Techn. Rep. RUU-CS-80-6, University of Utrecht (1980), also: Proc. 5th
GI Fachtagung Theor. Informatik, Springer Lecture Notes in Comput. Sci. 104 (1981) 224233.
“Computers and (in)tractable problems (in Dutch), Techn. Rep. RUU-CS-80-8, University of Utrecht (1980) (presented in the MC Colloquium Series on ”Complexity and Algorithms”1980).
“Worst case optimal insertion and deletion methods for decomposable searching problems”(with
M.H. Overmars), Techn. Rep. RUU-CS-80-10, University of Utrecht (1980), Inf. Proc. Lett.
12 (1981) 168-173.
“Untangling a traveling salesman tour in the plane”(with A.A. Schoone), Techn. Rep. RUUCS-80-11, University of Utrecht (1980), also: Proc. 7th Conf. Graph-theoretic Concepts
in Computer Science, Hanser-Verlag, 1982, p. 87-98. (Revised version to appear in Theor.
Comp. Sci.).
“Efficient recognition of rational relations”(with M. Nivat), Techn. Rep. RUU-CS-80-12.
University of Utrecht (1980), Inf. Proc. Lett. 14 (1982) 34-38 (Outline presented at the 17th
Dutch Math. Congress, Amsterdam, 1981).
1981
“Maintenance of configurations in the plane: revised version”(with M.H. Overmars), Techn.
Rep. RUU-CS-81-3, University of Utrecht (1981), J. Comp. Syst. Sci. 23 (1981) 166-204.
“Stratified balanced search trees”(with M.H. Overmars), Techn. Rep. RUU-CS-81-4, University of Utrecht (1981), Acta Informatica 18 (1983) 345-359.
“An elementary fact about unambiguity”, EATCS Bulletin 13, 1981, p. 4-6.
Supplement to “Multidimensional algorithms and data structures: a bibliography”(with H.
Edelsbrunner, Graz), EATCS Bulletin 13, 1981, p. 79-85.
“Connected components of orthogonal geometric objects”(with H. Edelsbrunner, Th. Ott9
mann and D. Wood), Techn. Rep. 81-CS-04, McMaster University (1981), also: RAIRO
Inform. Theor. 18 (1984) 171-183.
“Positions of symbols in context-free derivations”, EATCS Bulletin 15, 1981, p. 54-55.
“A basis for dataflow computing”(with A.P.W. B¨ohm), Techn. Rep. RUU-CS-81-6, University of Utrecht (1981).
“The art of dynamizing”(with M.H. Overmars), Techn. Rep. RUU-CS-81-8, University of
Utrecht (1981), also: Math. Foundations of Computer Science 1981 (Proc. 10th Symposium),
Springer Lect. Notes in Computer Science 118 (1981) 121-131.
“VLSI-layouts of perfect binary trees”(with M.H. Overmars and D. Wood) , Techn. Rep.
RUU-CS-81-13, University of Utrecht (1981), to appear.
“Organisation of operating systems for computer networks”(in Dutch) (with I.J.M. Birkhoff), Techn. Rep. RUU-CS-81-14, University of Utrecht (1981).
“Grenzen aan de programmeerbaarheid”, notes for the INW working group, unpublished,
August 1981, 6 pages.
“The bounded aspects ratio problem for VLSI-layouts of perfect binary trees”, Techn. Rep.
RUU-CS-81-16, University of Utrecht (1981).
“Graphics and computational geometry”, Techn. Rep. RUU-CS-81-18, University of Utrecht
(1981), also in Proc. AFCET Symp. on ”the Mathematics of Computer Science”, Paris, 1982,
pp. 159-165.
1982
∗∗ “Fundamental algorithms”(295 p., in Dutch), Techn. Rep. RUU-CS-82-1, University of
Utrecht (1982).
“Wire routing is NP-complete”(with M.R. Kramer), Techn. Rep. RUU-CS-82-4, University of Utrecht, 1982.
“The NP-completeness of finding minimum area layouts for VLSI circuits”(with M.R. Kramer), Techn. Rep. RUU-CS-82-6, University of Utrecht, 1982.
“The complexity of VLSI circuits for arbitrary boolean functions”(with M.R. Kramer), Techn.
Rep. RUU-CS-82-7, in: E. B¨
orger et. al. (eds.), Logic and Machines: decision problems and
complexity, Lect. Notes in Comp. Sci. 171 (1984) 397-407, Springer-Verlag.
“Distributed computing”, Techn. Rep. RUU-CS-82-8, University of Utrecht, also in: J.W,
de Bakker & J. van Leeuwen (eds.), Foundations of Computer Science IV, Part 1, MC Tract
10
158, Mathematical Centre, Amsterdam, 1983, pp. 1-34.
“Systolic computation and VLSI”, Techn. Rep. RUU-CS-82-9, University of Utrecht, also in: J.W. de Bakker & J. van Leeuwen (eds.), Foundations of Computer Science IV, Part
1, MC Tract 158, Mathematical Centre, Amsterdam, 1983, pp. 75-103.
∗∗ Colloquium Complexity and Algorithms, two volumes, MC Syllabus 48.1 & 48.2, (edited with P. Vitanyi and P. van Emde Boas), Mathematical Centre, Amsterdam, 1982.
“Computers and (in)tractable Problems”(in Dutch), in: P. Vitanyi, J. van Leeuwen & P.
van Emde Boas (eds.), Colloquium Complexity and Algorithms, MC Syll. 48.1, Mathematical Centre, Amsterdam, 1982, pp. 3-26.
“Multidimensional data structures and algorithms: a bibliography”(with H. Edelsbrunner),
Bericht F 104, Institut f. Informationsverarbeitung, Graz, 1982.
“Periodic versus arbitrary tessellations of the plane using polyominoes of a single type”(with
H.A.G. Wijshoff), Techn. Rep. RUU-CS-82-11, University of Utrecht, also in: A.B. Cremers
& H.P. Kriegel (eds.), 6th Conference on Theoretical Computer Science, Springer Lecture
Notes in Computer Science 145 (1983) 353-365.
1983
“Compositions of double diagonal and cross Latin squares”(with H.L. Bodlaender and H.A.G.
Wijshoff), Techn. Rep. RUU-CS-83-1, University of Utrecht, revised version: Nieuw Archief
v. Wiskunde 4(1984) 256-266.
“Periodic storage schemes with a minimum number of memory banks”(with H.A.G. Wijshoff), Techn. Rep. RUU-CS-83-4, University of Utrecht.
“Fundamental theorems in dataflow computing”(with A.P.W. B¨ohm) in: L. Priese (ed.),
Report on the 1st GTI-Workshop, Bericht 13/Reihe Theoretische Informatik, Universit¨at Paderborn, 1983.
“Periodic storage mappings for vector computations (with H.A.G. Wijshoff), in: Proc. Workshop ”Graph-theoretic Concepts in Computer Science”(WG’83), Osnabr¨
uck, 1983.
“g-schemes and d-ordered vectors”(with H.A.G. Wijshoff), Techn. Rep. RUU-CS-83-7, University of Utrecht (1983), IEEE Trans. Comput. C-36 (1987) 233-239.
“A linearity condition for periodic skewing schemes”(with H.A.G. Wijshoff), Techn. Rep.
RUU-CS-83-10, University of Utrecht (1983).
“Data mappings in large parallel computers”(with H.A.G. Wijshoff), Techn. Rep. RUUCS-83-11, University of Utrecht, also in: I. Kupka (ed.), GI-13. Jahrestagung, Informatik Fb
73, Springer-Verlag, 1983, pp. 8-20.
11
∗∗ “Foundations of Computer Science IV”: Distributed Systems, Part 1: MC Tract 158,
Part 2: MC Tract 159, (edited with J.W. de Bakker), Mathematical Centre, Amsterdam,
1983.
“Parallel computers and algorithms”, Techn. Rep. RUU-CS-83-13, University of Utrecht.
“The technological image of 1984”(in Dutch), Techn. Rep. RUU-CS-83-14, University of
Utrecht, 1984.
‘Routing with compact routing tables”(with R.B. Tan), Techn. Rep. RUU-CS-83-16, University of Utrecht.
∗∗ “Operating Systems”(231p. in Dutch) (with H.P. Penning), Techn. Rep. RUU-CS-83-18,
University of Utrecht.
1984
“The structure of periodic storage schemes for parallel memories”(with H.A.G. Wijshoff),
Techn. Rep. RUU-CS-84-1, University of Utrecht (1984), also: IEEE Trans. Computers
C-34 (1985) 501-505.
“The minimum bisection width of (three-dimensional) blocks”(with H.L. Bodlaender), Techn.
Rep. RUU-CS-84-2, University of Utrecht (1984), also as: ”A colorful proof of an obvious
theorem”, in: Dopo Le Parole, Album Amicorum for A.K. Lenstra, 1984, pp. 25-30.
“Universiteiten niet onverdeeld blij met miljarden-injektie, Prof. Van Leeuwen over informatikaplan”, interview, Utrechts Universiteitsblad, 3 Februari 1984, p 5.
“Systolische Berechnungen und VLSI”(with M.R. Kramer), Informatik-Spektrum 7 (1984)
154-165.
“Periodic storage schemes for parallel memories”(with H.A.G. Wijshoff), Proc. PARS Workshop Erlangen (April 1984), PARS Mitteilungen 2 (Oct 1984) 107-115.
“Worst-case analysis of set union algorithms”(with R.E. Tarjan), J. ACM 31 (1984) 245218.
∗∗ “Topics in the Theory of Computation”(selected papers from FCT ’83, edited with M.
Karpinski), Annals of Discrete Math. Vol 24, North-Holland Publ. Comp., Amsterdam, 1984.
“Simulation of large networks on smaller networks”(with H.L. Bodlaender), Techn. Rep.
RUU-CS-84-4, University of Utrecht (1984), prelim. version in Proc. NGI-SION Symposium
1984, Amsterdam, pp. 227-241, extended version in: K. Mehlhorn (ed.), STACS 85: 2nd
Annual Symposium on Theoretical Computer Science, Lect. Notes in Computer Sci. 182
(1985) 47-58, Springer-Verlag.
12
“Uniform emulations of the shuffle-exchange network”(with H.L. Bodlaender), Techn. Rep.
RUU-CS-84-5, University of Utrecht (1984), also in U. Pape (ed.), Proc. 10th Conf. Graph
theoretic concepts in Computer Sci., Trauner-Verlag, 1984, 19-28.
“Parallel memories, periodic skewing schemes, and the theory of finite Abelian groups”(with
J. Tappe and H.A.G. Wijshoff), Techn. Rep. RUU-CS-84-7, University of Utrecht (1984),
also:
“Beginselen van het Programmeren”, unpublished course notes, course given at Philips Research Laboratories, Eindhoven, Oct/Nov 1984.
“Arbitrary versus periodic storage schemes and tessellations of the plane using one type
of polyomino”(with H.A.G. Wijshoff), Inf & Control 62 (1984) 1-25.
“Array Processing Machines”(with J. Wiedermann), Techn. Rep. RUU-CS-84-13, University
of Utrecht (1984), also in: L. Budach (ed.), Fundamentals of Computation Theory - FCT ’85,
Lect. Notes in Computer Science 199 (1985) 257-268, Springer-Verlag.
1985
“Pascal: compact reference guide to the programming language”, Techn. Rep. RUU-CS85-1, unpublished, University of Utrecht (1985).
“On the complexity of finding uniform emulations”(with H.L. Bodlaender), Techn. Rep.
RUU-CS-85-4, University of Utrecht (1985).
“Fast simulation of Turing machines by random access machines”(with J. Katajainen and
M. Penttonen), Techn. Rep. RUU-CS-85-7, University of Utrecht (1985), extended version:
Report B37, University of Turku, 1985, also in: Seminaire du Labor. Langages et Systemes
Informatique 1984-1985, Toulouse, pp. 87-103; complete and revised version in: SIAM J.
Comput. 17 (1988) 77-88.
“The complexity of VLSI circuits for arbitrary Boolean functions”(revised version, with M.R.
Kramer), in: F.P. Preparata (ed.), Advances in Computing Research, Vol 2/1984 (VLSI Theory), JAI Press, 1984, pp. 115-128.
“The complexity of wire routing and finding minimum area layouts for arbitrary VLSI circuits”(revised version, with M.R. Kramer), in: F.P. Preparata (ed.), Advances in Computing
Research, Vol 2/1984 (VLSI Theory), JAI Press, 1984, pp. 129 -146.
“Authentication”(with G.M.J. Pluimakers), Techn. Rep. RUU-CS-85-9, University of Utrecht
(1985), also in: R. Paans & R.A.C. Thomas, Proceedings Conference on ”Data: management
and Control”, NGI/Section EDP-Auditing, Amsterdam, 1985, pp. 107-116.
“An alternate view of the alternating bit protocol”(with A.A. Schoone), in: H. Noltemeier (ed.), Proceedings WG ’85 - Int. Workshop on Graphtheoretic Concepts in Computer
13
Science, Trauner Verlag, Linz, 1985, pp. 347-354.
“Computer networks with compact routing tables”(with R.B. Tan), in: G. Rozenberg &
A. Salomaa (eds.), The book of L, Springer-Verlag, 1985, pp. 259-273.
“Report on FOCS 25”, EATCS Bulletin number 26, 1985, pp. 127-129.
“New upperbounds for decentralized extrema-finding in a ring of processors”(with H.L. Bodlaender), Techn. Rep. RUU-CS-85-15, University of Utrecht (1985), also in: E. Gafni &
N. Santoro (eds.), Distributed Algorithms on Graphs, Proc. 1st Int. Workshop on Distr.
Algorithms, Ottawa, 1985, Carleton University Press, Ottawa, 1985,pp. 27-40.
“Interval routing”(with R.B. Tan), Techn. Rep. RUU-CS-85-16, University of Utrecht (1985),
revised version: the Computer J. 30 (1987) 298-307.
“An improved upperbound for distributed election in bi-directional rings of processors” (with
R.B. Tan), Techn. Rep. RUU-CS-85-23, University of Utrecht (1985), revised version: Distributed Computing 2 (1987) 149-160.
“Diameter increase caused by edge deletion in directed and undirected graphs”(with A.A.
Schoone and H.L. Bodlaender), Techn. Rep. RUU-CS-85-26, University of Utrecht (1985),
to appear in J. Graph Theory.
∗∗ Special Issue, Papers Selected from International Conference on “Foundation of Computing Theory”, Inf. & Control 64 (1985) Numbers 1-3 (edited with M. Karpinski), Academic
Press, 1985.
1986
“Authentication: a concise survey”(with G.M.J. Pluimakers), Computers & Security 5 (1986)
243-250.
“Simulation of parallel algorithms on a distributed network”(with A.A. Schoone), Techn.
Rep. RUU-CS-86-1, University of Utrecht (1986), submitted for publication.
“General symmetric distributed termination detection” (with R.B. Tan), Techn. Rep. RUUCS-86-2, University of Utrecht (1986), submitted for publication.
“Distribution of records on a ring of processors”(with H.L. Bodlaender), Techn. Rep. RUUCS-86-6, University of Utrecht (1986).
“Report on FOCS 85”, EATCS Bulletin nr 28, 1986, pp. 110-112.
“Impressions from SOFSEM 85”, EATCS Bulletin nr 28, 1986, pp.112-115.
“Very thin VLSI-layouts of complete binary trees”(with R.B. Tan), Techn. Rep. RUUCS-86-7, University of Utrecht (1986).
14
“Protocols for distributed systems¨ın: A-Eskwadraat travelcommittee (ed.), Utrecht Research
Topics in Physics, Mathematics, Computer Science, Astronomy, and Geophysics, Utrecht,
1986, pp. 21-23.
“Simulation of large networks on smaller networks”(with H.L. Bodlaender), Inf. & Control 71 (1986) 143-180.
Comments on “Distributed termination detection algorithm for distributed computations”(with
G. Tel and R.B. Tan), Inf.Proc.Lett. 23 (1986) 163.
“Pragmatic aspects of computational complexity”(panel contribution), in: H.J. Kugler (ed.),
INFORMATION PROCESSING, Elsevier Science Publ., 1986, pp. 5-6.
∗∗ “Parallel Computers and Computations”(edited with J.K. Lenstra), CWI Syll. 9, Centre
for Mathematics and Computer Science, Amsterdam, 1986.
“Parallel computers and algorithms”, in: J. van Leeuwen & J.K. Lenstra (eds.), Parallel
Computers and Computations, CWI Syll. 9, Centre for Mathematics and Computer Science,
Amsterdam, 1986, pp. 1-32.
“The derivation of graph marking algorithms from distributed termination detection protocols”(with G. Tel and R.B. Tan), Techn. Rep. RUU-CS-86-11, University of Utrecht (1986),
revised version: Science of Computer Programming 10 (1988) 107-137.
∗∗ “Graph algorithms”(96 p), techn. Rep. RUU-CS-86-17, University of Utrecht (1986),
revised and extended in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science,
Elsevier Science Publ., Amsterdam, 1990, Chapter 10, pp. 525-631.
1987
“Guessing games and distributed computations in synchronous networks”(with N. Santoro,
J. Urrutia and S. Zaks), Rep. SCS-TR-96, Carleton University, also in: Th. Ottmann (ed.),
Automata, Languages and Programming, Proc 14th Int. Colloquium, Lecture Notes in Computer Science, Springer-Verlag, 267 (1987) 347- 356, revised version: (to appear).
“Interval heaps”(with D. Wood), Techn. Rep. RUU-CS-87-1, University of Utrecht (1987),
revised and extended version: Research Report CS-88-13, Data Structuring Group, University of Waterloo, revised version: The Computer Journal 36 (1993) 209-216.
“Array processing machines: an abstract model”(with J. Wiedermann), BIT 27 (1987) 25-43.
“Simulation of Turing machines by random access machines in O(T log S) time”(with J.
Katajainen and M. Penttonen), Dept of Computer Science, University of Turku, Report A44.
Comments on “A distributed algorithm for distributed termination”(with G. Tel), Inf.Proc.Lett.
15
25 (1987) 349.
“Improved diameter bounds for altered graphs”(with A.A. Schoone and H.L. Bodlaender), in:
G. Tinhofer & G. Schmitt (eds.), WG ’86 Graph-Theoretic Concepts in Computer Science,
Lecture Notes in Computer Science, Springer-Verlag, 246 (1987) 227-236.
“Diameter increase caused by edge deletion”(with A.A. Schoone and H.L. Bodlaender), J.
Graph Theory 11:3 (1987) 409427.
“Enumeration in graphs”(with G.J. Bezem), Techn. Rep. RUU-CS-87-7, University of
Utrecht (1987).
∗∗ 2nd International Workshop on Distributed Algorithms: draft papers (edited with E. Gafni, M. Raynal, N. Santoro and S. Zaks), Techn. Rep. RUU-CS-87-10, University of Utrecht
(1987).
∗∗ “Distributed Computing: 2nd International Workshop”(editor), Lecture Notes in Computer Science, vol 312, Springer-Verlag, 1988.
“A nondeterministic algorithm and its analysis”(with G. Tel), EATCS Bulletin nr.33, 1987,
pp. 100-103.
“Maintenance of transitive closures and transitive reductions of graphs”(with J.A. La Poutre),
Techn. Rep. RUU-CS-87-25, Dept of Computer Science, University of Utrecht (1987), extended abstract in: H. G¨
ottler and H.J. Schneider (eds), Graph-theoretic Concepts in Computer
Science (Proceedings WG ’87), Lecture Notes in Computer Science, Vol. 314, Springer-Verlag,
1988, pp. 106-120.
“On the client/server model: evaluation and proposals related to the client/server model”,
report for NCR - Utrecht, unpublished, December 1987, 28 pages.
1988
“On estimating the complexity of logarithmic decompositions”(with M. Bezem), Inf.Proc.Lett.
26 (1988) 321-324.
“The client/server model in distributed computing”, Techn. Rep. RUU-CS-88-9, Dept. of
Computer Science, University of Utrecht (1988), revised version in: CWI Quarterly 2 (1989)
193-218.
“Assertional verification of a majority consensus algorithm for concurrency control in multiple
copy databases”(with N.J. Drost), Techn. Rep. RUU-CS-88-13, Dept. of Computer Science,
University of Utrecht (1988), also in: F.H. Vogt (Ed.), Concurrency ’88, Lecture Notes in
Computer Science, Vol 335, Springer-Verlag, 1988, pp. 320-334.
“An optimal pointer machine algorithm for finding nearest common ancestors”(with A.K.
16
Tsakalides), Techn. Rep. RUU-CS-88-17, Dept. of Computer Science, University of Utrecht
(1988).
“Fast simulation of Turing machines by random access machines”(with J. Katajainen and
M. Penttonen), SIAM J. Comput. 17 (1988) 77-88.
“Onderzoek inzake Y-compatibele BIOS software”, report for Tulip Computers BV, unpublished, October 1988, 20 pages.
“Some observations for the pigeonhole principle”(with F.J. Brandenburg and R.B. Tan),
Techn. Rep. RUU-CS-88-39, Dept. of Computer Science, University of Utrecht (1988).
1989
“On models for propositional dynamic logic”(with P.M.W. Knijnenburg), Techn. Rep. RUUCS-89-3, Dept. of Computer Science, University of Utrecht (1989), revised version: Theor.
Comput. Sci. 91 (1991) 181-204.
∗∗ “Graph-Theoretic Concepts in Computer Science”(editor), Proceedings 14th International Workshop WG ’88, Lecture Notes in Computer Science, vol 344, Springer-Verlag, 1989.
∗∗ “Computing Science in the Netherlands”(edited with P.G.M. Apers and D. Bosman),
Proceedings CSN 89, Vol 1 and 2, SION/Centre for Mathematics and Computer Science,
Amsterdam, 1989.
“Efficient elections in chordal ring networks”(with H. Attiya, N. Santoro and S. Zaks), Algorithmica 4 (1989) 437-446.
“Audit EATCS Financial Administration”, unpublished report, commissioned by the EATCS
Council, Spring 1989.
“Onderzoek inzake compatibele BIOS software”, report for Tulip Computers BV, unpublished, May 1989, 19 pages.
“Contra-rapport inzake een door IBM (dd 12 mei 1989) verstrekt onderzoek van Tulip BIOS
software”, report for Tulip Computers BV, unpublished, May 1989, 16 pages.
“Notitie betreffende nadere opmerkingen van IBM-zijde (dd 26 mei 1989) inzake een vergelijkend onderzoek van de ERSO BIOS”, report for Tulip Computers BV, unpublished, May
1989, 2 pages.
“Structured NC”(with B. Scholten), Techn. Rep. RUU-CS-89-6, Dept. of Computer Science, University of Utrecht, Utrecht (1989), also in: F. Dehne et al. (Eds), Algorithms
and Data Structures, Proceedings WADS ’89, Lecture Notes in Computer Science, Vol 382,
Springer-Verlag, 1989, pp. 487-498.
17
“Computational complexity of norm maximalization”(with H.L. Bodlaender, P. Gritzmann,
and V. Klee), IMA Preprint # 528, Institute for Mathematics and Its Applications, University of Minnesota, Minneapolis, 1989, revised version: Algorithmica 10 (1990) 203-225.
“The one-dimensional skewing problem”(with G. Tel and H.A.G. Wijshoff), Techn. Rep.
RUU-CS-89-23, Dept. of Computer Science, University of Utrecht, Utrecht (1989).
“Correctness of the two-phase commit protocol”, Techn. Rep. RUU-CS-89-34, Dept. of
Computer Science, University of Utrecht, Utrecht (1989), also in: J.W. de Bakker, 25 jaar
Semantiek, Liber Amicorum, CWI, Amsterdam, April 1989, pp 319-327.
“Algorithms and Complexity (ALCOM): ESPRIT-Basic Research Actions Project 3075”,
EATCS Bulletin Nr 39, Oct. 1989, pp. 57-59.
∗∗ “A First Course on Formal Methods”(Part I, in Dutch), lecture notes, Dept of Computer Science, Utrecht University, Utrecht (1989/1990).
1990
∗∗ “Handbook of Theoretical Computer Science”(editor), Vol 1: Algorithms and Complexity,
Elsevier Science Publishers, Amsterdam, 1990, 996 + ix pages (co-published by MIT Press,
translated into Japanese).
∗∗ “Handbook of Theoretical Computer Science”(editor), Vol 2: Formal Models and Semantics, Elsevier Science Publishers, Amsterdam, 1990, 1273 + ix pages (co-published by
MIT Press, translated into Japanese).
“On special multiples of integers”(with G. Kant), EATCS Bulletin, Nr 41, 1990, pp. 210-211.
“Prefix routing schemes in dynamic networks”(with E.M. Bakker and R.B. Tan), Techn.
Rep. RUU-CS-90-10, Dept. of Computer Science, University of Utrecht, Utrecht (1990),
revised version in: Computer Networks and ISDN Systems 26 (1993) 403-421.
“Strong colorings of graphs”(with G. Kant), Techn. Rep. RUU-CS-90-15, Dept. of Computer
Science, University of Utrecht, Utrecht (1990).
“The file distribution problem for processor networks”(with G. Kant), Techn. Rep. RUUCS-90-16, Dept. of Computer Science, University of Utrecht, Utrecht (1990), also in: J.R.
Gilbert and R. Karlson (Eds.), Proc. 2nd Scandinavian Workshop on Algorithm Theory,
Lecture Notes in Computer Science, Vol 447, Springer-Verlag, 1990, pp. 48-59.
“Maintaining 2- and 3-connected components in graphs, Part I: 2- and 3-edge connected
components”(with J.A. La Poutr´e and M.H. Overmars), Techn. Rep. RUU-CS-90-26, Dept.
of Computer Science, University of Utrecht, Utrecht (1990), revised version: “Maintenance of
2- and 3-edge connected components of graphs I”(with J.A. La Poutr´e and M.H. Overmars),
Discr Math 114 (1993) 329-359.
18
“Perfect colorings”(with E.M. Bakker and R.B. Tan), Techn. Rep. RUU-CS-90-35, Dept.
of Computer Science, University of Utrecht, Utrecht (1990).
“Developments in Informatics Research”, unpublished paper, presented at the 10 Year Anniversary Symposium of SION, Zeist, October 30.
1991
∗∗ “Distributed Algorithms: Proceedings 4th International Workshop”(editor, with N. Santoro), Lecture Notes in Computer Science, Vol 486, Springer-Verlag, Berlin, 1991.
∗∗ “PARLE ’91 - Parallel Architectures and Languages Europe: Proceedings”(editor, with
E.H.L. Aarts and M. Rem), Vol I: Parallel Architectures and Algorithms, Lecture Notes in
Computer Science, Vol 505, Springer-Verlag, Berlin, 1991.
∗∗ “PARLE ’91 - Parallel Architectures and Languages Europe: Proceedings”(editor, with
E.H.L. Aarts and M. Rem), Vol II: Parallel Languages, Lecture Notes in Computer Science,
Vol 506, Springer-Verlag, Berlin, 1991.
∗∗ “Computing Science in the Netherlands”(editor), Proceedings 5th National Conference
(CSN ’91), Utrecht, Vol 1 and 2, SION/Centre for Mathematics and Computer Science, Amsterdam, 1991.
“Een case voor Open Systems”, in: Dokumentatie NOVI Praktijkdag “OPEN SYSTEMEN van Wens naar Realiteit”, RAI Congrescentrum, November, 1991.
“Linear interval routing”(with E.M. Bakker and R.B. Tan), Techn. Rep. RUU-CS-91-7,
Dept. of Computer Science, University of Utrecht, Utrecht (1991), also in: Algorithms Review 2 (1991) 45-61.
“Uniform d-emulations of rings, with an application to distributed virtual ring construction”(with E.M. Bakker), Techn. Rep. RUU-CS-91-21, Dept. of Computer Science, University
of Utrecht, Utrecht (1991), revised version in: Networks 23 (1993) 237-248.
“Some domination problems on trees and on general graphs”(with E.M. Bakker), Technical Report RUU-CS-91-22, Dept. of Computer Science, University of Utrecht, Utrecht (1991).
“The optimal placement of replicated items in distributed databases on tree-like networks”(with
E.M. Bakker), Techn. Rep. RUU-CS-91-23, Dept. of Computer Science, University of
Utrecht, Utrecht (1991).
“Voorwoord van de dagvoorzitter”, in A-ESkwadraat Symposium “Verstand van Verstand:
Expertsystemen en Neurale Netwerken”, symposium bundel, Utrecht, Mei 1991, p. 5.
“Deskundigenbericht inzake ARC contra Schuman Incasso” (with Th.J. Mulder and H.T.
19
Milo), rapport voor het Gerechtshof te Arnhem, unpublished, November 1991, 20 pages.
1992
“Evaluatie van enkele rapporten inzake het Uni-Living II softwarepakket ten behoeve van
de woninginrichtingsbranche”, report for the “Vereniging van Gebruikers van Uni-Living II”,
unpublished, 1992, 10 pages.
∗∗ “Information Processing 92: Proceedings IFIP 12th World Computer Congress (IFIP
92)”, Vol I: Algorithms, Software, Architecture (editor), North-Holland/Elsevier Science Publishers, Amsterdam, 1992, 718 + xxx pages.
∗∗ Special Issue, Papers selected from the PARLE ’91 Conference on “Parallel Architectures
and Languages” (guest editor, with E.H.L. Aarts and M. Rem), Future Generation Computer
Systems (FGCS), Vol 8, Nr 4, September 1992, pp 267-440.
“New developments in computer science teaching and research” (in Dutch), in: Report of
the 1st Annual Meeting of Computer Science Alumni, AVIRUS, Dept of Computer Science,
Utrecht University, 1997, pp. 8-11.
“Guest editorial”(with E.H.L. Aarts and M. Rem), Future Generation Computer Systems
8 (1992) 267-268.
∗∗ “Fundamental algorithms and data structures”(with P. Widmayer), in: E.G. Coffman
et al. (Eds.), Handbooks in Operations Research and Management Science, Vol 3: Computing, North-Holland/Elsevier Science Publishers, Amsterdam, 1992, Chapter 7, pp. 323-373.
1993
“On proofs by analogy”, in: H. Barendregt et al. (Eds.), Dirk van Dalen Festschrift, Quaestiones Infinitae, Vol V, Dept. of Philosophy, Utrecht University, 1993, pp. 79-88.
“Adjusting to the trends in informatics” (in Dutch), in: Report of the 2nd Annual Meeting of Computer Science Alumni, AVIRUS, Dept of Computer Science, Utrecht University,
1993, pp. 9-13.
“Periodic Review of Esprit Basic Research Action 7195, Project ACCLAIM: Advanced Concurrent Constraint Languages-Application, Implementation, and Methodology”, review of
September 6 in Leuven, report for ESPRIT Basic Research, unpublished.
“Periodic Review of Esprit Basic Research Action 7269, Project QMIPS: Quantitative Modeling in Parallel Systems”, review of October 25 in Brussels, report for ESPRIT Basic Research,
unpublished.
20
1994
∗∗ “Graph-Theoretic Concepts in Computer Science”(editor), Proceedings 19th International
Workshop WG ’93, Lecture Notes in Computer Science, Vol 790, Springer-Verlag, Berlin,
1994.
∗∗ “Algorithms - ESA ’94”(editor), Proceedings 2nd Annual European Symposium, Lecture
Notes in Computer Science, Vol 855, Springer-Verlag, Berlin, 1994.
∗∗ “Incremental Computation and Dynamic Algorithms” (editor, with K. Mehlhorn and Th.
Reps), Dagstuhl-Seminar-Report 88 (9418), Int. Begegnungs- und Forschungszentrum f. Informatik, Schloss Dagstuhl, 1994.
“Periodic Review of Esprit Basic Research Action 7195, Project ACCLAIM: Advanced Concurrent Constraint Languages-Application, Implementation, and Methodology”, review of
October 19 in Leuven, report for ESPRIT Basic Research, unpublished.
“Periodic Review of Esprit Basic Research Action 7269, Project QMIPS: Quantitative Modeling in Parallel Systems”, review of October 28 in Newcastle-upon-Tyne, report for ESPRIT
Long-Term Research, unpublished.
1995
“Compact routing methods: a survey”(with R.B. Tan), Techn. Report UU-CS-1995-05, Dept
of Computer Science, Utrecht University, Utrecht (1995), also in: Proc. 1st Colloquium
on Structural Information and Communication Complexity (Sirocco94), Carleton University
Press, 1994, pp. 71-93.
“Guessing games, binomial sum trees and distributed computations in synchronous networks”(with N. Santoro, J. Urrutia and S. Zaks), Techn. Report UU-CS-1995-13, Dept of
Computer Science, Utrecht University, Utrecht (1995).
“The complexity of interval routing on random graphs”(with M. Flammini and A. MarchettiSpaccamela), Techn. Report UU-CS-1995-16, Dept of Computer Science, Utrecht University,
Utrecht (1995); extended abstract in: J. Wiedermann and P. H´ajek (Eds.), Mathematical
Foundations of Computer Science 1995, 20th Int. Symposium (MFCS’95), Lecture Notes in
Computer Science Vol. 969, Springer-Verlag, Berlin, 1995, pp. 37-49.
“On interval routing schemes and treewidth” (with H.L. Bodlaender, R.B. Tan, and D.M. Thilikos), extended abstract in: M. Nagl (Ed.), Graph-Theoretic Concepts in Computer Science,
21st Int. Workshop (WG’95), Lecture Notes in Computer Science Vol. 1017, Springer-Verlag,
Berlin, 1995, pp. 181-196; revised and extended version: Techn. Report UU-CS-1996-41, Dept
of Computer Science, Utrecht University, Utrecht (1996) (to appear in Information & Computation).
∗∗ “Computer Science Today: Recent Trends and Developments” (editor), Lecture Notes
21
in Computer Science Vol. 1000, Springer-Verlag, Berlin, 1995, 643 + xiv pages.
“Final Review of Esprit Basic Research Action 7195, Project ACCLAIM: Advanced Concurrent Constraint Languages-Application, Implementation, and Methodology”, review of
October 19 in Leuven, report for ESPRIT Long-Term Research, unpublished.
“Final Review of Esprit Basic Research Action 7269, Project QMIPS: Quantitative Modeling
in Parallel Systems”, review of October 20 in Zaragoza, report for ESPRIT Long-Term Research, unpublished.
1996
∗∗ “No Future Without Informatics”(“Geen toekomst zonder informatica: Toekomstverkenning Informatica 1996-2005”, in Dutch, contributing author), Report of the Foresight
Committee for Informatics in the Netherlands (“Verkenningscommissie Informatica”), Overlegcommissie Verkenningen, Amsterdam, 1996, 69+XIV pages.
“Report on the evaluation meeting of ECVNET” (with A.J. Thunem), internal report of
the evaluation committee, Long-Term Research, DG III, EC, Brussels, 10 pages, unpublished, May 1996.
“Evaluation of the Concept of Networks of Excellence”(contributing author), Final report
of the evaluation committee, Long-Term Research, DG III, EC, Brussels, 1996.
“Evaluation of two Ph.D. School proposals - a Report for the Danish National Research
Foundation”(chief author), Report of the Evaluation Panel, Danish National Research Foundation, Copenhagen, 1996.
“Report on the LTR Strategic Planning Workshop”, Report on a Workshop held September 24, Long-Term Research, DG III, EC, Brussels, 1996.
“On the effectiveness of search engines”, in: J. Tromp (Ed.), A dynamic and quick intellect, Liber Amicorum: Paul Vit´
anyi 25 years @ CWI, Centre for Mathematics and Computer
Science, Amsterdam (1996), pp. 81-97.
1997
∗∗ “Five Years for B`eta Students”(“Vijf jaar voor B`eta’s”: De noodzaak van een vijfjarig
curriculum voor de b`eta-opleidingen aan de algemene universiteiten”, in Dutch, contributing
author), Report of the Interuniversitary Committee on the Necessity of a Fifth Curriculum
Year for Science Students in the Netherlands (“Commissie Vijfde Jaar B`eta Studies”), University of Groningen, 1997, 76+VIII pages.
“On interval routing schemes and treewidth” (with H.L. Bodlaender, R.B. Tan, and D.M.
Thilikos), Information and Computation 139 (1997) 92-109.
22
“Informatica 2000” (in Dutch), in: Report of the 4th Annual Meeting of Computer Science Alumni, AVIRUS, Dept of Computer Science, Utrecht University, 1997, pp. 9-12.
“Review of Esprit Long Term Research Project 20.996: EvoNet – the Network of Excellence in Evolutionary Computing” (with S. Marshall), review of April 9 in Brussels, report
for ESPRIT Long-Term Research, unpublished.
1998
“ Over wetenschappelijk ondernemerschap: een faculteit moet een eigen bedrijfje kunnen
zijn”, interview in: Utrecht University Newspaper (U-blad), special section devoted to the
10th anniversary of the Faculty of Mathematics and Computer Science, 15 januari 1998, p. 2.
“Informatica-opleidingen niet herverkavelen maar modernizeren” (“Computer science curricula should not be split but modernized”), in: Automatisering Gids, 27 februari 1998.
“Preface”, in: A-Eskwadraat Study Tour ’98, Preliminary Report, A-Eskwadraat, Utrecht
University, p. 5, 1998.
“Twee Jaar Julius Instituut” (“The Julius Institute after Two Years”) (with Ch.G. van
Weerdt), Report of the Evaluation Committee, internal report for the Faculty of Physics
and Astronomy, Utrecht University, 1998.
“De (IT-)revolutie wordt nu pas goed zichtbaar” (“The IT-revolution is more visible now
than ever before”), interview in: Ericsson Magazine, June 1998, pp. 21-24.
“Onderzoek van de inhoud van een CD-ROM bevattende de broncode van procesbesturingssoftware van IPS 2000 systemen”, report for Gerritse Systems Engineering, unpublished, 1998,
3 pages.
“Onderzoek van enige softwarepakketten voor de procesbesturing van textielverfkeukens zoals
de IPS systemen”, report for Gerritse Systems Engineering, unpublished, 1998, 5 pages.
“The complexity of interval routing on random graphs”(with M. Flammini and A. MarchettiSpaccamela), The Computer Journal 41 (1998) 16-25.
1999
“B`etastudies aan universiteit aantrekkelijker” (“Science studies at the university are becoming more attractive”), interview (with C.T. Jansen) in: Utrechts Nieuwsblad, March 12,
1999, p. 16.
“Emancipatie? Is dat nog relevant dan? - Decanen over emancipatie en onderwijs” (“Is
emancipation still relevant? - Deans about emancipation and education”), interview (with
23
J. Rispens) in: Utrecht University Newspaper (U-blad), Special section devoted to “OERonderwijs evaluatie rapport”, 10 june 1999, p 12.
“Onderzoek naar de volledigheid en werkbaarheid van de inhoud van zes tapes bevattende
IPS-1 en IPS-2 procesbesturingssoftware”, report for Gerritse Systems Engineering, unpublished, 1999, 4 pages.
“Embedded algorithms”, lecture on the accasion of receiving the Bolzano medal, ICALP
1999, Prague.
“On the attractiveness of Utrecht University and academic leadership”, interview, 4 pages,
extracts published in: J. Bensing et al. (Redactie), ‘Werken aan kwaliteit - hoe aantrekkelijk
is de Universiteit Utrecht voor professionals’, Uitgave ter gelegenheid van het afscheid van
Mevr. Dr B.E. van Vucht Tijssen als lid van het CvB, ACKP, Universiteit Utrecht, 1999.
“Kort verslag van een orienterend bezoek aan de faculteit Kunst, Media en Technologie van
de HKU”, internal report for ‘Universitair Strategisch Programma’, Utrecht University, unpublished, 1999, 2 pages.
“Belangrijkste ontwikkeling was de chipstechnologie”, interview on the developments in informatics (by K. Volkers), in: Utrecht University Newspaper (U-blad), 16 december 1999, p
6, shortened version also in: Illuster, Nr. 17, December 1999, p 12.
“Netwerken – Een onderzoeksprogramma op het grensvlak van Informatica en Wiskunde”
(with O. Boxma, V.F. Nicola and A. Schrijver), notitie voor NWO/GBE, unpublished, December 1999, 6 pages.
2000
“Onderzoek van enige handleidingen voor de procesbesturing van textielverfkeukens i.c. de
IPS systemen”, report for Gerritse Systems Engineering, unpublished, 2000, 6 pages.
“Three pro-active themes in computer science”, Conclusions from a FET Brainstorming Meeting held January 17/18 in Brussels, report for EC/DG XIII, 8 pages, unpublished.
“Future themes in theoretical computer science – Conclusions from a discussion meeting”,
excerpt of the previous document, EATCS Bulletin, Nr 71, June 2000, pp. 8-14.
“Ontmoetingen in Utrecht”, in: Liber Amicorum for Arjen Sevenster, 20 year jubilee at
Elsevier Science Publishing, February 20, 2000.
“λ-Coloring of graphs” (with H.L. Bodlaender, T. Kloks, and R.B. Tan), in: H. Reichel
and S. Tison (Eds.), STACS 2000, Proc. 17th Annual Symp. on Theoretical Aspects of
Computer Science, Lecture Notes in Computer Science Vol. 1770, Springer-Verlag, Berlin,
2000, pp. 395-406.
24
“Approximations for λ-coloring of graphs” (with H.L. Bodlaender, T. Kloks, and R.B. Tan),
Techn. Report UU-CS-2000-25, Dept of Computer Science, Utrecht University (2000).
“Review of CoIL: The Computational Intelligence and Learning cluster” (with D. Pearce
and C. Torras), midterm review of February 3 in Brussels, report for EC/DG XIII, 3 pages,
unpublished.
“Marie Curie Individual Fellowships: Mathematics & Information Sciences (MAT) and Engineering (ENG) panel”, co-chairman’s summary, panel meeting May 15-17, report for EC/DG
II - Directorate F, 4 pages, unpublished.
∗∗ “Theoretical Computer Science - Exploring New Frontiers of Theoretical Informatics”
(editor, jointly with O. Watanabe, M. Hagiya, P.D. Mosses and T. Ito), Proc’s Int. Conference IFIP TCS 2000, Lecture Notes in Computer Science Vol 1872, Springer-Verlag, Berlin, 2000.
“On the power of interactive computing” (with J. Wiedermann), in: J.van Leeuwen et al
(Eds), “Theoretical Computer Science - Exploring New Frontiers of Theoretical Computer
Science, Proc. IFIP TCS’2000 Conference, Lecture Notes in Computer Science Vol. 1872,
Springer-Verlag, Berlin, 2000, pp 619-623.
“On algorithms and interaction” (with J. Wiedermann), in: M. Nielsen and B. Rovan (Eds),
Mathematical Foundations of Computer Science 2000, 25th Int. Symposium (MFCS’2000),
Lecture Notes in Computer Science Vol. 1893, Springer-Verlag, Berlin, 2000, pp. 99-112.
“Over de samenwerking met de industrie”, in: Liber Amicorum for R.P. van de Riet, Stichting
Mathematisch Centrum, 2000, pp. 77-78.
“The Turing machine paradigm in contemporary computing” (with J. Wiedermann), Techn.
Report UU-CS-2000-33, Dept of Computer Science, Utrecht University (2000), also in: B.
Enquist and W. Schmidt (Eds), Mathematics Unlimited - 2001 and Beyond, Springer-Verlag,
2001, pp 1139-1155.
“Finding a ∆-regular supergraph of minimum order” (with H.L. Bodlaender and R.B. Tan),
Techn. Report UU-CS-2000-29, Dept of Computer Science, Utrecht University (2000), to appear in Discr Appl. Math.
“Beslist niet alleen voor nerds - 25 jaar Informatica: definitieve doorbraak komt er aan”,
interview, in: Informatica Katern bij het U-blad, 5 oktober 2000, p. 2.
“De eerste hoogleraar - Vechten voor je vakgebied”, interview, in: Informatica Katern bij
het U-blad, 5 oktober 2000, p. 8.
“Marie Curie Individual Fellowships Joint Panels: Mathematics & Information Sciences
(MAT) and Engineering (ENG)”, panel meeting Oct 11-13, chairmen’s report for EC/DG
II - Directorate F, Human Potential Programme, 6 pages, unpublished.
“Global Computing - Cooperation of Autonomous and Mobile Entities in Dynamic Envi25
ronments: A Proactive Initiative” (co-editor of the ‘terms of reference’), report for EC DGINFSO/FET, Brussels, 4 pages, unpublished.
2001
“The Turing machine paradigm in contemporary computing” (with J. Wiedermann), in: B.
Enquist and W. Schmidt (Eds), Mathematics Unlimited - 2001 and Beyond, Springer-Verlag,
2001, pp 1139-1155.
“A computational model of interaction in embedded systems” (with J. Wiedermann), Techn.
Report UU-CS-2001-02, Dept of Computer Science, Utrecht University (2001).
“Breaking the Turing barrier: the case of the Internet” (with J. Wiedermann), Techn. Report,
Institute of Computer Science, Czech Academy of Sciences, Prague, 2001 (to appear).
“Emergence of a super-Turing computational potential in artificial living systems” (with J.
Wiedermann), Techn. Report No. 833, Institute of Computer Science, Academy of Sciences
of the Czech Republic, Prague (2001); also in: J. Kelemen and P. Sos´ık (Eds.), Advances in
Artificial Life, Proc. 6th European Conference (ECAL’2001, or: Artificial Life 2001), Lecture
Notes in Artificial Intelligence Vol 2159, Springer-Verlag, Berlin, 2001, pp 55-65.
“Invoering Bachelor/Master Universiteit Utrecht - Uitgangspunten Universitair Kader” (University Committee Report, contributing member), Bijlage bij het U-Blad, 22 februari 2001, 8
pages.
∗∗ “Automata, Languages and Programming” (editor, jointly with F. Orejas and P.G. Spirakis), Proc’s 28th Int. Colloquium ICALP 2001, Lecture Notes in Computer Science Vol 2076,
Springer-Verlag, Berlin, 2001.
“Beyond the Turing limit: Evolving interactive systems” (with J. Wiedermann), in: L. Pacholski and P. Ruzicka (Ed.), SOFSEM 2001: Theory and Practice of Informatics, Proc. 28th
Conference, Lecture Notes in Computer Science Vol 2234, Springer-Verlag, Berlin, 2001, pp
90-109.
“Verslag kascommissie over het boekjaar 1.1.2000-31.12.2000” (with J. Wilschut), Utrechtse
Academische Vereniging “Helios”, Utrecht University, 2001.
“Inleiding Thema D - Content management”, in: Programmaboekje Nederlands ICT-Kenniscongres
2001, 6-7 september 2001, p 54.
2002
“The emergent computational potential of evolving artificial living systems” (with J. Wiedermann), Techn. Report UU-CS-2002-002, Institute of Information and Computing Sciences,
Utrecht University (2002).
26
“Advies commissie plaatsbepaling Freudenthal Instituut”, internal report (6 pages, written
with R. van Vlimmeren), Faculty of Mathematics and Computer Science, Utrecht University,
January 2002.
“Relativistic computers and non-uniform complexity theory” (with J. Wiedermann), Techn.
Report 866 , Institute of Computer Science, Czech Academy of Sciences, Prague, 2002, also
in: C.S. Calude, M.J. Dineen, and F. peper (Eds), Unconventional models of computation,
Proc 3rd Int Conference (UMC’2002), Lecture Notes in Computer Science Vol 2509, SpringerVerlag, Berlin, 2002, pp 287-299.
“Exploring the frontiers of computability” (with J. Wiedermann), ERCIM News, No. 50,
July 2002, pp 48-49 (see also: http://www.ercim.org/publication/Ercim News/enw50/
wiedermann.html).
∗∗ “De onderwijsvisitatie Informatica - Toegepaste Informatica - Computerwetenschappen”,
committee report (139 pages, contributing author), Vlaamse Interuniversitaire Raad, Brussels, July 2002.
“Elements of machine learning”, in: SOIA’2002, Proc. Philips Symposium on Intelligent
Algorithms, Eindhoven, 2002, pp. 11-21.
“Algorithmic systems”, contributed section in: Research Assessment 1996-2001 Computer
Science, Faculty of Mathematics and Computer Sience, 2002.
“Performance ratios for the Karmarkar-Karp differencing method” (with W. Michiels, J.
Korst, and E. Aarts), CS-Report 02-17, Dept of Mathematics and Computer Science, Technische Universiteit Eindhoven, 2002.
2003
“The emergent computational potential of evolving artificial living systems” (with J. Wiedermann), Ai Communications 15 (2003) 205-215.
“Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem” (with W. Michiels, J. Korst, and E. Aarts), in: H. Alt and M. Habib
(Eds.), STACS 2003, Proc. 20th Annual Symp. on Theoretical Aspects of Computer Science,
Lecture Notes in Computer Science Vol. 2607, Springer-Verlag, Berlin, 2003, pp. 583-595.
“Periodic Review of IST-FET Global Computing Action IST-2001-33135, Project CRESCCO: Critical Resource Sharing for Cooperation in Complex Systems”, review of January 6 in
Paphos, consolidated report for EC/Directorate IS, unpublished.
“Periodic Review of IST-FET Global Computing Action IST-2001-33116, Project FLAGS:
Foundational Aspects of Global Computing Systems, review of February 1 in Paphos, report
for EC/Directorate IS, unpublished.
27
“Interactief, intelligent en nog veel meer”, Di¨esrede 2003, Communicatie Service Centrum,
Universiteit Utrecht, pp 2-10.
“Interactief, intelligent en nog veel meer - Het veranderende beeld van de informatica”, TINFON 12 (2003) 63-65. Rectificatie: TINFON 12 (2003) 91.
“Report of the Beirat of the Department of Informatics”, report of the meeting in Garching on 22 May 2003, TU M¨
unchen, 2003.
“Performance ratios for the Karmarkar-Karp differencing method” (with W. Michiels, J.
Korst, and E. Aarts), in: H. Broersma et al (Eds), Proc. 2nd Cologne Twente Workshop
on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Math 13, Elsevier
Science, 2003.
“Lineages of automata - A model for evolving interactive systems” (with P. Verbaan and
J. Wiedermann), Techn Report ALCOMFT-03-195, Institute of Information and Computing
Sciences, Utrecht University, 2003.
“Finding a ∆-regular supergraph of minimum order” (with H.L. Bodlaender and R.B. Tan),
Discr. Appl. Math. 131 (2003) 3-9.
“The Distinguished Achievements Award - EATCS Award 2003”, EATCS Bulletin Nr 81,
October 2003, pp. 14-15.
2004
“Evaluation of INRIA - THEME 1B 2003 (R´eseaux et T´el´ecommunications), contributing
author and coordinator, 20 pages, INRIA, unpublished.
“Some hierarchy results in non-uniform complexity theory” (with P. Verbaan and J. Wiedermann), Techn Report UU-CS-2004-xx, Institute of Information and Computing Sciences,
Utrecht University, 2004 (to appear).
“ICT-diensten op niveau”, contributing author, Rapport Adviescommissie Dienstentypologie, 11 pages, Utrecht University, unpublished.
“Approaches in machine learning”, Ch 8 in: W. Verhaegh, E. Aarts, and J. Korst (Eds),
Algorithms in Ambient Intelligence, Philips Research Book Series, Kluwer Academic Publ,
Dordrecht, 2004, pp. 151-166.
“Approximations for λ-colorings of graphs” (with H.L. Bodlaender, T. Kloks, and R.B. Tan),
The Computer Journal 47 (2004) 193-204.
“Lineages of automata - A model for evolving interactive systems” (with P. Verbaan and
J. Wiedermann), Techn Report UU-CS-2004-018, Institute of Information and Computing
Sciences, Utrecht University, 2004.
“Complexity of evolving interactive systems” (with P. Verbaan and J. Wiedermann), in:
28
J. Karhum¨
aki et al. (Eds.), Theory is Forever, Lecture Notes in Computer Science Vol. 3113,
Springer-Verlag, Berlin, 2004, pp 268-281.
“Report of the Beirat of the Department of Informatics”, report of the meeting in Garching on 14 October 2004, TU M¨
unchen, 2004.
“The Distinguished Achievements Award - EATCS Award 2004”, EATCS Bulletin Nr 84,
October 2004, pp. 10-11.
“Nut en wenselijkheid van een verkenning van het wetenschappelijk ICT-onderzoek”, notes, Discussion Meeting, KNAW, Amsterdam, November 9, unpublished.
2005
“Preface” (with F. Orejas), in: F. Orejas, J. van Leeuwen (Guest Eds), Automata, Languages and Programming, Special Issue, Theoretical Computer Science 331 (2005) 1-2.
∗∗ Special Issue, “Automata, Languages and Programming”, Papers Selected from the 28th
International Colloquium on Automata, Languages and Programming (ICALP’01, edited together with F. Orejas), Theoretical Computer Science 331 (2005) issue nr 1.
“Verslag kascommissie over de boekjaren 2001, 2002, en 2003” (with G.A. van Strien), Utrechtse Academische Vereniging “Helios”, Utrecht University, 2005.
“Elk besluit is een beginpunt van ontwikkeling” (“Every decision is the start of a new development”), interview over de oprichting van de nieuwe faculteit B`etawetenschappen, in: Beta
Nieuwsbrief, jaargang 1, nr 3, September 2005.
“The Distinguished Achievements Award - EATCS Award 2005”, EATCS Bulletin Nr 87,
October 2005, pp. 10-11.
2006
“A Theory of Interactive Computation” (with J. Wiedermann), Chapter in: D. Goldin, S.A.
Smolka, and P. Wegner (Eds.), Interactive Computation: the New Paradigm, Springer-Verlag,
Berlin, 2006, pp 119-142.
“Interval routing and minor-monotone graph parameters” (with E.M. Bakker, H.L. Bodlaender, and R.B. Tan), Techn. Report UU-CS-2006-001, Department of Information and
Computing Sciences, Utrecht University (2006).
“Lazy Autoconfiguration in Mobile Ad Hoc Networks and Dynamic Sets of Mobile Agents”
(with J. Wiedermann), Techn. Report UU-CS-2006-018, Department of Information and Computing Sciences, Utrecht University (2006).
29
“Stel je voor: je bent vakdecaan!” (“Introducing/imagine: you are department chairman”),
interview, in: Beta Nieuwsbrief, jaargang 2, nr 6, Mei 2006.
“Report of the Beirat of the Fakult¨at f¨
ur Informatik”, report of the meeting in Garching
on 4 May 2006, TU M¨
unchen, 2006.
“On the representation of disk graphs” (with E.J. van Leeuwen), Techn. Report UU-CS2006-037, Department of Information and Computing Sciences, Utrecht University (2006).
“Panel on the Contributions of the DISC Community to Distributed Computing: A Historical Perspective” (with E. Gafni, M. Raynal, N. Santoro and S. Zaks), in: S. Dolev (Ed.),
Distributed Computing, 20th International Symposium (DISC 2006), Lecture Notes in Computer Science Vol 4167, Springer-Verlag, Berlin, 2006, p 580.
2007
“Performance ratios for the Karmarkar-Karp differencing method” (with W. Michiels, J.
Korst, and E. Aarts), Journal of Combinatorial Optimization 12:1 (2007) 19-32.
∗∗ “SOFSEM 2007: Theory and Practice of Computer Science” (editor, jointly with G.F.
Italiano, W. van der Hoek, Chr. Meinel, H. Sack and F. Pl´asil), Proc’s 33rd Conference on
Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer
Science Vol 4362, Springer-Verlag, Berlin, 2007.
∗∗ “SOFSEM 2007: Theory and Practice of Computer Science” (editor, jointly with G.F.
Italiano, W. van der Hoek, Chr. Meinel, H. Sack, F. Pl´asil andM. Bielikov´a), 33rd Conference on Current Trends in Theory and Practice of Computer Science, Proceedings Volume II,
Institute of Computer Science AS CR, Prague, 2007.
”Jan van Leeuwen, member of the Academia Europaea”, in: Annual Review 2006 (Utrecht
University), p. 35, Utrecht University, 2007.
“Student Enrollment and Image of the Informatics Discipline” (with L. Tanca), Techn. Report
UU-CS-2007-024, Dept of Information and Computing Sciences, Utrecht University (2007).
“Leerstoelenplan Informatica 2007-2012”, committee report (author), Department of Information and Computing Sciences, Utrecht University, June 2007.
(with M. Veldhorst) Structuurrapport ‘Leerstoel Multimedia’, Departement Informatica, Universiteit Utrecht, 2007.
2008
“Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint” (with H.L.
Bodlaender, R.B. Tan, and Th.C. van Dijk), Techn. Report UU-CS-2008-005, Department of
30
Information and Computing Sciences, Utrecht University (2008), in: J. Gudmundsson (Ed.),
Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Proceedings, Lecture Notes in Computer Science, Vol. 5124, Springer-Verlag, Berlin, 2008, pp.
102-113.
“How We Think of Computing Today” (with J. Wiedermann), in: A. Beckmann, C. Dimitracopoulos, and B. L¨
owe (Eds.), Logic and Theory of Algorithms, 4th Conference on
Computability in Europe (CiE 2008), Proceedings, Lecture Notes in Computer Science, Vol.
5028, Springer-Verlag, Berlin, 2008, pp. 579-593.
(with M. Veldhorst) Structuurrapport ‘Leerstoel Architecture of Information Systems’, Departement Informatica, Universiteit Utrecht, 2008.
“The Technion Faculty of Computer Science” (contributing author with R.H. Katz, C. Beeri,
and D.P. Dobkin), submitted to the President of the Technion, unpublished report, May 2008.
“TNO Defence, Security and Safety - BU1 and BU2”, External Technology Audit, Audit
report 2008 sp 0441 (with R.W. Harwig et al.), TNO Strategy and Research Planning, 45
pages (unpublished).
“Discussion on Field-specific Quality Assurance of Informatics Higher Education - Perspectives from Academics and Industry’, ppt presentation (unpublished), Euro-Inf Final Conference,
University of Cagliari, 04 Sept.
“Student Enrollment and Image of the Discipline” (with L. Tanca), Working Group Report for Informatics Europe, Informatics Europe, 2008 (published on the website).
“Forming a collegial network” (with B. Meyer), in: Workshop for (New) Department Chairs,
ECSS 2008, Informatics Europe, ETH Z¨
urich, Oct 7, 2008 (ppt only).
“On Informatics and Algorithms Research”, Erwiderung, RWTH Aachen, October 24, 2008.
“Research-intensive universities, excellence, and teaching”, keynote address, National Faculties meeting, Oslo-Sandviken, November 12, 2008 (ppt only).
“Jan van Leeuwen blikt terug”, interview, BetaNieuws Nr 15 (2009), 18 december 2009.
2009
“De faculteit, wat zeg ik: DE faculteit”, bijdrage afscheidsliber voor Eugene Bernard, 7
januari 2009.
“A fascinating science”, in: H.L. Bodlaender et al. (Ed.), Fascination for Computation 25 Jaar opleiding Informatica, Utrecht University, Utrecht, 2009, pp. 33-46.
“What type of computer scientist do we need for the future”, at LSI UPC, Barcelona March
17, 2009 (ppt only).
31
“The quest for a philosophy of the information and computing sciences”, speech (unpublished), NIAS, March 11, 2009.
“Towards a philosophy of the information and computing sciences”, NIAS Newsletter 42,
pp 22-25,2009.
“Ultieme informatie”, interview (door B. Mols), NRC Handelsblad 18/19 April, Wetenschapsbijlage, p. 2009.
“Research evaluation for computer science” (with B. Meyer, Chr. Choppy and J. Staunstrup),
Viewpoint article, C.ACM 52:4 (2009) 31-34 .
“Algorithmic Systems”, contributed section in: Research Assessment Computer Science 20022008, Faculty of Science, Utrecht, 2009, pp. 139-159.
“Connecting the informatics departments and research centers in Europe”, at ECSS 2009,
Paris 2009 (ppt only).
“Informatics: Constructing a new world...”, invited address, 35 Year Anniversary (Predn´aˇskov´e
popoludnie pri prileˇzitosti 35), Department of Computer Science, Comenius University, Bratislava, November 9, 2009 (ppt only).
“Structure of Polynomial-Time Approximation” (with E.J. van Leeuwen), Techn. ReportUUCS-2009-034, Department of Information and Computing Sciences, Utrecht University (2009).
2010
∗∗ “SOFSEM 2010: Theory and Practice of Computer Science” (editor, jointly with A.
Muscholl, D. Peleg, J. Pokorn´
y and B. Rumpe), Proc’s 36th Conference on Current Trends
in Theory and Practice of Computer Science, Lecture Notes in Computer Science Vol 5901,
Springer-Verlag, Berlin, 2010.
∗∗ “SOFSEM 2010: Theory and Practice of Computer Science” (editor, jointly with M.
Bielikov´a, A. Muscholl, D. Peleg, J. Pokorn´
y and B. Rumpe), 36th Conference on Current
Trends in Theory and Practice of Computer Science, Proceedings Volume II, Institute of
Computer Science AS CR, Prague, 2010.
“Computation as unbounded process”, in: Workshop ‘Philosophy of the Information and
Computing Sciences’, Lorentz Center, Leiden, February 10, 2010 (ppt only).
“Middenin de informatierevolutie”, interview (door B. Mols), in: B. Mols, Omringd door
Informatica, uitgave CWI, Amsterdam, 2010, pp. 12-17.
Bijdrage aan “Mijlpalen van de informatica en haar toepassingen” (historisch overzicht, door
B. Mols), in: B. Mols, Omringd door Informatica, uitgave CWI, Amsterdam, 2010, pp. 122135.
32
Bijdrage aan “Bouwstenen voor de volgende informatierevolutie”, interview (door B. Mols),
in: NWO Hypothese 17:2 (2010) 14-16.
“On measures of complexity”, in: Th. Janssen and L. Torenvliet, em Lectori Salutem, Liber
Amicorum for P. van Emde Boas, Ammsterdam, 2010, pp 39-44.
“Distinguished Lorentz Fellowship 2009”, eindverslag voor NIAS, maart 2010 (unpublished).
“Leven in de Infosfeer - De informatiemens en zijn e-omgeving”, interview (door H. de Man),
Digitale Bibliotheek 2:5 (2010) 26-31.
“Round the bend, amidst the trees”, in: A. Brandstetter et al, Liber Amicorum for W.
Blockmans, NIAS, Wassenaar, 2010, pp. 50-52.
“From ALGOL 60 to the things we program now’, presentation, ALGOL 60 - 50 year anniv.
meeting, Museum Boerhaave, Leiden 2010 (ppt only)
“Convex polygon intersection graphs” (with E.J. van Leeuwen), Techn. Report UU-CS-2010026, Department of Information and Computing Sciences, Utrecht University (2010).
“Strategies of the association of informatics departments and IT research centers in Europe”, at ECSS 2010, Prague 2010 (ppt only, published on the ECSS 2010 website).
“Panel: Future of the European scientific societies in informatics”, summary of the panel
at ECSS 2010, October 13, 2010, Prague (pdf, published on the ECSS 2010 website).
“De kennis-ICT paradox”, interview (door J.C.E. Brouwers), in: (Laatste) Nieuwsbrief, Nr
19, ICTRegie, November 2010, pp 10-11.
2011
“We hebben in feite een nieuwe Turing nodig”, interview (door W. Klein Ikkink), in: I/O
ICT-Onderzoek, Magazine van IPN, NWO Exacte Wetenschappen, 8:1 (2011) 8-9.
“Convex polygon intersection graphs” (with E.J. van Leeuwen), in: U. Brandes, S. Cornelsen
(Eds.), Graph Drawing, Proceedings 18th International Symposium (GD 2010), Lecture Notes in Computer Science Vol 6502, Springer-Verlag, Berlin, 2011, pp 377-388.
“Name resolution by rewriting in dynamic networks of mobile entities”(with J. Wiedermann),
in: C.S. Calude, G. Rozenberg, and A. Salomaa (Eds.), Rainbow of Computer science, Lecture Notes in Computer Science Vol 6570, Springer-Verlag, Berlin, 2011, pp 215-227.
“Integer representation of convex polygon intersection graphs” (with T. M¨
uller and E.J. van
Leeuwen), in: F. Hurtado, M. van Kreveld (Eds), 27th ACM Symposium on Computational
Geometry (SoCG 2011), Proceedings, Paris, 2011, ACM, pp. 300-307.
33
“Extended panel: Future of the European Scientific Societies in Informatics”, discussion
paper, panel at CEPIS, March 17, 2011, Brussels (published on ECSS website).
‘Watson and the philosophy of computation’, colloquium, ITU, Copenhagen, 2011 (ppt only).
“Computer Science
i” (with B. Meyer et al), Journal of St Petersburg State University, Nr 9 (3834) 30 juni 2011. (http://journal.spbu.ru/?p=519, “Computer Science is fighting
for a fair assessment”, translation of CACM 52:4 (2009) 31-34).
“European Forum for ICST”, Blueprint, Task group report, Extended Panel on ‘the Future
of the European Scientific Societies in Informatics’, July, 2011 (published on the ‘societies’
website only).
“B`eta-reserves in perspectief”, rapport commissie ‘Reservebeleid’ (voorz), Faculteit B`etawetenschappen,
Utrecht, juli, 2011.
“Conclusies Inpassing FIsme”, rapport commissie (met E. Vermeulen), Faculteit B`etawetenschappen,
Utrecht, juli, 2011.
“Future of the European Scientific Societies in Informatics - Milan Agreement”, November
2011, (published on the ‘societies’ website only).
∗∗“Digitale en andere werkelijkheden”, valedictory speech, Utrecht, 2011.
2012
“Het rekenwerk van de computer”, interview door E. Hardeman, Digitaal Universiteitsblad
(DUB), Utrecht, 18 Januari 2012.
“Computer-assisted proof of performance ratios for the Differencing Method” (with W. Michiels, E. Aarts, J. Korst, and F.C.R. Spieksma), J. Discrete Optimization 9 (2012), pp. 1-16.
“Structure of Polynomial-Time Approximation” (with E.J. van Leeuwen), Theory of Comput
Systems 50:4 (2012) 641-674.
“Computation as an unbounded process” (with J. Wiedermann), Theor. Computer Sci 429
(2012) 202-212
“Department evaluation - Protocol for research assessment in Informatics, Computer Science, and IT department and research institutes”(with H-U. Heiss, M. Nagl, C. Pereira, and
L. Tanca), Informatics Europe, Z¨
urich, 2012.
“The scientific and professional ICT societies in Europe and their contribution to the Digital Future” (with P. van Roy), discussion paper, European Forum for ICST, 2012.
34
“Meeting on 09-1-May 2012”, Notes/actions of the Pisa meeting (with C. Pereira), European Forum for ICST, 2012 (published on the website).
“Where to send your paper?”, position paper, Perspectives Workshop: Publication Culture in Computing Research, 6-9 Oct 2012, Dagstuhl. (Abstract in: Dagstuhl Reports 2013,
Vol 2, Nr 11, p. 38.)
“Is cyber security a research job for computer science?”, panel contribution, ERCIM 2012
Symposium, Sophia Antipolis, 2012 (ppt only).
“Role and strategies of the European Public Research Organisations in ICST towards Horizon
2020”, panel contribution, ERCIM 2012 Symposium, Sophia Antipolis, 2012 (ppt only).
“Turing’s impact on understanding computation”, invited lecture, turing100.nl (VvL), Public
Library, Amsterdam, October 5, 2012 (ppt only).
“Turing’s impact on computability and complexity”, lecture (in ‘100 year Turing’), KU Leuven, November 28, 2012 (ppt only).
2013
“Integer representation of convex polygon intersection graphs” (with T. M¨
uller and E.J.
van Leeuwen), SIAM J. Discr Mathematics 27:1 (2013) 205231 (extended abstract: Computational Geometry - SoCG 2011, Proceedings, Paris, 2011, ACM, pp. 300-307), http:
//epubs.siam.org/doi/abs/10.1137/110825224.
“Shaping the digital future of Europe” (with P. van Roy and M. Shapiro), Strategy paper
2013-2015, European Forum for ICST, 2013 (published on the website).
“Rethinking computation” (with J. Wiedermann), in: M. Brown and Y. Erden (Eds), What
is computation, Proc. 6th AISB Symp on Computing and Philosophy, AISB Convention 2013,
Exeter, 2013, pp. 6-10.
“Tempora mutantur, nos et mutamur in illis”, in: J. Hage, A. Dijkstra, Een lawine van
ontwortelde bomen, Liber Amicorum for S.D. Swierstra, Utrecht, 2013, pp. 34-38.
“The role and relevance of experimentation in Informatics”(with C. Andujar, V. Schiaffonati, F.A. Schreiber, L. Tanca, M. Tedre, and K. van Hee), Informatics Europe Report,
Informatics Europe, 2013 (published on the IE website).
∗∗“Alan Turing: His Work and Impact”(editor, with S.B. Cooper), Elsevier, Amsterdam,
2013 (xxi+914 pages).
“The computational power of Turing’s non-terminating circular a-machines” (with J. Wiedermann), in: S.B. Cooper & J. van Leeuwen, Alan Turing: His Work and Impact, Elsevier,
35
2013, pp. 80-84.
“Department evaluation - Protocol for research assessment in Informatics, Computer Science, and IT department and research institutes”(with H-U. Heiss, M. Nagl, C. Pereira, and
L. Tanca), revised report, Informatics Europe, Z¨
urich, 2013.
“European Forum for ICST” (with F. Gagliardi), brief overview, ACM Europe Council, Paris,
May 1, 2013 (ppt only, published on www.eficst.eu).
“Treewidth and pure Nash equilibria”(with A. Thomas), in: G. Gutin, S. Szeider (Eds),
Parameterized and Exact Computation, Proc. 8th Int. Symposium (IPEC 2013), LNCS 8246,
Springer Int Publ Switzerland, 2013, pp. 348-360.
“Meeting on June 10th, 2013”, Notes/actions of the Potsdam meeting, European Forum
for ICST, 2012 (published on the website).
“Computing in Dutch secondary education” (with E. Barendsen et al), workshop proposal, September 2013.
“Het denkraam van uh ...”, in: M. van Kreveld, R.C. Veltkamp (Eds.), Liber Amicorum
voor M.H. Overmars, Utrecht, 2013 (1 pag).
“Watson and the power of learning Turing machines” (with J. Wiedermann), manuscript,
2013.
”Informatics (and how it is changing) as an academic discipline”, in Festkolloquium ”40
Jahre Fakult¨
atentag Informatik”, TU Berlin, Nov 21, 2013 (ppt only).
“Pure Nash equilibria in graphical games and treewidth”(with A. Thomas), submitted to
Special issue Algorithmica
2014
“On Floridi’s method of levels of abstraction”, Minds & Machines 24:1 (2013) 5-17.
“Turing machines with one-sided advice and the acceptance of the co-RE languages”(with
J. Wiedermann), Techn. Report UU-CS-2014-003, Department of Information and Computing Sciences, Utrecht University (2014), submitted for publication.
“Separating the classes of recursively enumerable languages based on machine size”(with J.
Wiedermann), Techn. Report UU-CS-2014-014, Department of Information and Computing
Sciences, Utrecht University (2014), submitted for publication.
“Computation as knowledge generation, with application to the observer-relativity problem”(with
J.Wiedermann), in: M. Brown and Y. Erden (Eds), Proc. 6th AISB Symp on Computing and
36
Philosophy, AISB 50 Convention 2014, London, 2014, 8 pages.
37

Vakken in het derde jaar van de BSc

voorbeeld zonder context tool:valstrikken

Kerndocent Chemische Technologie (1,0 fte)

Biografie Dr. Jos J. de Koning is universitair hoofddocent bij de

NEMO is het grootste Science Center van Nederland en is een

Bekijk rouwbrief - Uitvaartcentrum Matheï

Verzekeringen voor de life science sector Casualty

Neem deel aan de jaarlijkse wedstrijd van SCIENCE ON STAGE

weber.rep 750 / Cerinol MK

Bioprocesregeling