Periodic Orbits for Additive Cellular Automata.
Permanents, Pfaffian orientations, and even directed circuits.
Permissive strategies : from parity games to safety games
It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem of finding...
Permissive strategies: from parity games to safety games
It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem...
Persistency in the Traveling Salesman Problem on Halin graphs
For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition , , of the edge set E, where: = e ∈ E, e belongs to all optimum solutions, = e ∈ E, e does not belong to any optimum solution and = e ∈ E, e belongs to some but not to all optimum solutions.
Piecewise Linear Paths Among Convex Obstacles.
Pipelined decomposable BSP computers
The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.
Pipelined Decomposable BSP Computers
The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.
Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments.
Planning a Purely Translational Motion for a Convex Object in Two-Dimensional Space Using Generalized Voronoi Diagrams.
Plongements quasiisométriques du groupe de Heisenberg dans , d’après Cheeger, Kleiner, Lee, Naor
Bref survol du théorème de non-plongement de J. Cheeger et B. Kleiner pour le groupe d’Heisenberg dans .
Pm numbers, ambiguity, and regularity
Points and Triangles in the Plane and Halving Planes in Space.
Polyabelian loops and Boolean completeness
We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property Boolean completeness. It is a generalization of functional completeness, and is intimately connected to the computational complexity of various questions about expressions, circuits, and equations defined over the loop. We say that a loop is polyabelian if it is an iterated affine quasidirect product of Abelian groups; polyabelianness...
Polygon placement under translation and rotation
Polygon Triangulation in O(n log log n) Time with Simple Data Structures.
Polygonizations of Point Sets in the Plane.
Polynomial complexity of the Gilman-Maskit discreteness algorithm.
Polynomial languages with finite antidictionaries
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
Polynomial languages with finite antidictionaries
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.