Jan van Leeuwen

According to our database1, Jan van Leeuwen authored at least 112 papers between 1973 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.



In proceedings 
PhD thesis 



On csauthors.net:


Algorithms, Complexity, and Hans.
Proceedings of the Treewidth, Kernels, and Algorithms, 2020

Question answering by humans and machines: A complexity-theoretic view.
Theor. Comput. Sci., 2019

Finite State Machines with Feedback: An Architecture Supporting Minimal Machine Consciousness.
Proceedings of the Computing with Foresight and Industry, 2019

Turing Machines with One-sided Advice and Acceptance of the co-RE Languages.
Fundam. Informaticae, 2017

Shortcutting directed and undirected networks with a degree constraint.
Discret. Appl. Math., 2017

Epistemic Computation and Artificial Intelligence.
Proceedings of the Philosophy and Theory of Artificial Intelligence 2017, 2017

Non-classical Turing machines: extending the notion of computation.
Proceedings of the Ninth Workshop on Non-Classical Models of Automata and Applications, 2017

Separating the Classes of Recursively Enumerable Languages Based on Machine Size.
Int. J. Found. Comput. Sci., 2015

Pure Nash Equilibria in Graphical Games and Treewidth.
Algorithmica, 2015

What is Computation: An Epistemic Approach.
Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

On Floridi's Method of Levels of Abstraction.
Minds Mach., 2014

Integer Representations of Convex Polygon Intersection Graphs.
SIAM J. Discret. Math., 2013

Treewidth and Pure Nash Equilibria.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Computation as an unbounded process.
Theor. Comput. Sci., 2012

Structure of Polynomial-Time Approximation.
Theory Comput. Syst., 2012

Computer-assisted proof of performance ratios for the Differencing Method.
Discret. Optim., 2012

Name Resolution by Rewriting in Dynamic Networks of Mobile Entities.
Proceedings of the Rainbow of Computer Science, 2011

Convex Polygon Intersection Graphs.
Proceedings of the Graph Drawing - 18th International Symposium, GD 2010, Konstanz, 2010

Viewpoint - Research evaluation for computer science.
Commun. ACM, 2009

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.
Proceedings of the Algorithm Theory, 2008

How We Think of Computing Today.
Proceedings of the Logic and Theory of Algorithms, 2008

Preface: Automata, Languages and Programming .
Theor. Comput. Sci., 2005

Approximations for lambda-Colorings of Graphs.
Comput. J., 2004

Complexity of Evolving Interactive Systems.
Proceedings of the Theory Is Forever, 2004

Performance Ratios for the Karmarkar-Karp Differencing Method.
Electron. Notes Discret. Math., 2003

Finding a bigtriangleup-regular supergraph of minimum order.
Discret. Appl. Math., 2003

Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

The emergent computational potential of evolving artificial living systems.
AI Commun., 2002

Relativistic Computers and Non-uniform Complexity Theory.
Proceedings of the Unconventional Models of Computation, Third International Conference, 2002

Beyond the Turing Limit: Evolving Interactive Systems.
Proceedings of the SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics Piestany, Slovak Republic, November 24, 2001

Emergence of a Super-Turing Computational Potential in Artificial Living Systems.
Proceedings of the Advances in Artificial Life, 6th European Conference, 2001

lambda-Coloring of Graphs.
Proceedings of the STACS 2000, 2000

On Algorithms and Interaction.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

On the Power of Interactive Computing.
Proceedings of the Theoretical Computer Science, 2000

The Complexity of Interval Routing on Random Graphs.
Comput. J., 1998

On Interval Routing Schemes and Treewidth.
Inf. Comput., 1997

Compact Routing Methods: A Survey.
Proceedings of the Structural Information and Communication Complexity, 1994

Uniform <i>d</i>-emulations of rings, with an application to distributed virtual ring construction.
Networks, 1993

Maintenance of 2- and 3-edge- connected components of graphs I.
Discret. Math., 1993

Prefix Routing Schemes in Dynamic Networks.
Comput. Networks ISDN Syst., 1993

Interval Heaps.
Comput. J., 1993

Parallel computing.
Future Gener. Comput. Syst., 1992

On Models for Propositional Dynamic Logic.
Theor. Comput. Sci., 1991

On special multiples of integers.
Bull. EATCS, 1990

Computational complexity of norm-maximization.
Comb., 1990

The File Distribution Problem for Processor Networks.
Proceedings of the SWAT 90, 1990

Graph Algorithms.
Proceedings of the Handbook of Theoretical Computer Science, 1990

Efficient Elections in Chordal Ring Networks.
Algorithmica, 1989

Structured NC.
Proceedings of the Algorithms and Data Structures, 1989

Fast Simulation of Turing Machines by Random Access Machines.
SIAM J. Comput., 1988

The Derivation of Graph Marking Algorithms From Distributed Termination Detection Protocols.
Sci. Comput. Program., 1988

On Estimating the Complexity of Logarithmic Decompositions.
Inf. Process. Lett., 1988

Assertional Verification of a Majority Consensus Algorithm for Concurrency Control in Multiple Copy Databases.
Proceedings of the Concurrency 88: International Conference on Concurrency, 1988

On Linear Skewing Schemes and d-Ordered Vectors.
IEEE Trans. Computers, 1987

Diameter increase caused by edge deletion.
J. Graph Theory, 1987

A non-deterministic algorithm and its analysis.
Bull. EATCS, 1987

An Improved Upperbound for Distributed Election in Bidirectional Rings of Processors.
Distributed Comput., 1987

Interval Routing.
Comput. J., 1987

Array Processing Machines: An Abstract Model.
BIT Comput. Sci. Sect., 1987

Maintenance of Transitive Closures and Transitive Reductions of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, International Workshop, 1987

The Derivation of on-the-fly Garbage Collection Algorithms from Distributed Termination Detection Protocols.
Proceedings of the STACS 87, 1987

Guessing Games and Distributed Computations in Synchronous Networks.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Simulation of Large Networks on Smaller Networks
Inf. Control., December, 1986

Improved Diameter Bounds for Altered Graphs.
Proceedings of the Graphtheoretic Concepts in Computer Science, International Workshop, 1986

New Upperbounds for Decentralized Extrema-Finding in a Ring of Processors.
Proceedings of the STACS 86, 1986

Pragmatic Aspects of Complexity Theory (Panel).
Proceedings of the Information Processing 86, 1986

The Structure of Periodic Storage Schemes for Parallel Memories.
IEEE Trans. Computers, 1985

Inf. Control., 1985

Array processing machines.
Proceedings of the Fundamentals of Computation Theory, 1985

Arbitrary versus Periodic Storage Schemes and Tessellations of the Plane Using One Type of Polyomino
Inf. Control., July, 1984

Worst-case Analysis of Set Union Algorithms.
J. ACM, 1984

Computing the Connected Components of Simple Rectilinear Geometrical Objects in D-Space.
RAIRO Theor. Informatics Appl., 1984

Systolische Berechnungen und VLSI.
Inform. Spektrum, 1984

Periodic versus arbitrary tessellations of the plane using polyominos of a single type.
Proceedings of the Theoretical Computer Science, 1983

The VLSI complexity of Boolean functions.
Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983

Data Mappings in Large Parallel Computers.
Proceedings of the GI - 13. Jahrestagung, Hamburg, 3.-7. Oktober 1983, Proceedings, 1983

Efficient Recognition of Rational Relations.
Inf. Process. Lett., 1982

Dynamic Multi-Dimensional Data Structures Based on Quad- and <i> K - D </i> Trees.
Acta Informatica, 1982

Stratified Balanced Search Trees.
Acta Informatica, 1982

Maintenance of Configurations in the Plane.
J. Comput. Syst. Sci., 1981

The Measure Problem for Rectangular Ranges in d-Space.
J. Algorithms, 1981

Worst-Case Optimal Insertion and Deletion Methods for Decomposable Searching Problems.
Inf. Process. Lett., 1981

Some Principles for Dynamizing Decomposable Searching Problems.
Inf. Process. Lett., 1981

Two general methods for dynamizing decomposable searching problems.
Computing, 1981

The complexity of basic complex operations.
Computing, 1981

Untangling a Travelling Salesman Tour in the Plane.
Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), 1981

Dynamization of Decomposable Searching Problems Yielding Good Worsts-Case Bounds.
Proceedings of the Theoretical Computer Science, 1981

The Art of Dynamizing.
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

Stack Machines and Classes of Nonnested Macro Languages.
J. ACM, 1980

Further Comments on Bykat's Convex Hull Algorithm.
Inf. Process. Lett., 1980

Dynamization of Decomposable Searching Problems.
Inf. Process. Lett., 1980

Über Programmeffizienz und algebraische Komplexität.
Inform. Spektrum, 1980

Dynamically Maintaining Configurations in the Plane (Detailed Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

On the Complexity of Decision Trees, the Quasi-Optimizer, and the Power of Heuristic rules
Inf. Control., January, 1979

A Family of Similarity Measures Between Two Strings.
IEEE Trans. Pattern Anal. Mach. Intell., 1979

On Compromising Statistical Data-Bases with a few Known Elements.
Inf. Process. Lett., 1979

A Useful Lemma for Context-Free Programmed Grammars.
Acta Informatica, 1979

Move Rules and Trade-Offs in the Pebble Game.
Proceedings of the Theoretical Computer Science, 1979

The complexity of complex division (extended abstract).
Proceedings of the Fundamentals of Computation Theory, 1979

Effective constructions in well-partially- ordered free monoids.
Discret. Math., 1978

A Decomposition Theorem for Hyper-Algebraic Extensions of Language Families.
Theor. Comput. Sci., 1976

The Halting Problem for Linear Turing Assemblers.
J. Comput. Syst. Sci., 1976

The Complexity of Vector-Products.
Inf. Process. Lett., 1976

On the Construction of Huffman Trees.
Proceedings of the Third International Colloquium on Automata, 1976

Variations of a New Machine Model
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

The Tape-Complexity of Context-Independent Developmental Languages.
J. Comput. Syst. Sci., 1975

The Membership Question for ET0L-Languages is Polynomially Complete.
Inf. Process. Lett., 1975

An Improved Bound for Detecting Looping Configurations in Deterministic DPA's.
Inf. Process. Lett., 1974

A Partial Solution to the Reachability-Problem for Vector-Addition Systems
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

A Generalisation of Parikh's Theorem in Formal Language Theory.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

Notes on Pre-Set Pushdown Automata.
Proceedings of the L Systems, 1974

Characterization of unary developmental languages.
Discret. Math., 1973