Computing surfaces via pq-Permutations

In algebraic topology, compact two-dimensional manifolds are usually dealt through a well-defined class of words denoting polygonal presentations. In this article, we show how to eliminate the useless bureaucracy intrinsic to word-based presentations by considering very simple combinatorial structures called pq-permutations. Thanks to their specific effectiveness, pq-permutations induce a rewriting system P able to compute, in a very easy and intuitive way, the quotient surface associated with any given polygonal presentation. The system P is shown to enjoy both the fundamental computational properties of strong normalization and strict strong confluence. © 2009 Wiley Periodicals.