2 citations · 3 across the 8 of their papers we have counts for
8 papers
Non-Interlaced SAT is in P
Dr Serge Burckel
We investigate the NP-Complete problem SAT and the geometry of its instances. For a particular type that we call {\it non-interlaced formulas}, we propose a polynomial time algorit…
Computation with No Memory, and Rearrangeable Multicast Networks
Serge Burckel, Emeric Gioan, Emmanuel Thomé
We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one co…
Data Transmission in the Fourth Dimension
Serge Burckel
Alice wants to send an arbitrary binary word to Bob. We show here that there is no problem for her to do that with only two bits. Of course, we consider here information like a sig…
The Parallel-Sequential Duality : Matrices and Graphs
Serge Burckel
Usually, mathematical objects have highly parallel interpretations. In this paper, we consider them as sequential constructors of other objects. In particular, we prove that every…
Complexity of some Path Problems in DAGs and Linear Orders
Serge Burckel
We investigate here the computational complexity of three natural problems in directed acyclic graphs. We prove their NP Completeness and consider their restrictions to linear orde…
The Inductive Kernels of Graphs
Serge Burckel
It is well known that kernels in graphs are powerful and useful structures, for instance in the theory of games. However, a kernel does not always exist and Chvátal proved in 1973…