TR-96-12: On Systems with Sense of Direction

For a system with Sense of Direction, there are several possible consistent coding functions c and corresponding decoding functions d. Thus, it is desirable for a given system to identify, among all the couples (c, d) which are Sense of Direction, those who have additional properties. In fact, by using such properties, the solution of problems in a system could be further improved without any modication in the labeling. We rst consider two such properties: a strong form of decoding consistency called everywhere consistency, and the coding property called everywhere associativity. We prove that for any system with Sense of Direction there always exists at least a couple (c, d) where c is everywhere associative and d is everywhere consistent. The proof is constructive.We then focus on systems with edge symmetry. For these systems we study three impor- tant properties in presence of Sense of Direction: backward consistency, name symmetry, and homonymity. We establish a number of results for each of these properties, as well as some relationships among them. Some of these results have immediate practical ap- plications. For example, our results imply that all proper colorings can be tested in (low) polynomial time.