Prof. dr. J. (Jan) van Leeuwen

Buys Ballotgebouw
Princetonplein 5
Kamer 475
3584 CC Utrecht

Prof. dr. J. (Jan) van Leeuwen

Emeritus Professor
General Algorithms
+31 30 253 4001
j.vanleeuwen1@uu.nl

Publications

2022

Scholarly publications

Wiedermann, J., & van Leeuwen, J. (2022). ​Validating Non-trivial Semantic Properties of Autonomous Robots. In V. C. Muller (Ed.), Philosophy and Theory of Artificial Intelligence 2021: PT-AI: 4th Conference on "Philosophy and Theory of Artificial Intelligence" (pp. 91-104). (Studies in Applied Philosophy, Epistemology and Rational Ethics (SAPERE); Vol. 63). Springer. https://doi.org/10.1007/978-3-031-09153-7_8
Wiedermann, J., & van Leeuwen, J. (2022). Autonomní vozidla, která spolupracují a rozumí: Inteligentní algoritmy poda kapotou. In D. Černý, O. Vaculín, & P. Zámečník (Eds.), Automatizované řízení vozidel a autonomní doprava (pp. 54-81). Academia.

2021

Scholarly publications

Wiedermann, J., & van Leeuwen, J. (2021). Towards Minimally Conscious Cyber-Physical Systems: A Manifesto. In T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdzinski, C. Pahl, F. Sikora, & P. W. Wong (Eds.), SOFSEM 2021: Theory and Practice of Computer Science: 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021, Proceedings (1 ed., pp. 43-55). (Lecture Notes in Computer Science ; Vol. 12607 ). Springer Cham. https://doi.org/10.1007/978-3-030-67731-2_4

2020

Scholarly publications

van Leeuwen, J. (2020). Algorithms, complexity, and Hans. In F. V. Fomin, S. Kratsch, & E. J. van Leeuwen (Eds.), Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday (pp. 22-27). (Lecture Notes in Computer Science; Vol. 12160). Springer. https://doi.org/10.1007/978-3-030-42071-0_4

2019

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2019). Understanding Computation: A General Theory of Computational Processes. (Technical Report Series; No. UU-CS-2019-012). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/390075/2019_012.pdf?sequence=1
Wiedermann, J., & van Leeuwen, J. (2019). Finite State Machines with Feedback: An Architecture Supporting Minimal Machine Consciousness. In F. Manea, B. Martin, D. Paulusma, & G. Primiero (Eds.), Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings (pp. 286-297). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11558 LNCS). Springer. https://doi.org/10.1007/978-3-030-22996-2_25
van Leeuwen, J., & Wiedermann, J. (2019). Question answering by humans and machines: a complexity-theoretic view. Theoretical Computer Science, 777, 464-473. https://doi.org/10.1016/j.tcs.2018.08.012

2018

Scholarly publications

Wiedermann, J., & van Leeuwen, J. (2018). Epistemic Computation and Artificial Intelligence. In V. C. Muller (Ed.), Philosophy and Theory of Artificial Intelligence 2017: PT-AI: 3rd Conference on "Philosophy and Theory of Artificial Intelligence" (pp. 215-224). (Studies in Applied Philosophy, Epistemology and Rational Ethics (SAPERE); Vol. 44). Springer. https://doi.org/10.1007/978-3-319-96448-5_22
Tjoa, A. M., Bellatreche, L., Biffl, S., van Leeuwen, J., & Wiedermann, J. (Eds.) (2018). SOFSEM 2018: Theory and Practice of Computer Science: 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29- February 2, 2018, Proceedings. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10706 LNCS). Springer.

2017

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2017). Knowledge, Representation, and the Dynamics of Computation. In G. Dodig-Crnkovic, & R. Giovagnoli (Eds.), Representation and Reality in Humans, Other Living Organisms and Intelligent Machines (pp. 69-89). (Studies in Applied Philosophy, Epistemology and Rational Ethics (SAPERE); Vol. 28). Springer. https://doi.org/10.1007/978-3-319-43784-2_5
Kloks, T., Tan, R. B., & van Leeuwen, J. (2017). Tracking maximum ascending subsequences in sequences of partially ordered data. (Technical Report Series; No. UU-CS-2017-010). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/354856/2017010.pdf?sequence=1
Wiedermann, J., & van Leeuwen, J. (2017). Non-classical Turing machines: extending the notion of computation. In R. Freund, F. Mraz, & D. Prusa (Eds.), Proceedings Ninth Workshop on Non-Classical Models of Automata and Applications: NCMA 2017 Prague, Czech Republic (pp. 29-40). (books@ocg.at; Vol. 329). Osterreichische Computer Gesellschaft.
van Leeuwen, J., & Wiedermann, J. (2017). Turing machines with one-sided advice and acceptance of the co-RE languages. Fundamenta Informaticae, 153(4), 347-366. https://doi.org/10.3233/FI-2017-1544
Tan, R. B., van Leeuwen, E. J., & van Leeuwen, J. (2017). Shortcutting directed and undirected networks with a degree constraint. Discrete Applied Mathematics, 220, 91-117. https://doi.org/10.1016/j.dam.2016.12.016

2016

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2016). Question-answering and cognitive automata with background intelligence. (Technical Report Series; No. UU-CS-2016-007). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/344557/Question.pdf?sequence=1
van Leeuwen, J. (2016). On the subsequence theorem of Erdős and Szekeres. (Technical Report Series; No. UU-CS-2016-004). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/344556/Subsequence.pdf?sequence=1

2015

Scholarly publications

Wiedermann, J., & Van Leeuwen, J. (2015). Towards a computational theory of epistemic creativity. In AISB Convention 2015 The Society for the Study of Artificial Intelligence and the Simulation of Behaviour (AISB).
Van Leeuwen, J., & Wiedermann, J. (2015). Separating the Classes of Recursively Enumerable Languages Based on Machine Size. International Journal of Foundations of Computer Science, 26(6), 677-695. https://doi.org/10.1142/S0129054115500380
Wiedermann, J., & van Leeuwen, J. (2015). What is computation: An epistemic approach. In SOFSEM 2015: theory and practice of computer science: 41st International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015, Proceedings (pp. 1-13). (Lecture Notes in Computer Science; Vol. 8939), (Lecture Notes in Artificial Intelligence), (Lecture Notes in Bioinformatics). Springer. https://doi.org/10.1007/978-3-662-46078-8_1
van Leeuwen, J. (2015). A note on recursively enumerable classes of partial recursive functions. (Technical Report Series; No. UU-CS-2015-001). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/309763/2015_001.pdf?sequence=1
Thomas, A., & van Leeuwen, J. (2015). Pure Nash Equilibria in Graphical Games and Treewidth. Algorithmica, 71(3), 581-604. https://doi.org/10.1007/s00453-014-9923-3

2014

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2014). Separating the classes of recursively enumerable languages based on machine size. (Technical report Series; No. UU-CS-2014-014). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/304715/2014_014.pdf?sequence=1
van Leeuwen, J., & Wiedermann, J. (2014). Turing machines with one-sided advice and the acceptance of the co-RE languages. (Technical Report Series; No. UU-CS-2014-003). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/304944/2014_003.pdf?sequence=1
Tan, R. B., van Leeuwen, E. J., & van Leeuwen, J. (2014). Shortcutting directed and undirected networks with a degree constraint. (Technical Report Series; No. UU-CS-2014-020). UU BETA ICS Departement Informatica.
https://dspace.library.uu.nl/bitstream/handle/1874/305101/20.pdf?sequence=1
Wiedermann, J., & Van Leeuwen, J. (2014). Computation as knowledge generation, with application to the observer-relativity problem. In AISB 2014 - 50th Annual Convention of the AISB Society for the Study of Artificial Intelligence and the Simulation of Behaviour.
Van Leeuwen, J. (2014). On Floridi's method of levels of abstraction. Minds and Machines, 24(1), 5-17. https://doi.org/10.1007/s11023-013-9321-7

2013

Scholarly publications

Müller, T., van Leeuwen, E. J., & van Leeuwen, J. (2013). Integer representations of convex polygon intersection graphs. SIAM Journal on Discrete Mathematics, 27(1), 205-231. https://doi.org/10.1137/110825224
Wiedermann, J., & Van Leeuwen, J. (2013). Rethinking computations. In 6th AISB Symposium on Computing and Philosophy: The Scandal of Computation - What is Computation? - AISB Convention 2013 (pp. 6-10)

2011

Scholarly publications

Müller, T., van Leeuwen, E. J., & van Leeuwen, J. (2011). Integer representations of convex polygon intersection graphs. In Computational geometry (SCG'11) (pp. 300-307). ACM New York. https://doi.org/10.1145/1998196.1998248
Thomas, A., & van Leeuwen, J. (2011). Games on Graphs - The Complexity of Pure Nash Equilibria. Department of Information and Computing Sciences, Utrecht University.

2009

Scholarly publications

van Leeuwen, J. (2009). A Fascinating Science. In Fascination for Computation - 25 Jaar opleiding Informatica (pp. 33-46)
Meyer, B., Choppy, C., Staunstrup, J., & van Leeuwen, J. (2009). Research Evaluation for Computer Science. Communications of the ACM, 52(4), 31-34. https://doi.org/10.1145/1498765.1498780

2008

Scholarly publications

Wiedermann, J., & van Leeuwen, J. (2008). How We Think of Computing Today. In A. Beckmann, C. Dimitracopoulos, & B. Löwe (Eds.), Logic and Theory of Algorithms (pp. 579-593). Springer.

2007

Scholarly publications

van Leeuwen, J., & Tanca, L. (2007). Student Enrollment and Image of the Informatics Discipline. (UU-CS ed.) UU WINFI Informatica en Informatiekunde. http://www.cs.uu.nl/research/techreps/UU-CS-2007-024.html

2006

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2006). A Theory of Interactive Computation. In D. Goldin, S. A. Smolka, & P. Wegner (Eds.), Interactive Computation: the New Paradigm (pp. 119-142). Springer.

2004

Scholarly publications

Bodlaender, H. L., Kloks, T., Tan, R. B., & van Leeuwen, J. (2004). Approximations for Lambda-Colorings of Graphs. The Computer Journal, 47, 193-204.
van Leeuwen, J. (2004). The Distinguished Achievements Award - EATCS Award 2004. EATCS Bulletin, 84, 10-11.

2003

Scholarly publications

Michiels, W., Korst, J., Aarts, E., & van Leeuwen, J. (2003). Performance ratios for the Differencing Method applied to the Balanced Number Partitioning problem. In 20th Annual Symp.\ on Theoretical Aspects of Computer Science (STACS 2003) Springer.
van Leeuwen, J., & Wiedermann, J. (2003). The emergent computational potential of evolving artificial living systems. AI Communications, 15, 205-215.

2002

Scholarly publications

van Leeuwen, J., & Wiedermann, J. (2002). Exploring the frontiers of computability. ERCIM news, 50, 48-49.

2001

Scholarly publications

Orejas, F., Spirakis, P. G., & van Leeuwen, J. (2001). Automata, Languages and Programming - ICALP'2001. (LNCS ed.) Springer.
van Leeuwen, J., & Wiedermann, J. (2001). The Turing machine paradigm in contemporary computing. In B. Enquist, & W. Schmid (Eds.), Mathematics Unlimited - 2001 and Beyond (pp. 1139-1155). Springer.

2000

Scholarly publications

Bodlaender, H. L., Tan, R. B., & van Leeuwen, J. (2000). Finding a Delta-regular supergraph of minimum order. (UU-CS ed.) Utrecht University: Information and Computing Sciences. http://www.cs.uu.nl/research/techreps/UU-CS-2000-29.html
Bodlaender, H. L., Kloks, A. J. J., Tan, R. B., & van Leeuwen, J. (2000). Approximations for Lambda-coloring of graphs. (UU-CS ed.) Utrecht University: Information and Computing Sciences. http://www.cs.uu.nl/research/techreps/UU-CS-2000-25.html

1996

Scholarly publications

Bodlaender, H. L., van Leeuwen, J., Tan, R. B., & Thilikos, D. M. (1996). On interval routing schemes and treewidth. (UU-CS ed.) Utrecht University: Information and Computing Sciences. http://www.cs.uu.nl/research/techreps/UU-CS-1996-41.html

1995

Scholarly publications

Bodlaender, H., Tan, R. B., Thilokos, D., & van Leeuwen, J. (1995). On Interval Routing Schemes and treewidth. In M. Nagl (Ed.), Graph-Theoretic Concepts in Computer Science: 21st International Workshop, WG '95 Aachen, Germany, June 20–22, 1995 Proceedings (Vol. 1017, pp. 181-196). (Lecture Notes in Computer Science). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-60618-1_75
van Leeuwen, J. (1995). Guessing Games, Binomial Sum Trees and Distributed Computations in Synchronous Networks. (UU-CS ed.) Utrecht University. http://www.cs.uu.nl/research/techreps/UU-CS-1995-13.html

1990

Scholarly publications

Bodlaender, H. L., Gritzmann, P., Klee, V., & Van Leeuwen, J. (1990). Computational complexity of norm-maximization. Combinatorica, 10(2), 203-225. https://doi.org/10.1007/BF02123011

1988

Scholarly publications

van Leeuwen, J. (1988). An optimal pointer machine algorithm for finding nearest common ancestors. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-88-17.html

1987

Scholarly publications

Schoone, A. A., Bodlaender, H., & van Leeuwen, J. (1987). Diameter increase caused by edge deletion. Journal of Graph Theory, 11(3). https://doi.org/10.1002/jgt.3190110315
Schoone, A. A., Bodlaender, H., & van Leeuwen, J. (1987). Improved diameter bounds for altered graphs. In G. Tinhofer, & G. Schmidt (Eds.), Proceedings 12th International Workshop on Graph Theoretic Concepts in Computer Science, WG'86 (pp. 227-236). (Lecture Notes in Computer Science; Vol. 246). Springer. https://doi.org/10.1007/3-540-17218-1_61
Gafni, E., & van Leeuwen, J. (1987). 2nd International Workshop on Distributed Algorithms (draft papers). (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-87-10.html

1986

Scholarly publications

Bodlaender, H., & van Leeuwen, J. (1986). New Upperbounds for Decentralized Extrema-Finding in a Ring of Processors. In B. Monien, & G. Vidal-Naquet (Eds.), Proceedings 3rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 86 (pp. 119-129). (Lecture Notes in Computer Science; Vol. 210). Springer. https://doi.org/10.1007/3-540-16078-7_70
Bodlaender, H. L., & van Leeuwen, J. (1986). Simulation of large networks on smaller networks. Information and control, 71(3), 143-180.
van Leeuwen, J., & Tan, R. B. (1986). Very thin VLSI-layouts of complete binary trees. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-86-07.html
Tel, G., van Leeuwen, J., & Wijshoff, H. A. G. (1986). The one-dimensional skewing problem. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-86-08.html

1985

Scholarly publications

Bodlaender, H., & van Leeuwen, J. (1985). Simulation of Large Networks on Smaller Networks. In K. Mehlhorn (Ed.), Proceedings 2nd Symposium of Theoretical Aspects of Computer Science (pp. 47-58). (Lecture Notes in Computer Science; Vol. 182). Springer. https://doi.org/10.1007/BFb0023994
Schoone, A. A., & van Leeuwen, J. (1985). Verification of balanced link-level protocols. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-85-12.html

1983

Scholarly publications

van Leeuwen, J., & Tan, R. B. (1983). Routing with compact routing tables. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-83-16.html
van Leeuwen, J. (1983). Parallel computers and algorithms. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-83-13.html

1982

Scholarly publications

Kramer, P. P. G., & van Leeuwen, J. (1982). The NP-completeness of finding minimum area Layouts for VLSI-circuits (to appear). (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-82-06.html

1981

Scholarly publications

Overmars, M. H., & van Leeuwen, J. (1981). Maintenance of configurations in the plane (revised edition). (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-81-03.html

1980

Scholarly publications

Overmars, M. H., & van Leeuwen, J. (1980). Some principles for dynamizing decomposable searching problems. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-80-01.html
Overmars, M. H., & van Leeuwen, J. (1980). Dynamization of decomposable searching problems yielding good worst case bounds. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-80-06.html
Overmars, M. H., & van Leeuwen, J. (1980). Dynamic multi-dimensional data structures based on quad- and k-d trees. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-80-02.html

1979

Scholarly publications

van Leeuwen, J. (1979). The complexity of basic complex operations. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-79-04.html
Overmars, M. H., & van Leeuwen, J. (1979). Two general methods for dynamizing decomposable searching problems. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-79-10.html
Overmars, M. H., & van Leeuwen, J. (1979). Rapid subtree indentification revisited. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-79-03.html

1978

Scholarly publications

van Leeuwen, J. (1978). Linear time generation of a new fixed-length data-compression code. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-78-03.html

1977

Scholarly publications

van Leeuwen, J. (1977). Inleiding tot database systems. (RUU-CS ed.) Unknown Publisher. http://www.cs.uu.nl/research/techreps/RUU-CS-77-04.html