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.
Computing Surfaces via pq-Permutations
PULCINI, GABRIELE
2009-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.