Parties reconnaissables de monoïdes définis par générateurs et relations
Partitioning Arrangements of Lines, I: An Efficient Deterministic Algorithm.
Pascal's triangle, complexity and automata. (Triangle de Pascal, complexité et automates.)
Paths through fixed vertices in edge-colored graphs
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
PCP-prime words and primality types
Performance considerations on a random graph model for parallel processing
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...