Inverse monoids of higher-dimensional stringsReportar como inadecuado

Inverse monoids of higher-dimensional strings - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 PoSET - Models for a Structured Programming of Space and Time LaBRI - Laboratoire Bordelais de Recherche en Informatique, SCRIME - Studio de Création et de Recherche en Informatique et Musique Électroacoustique, Inria Bordeaux - Sud-Ouest 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : Halfway between graph transformation theory and inverse semigroup theory, we define higher dimensional strings as bi-deterministic graphs with distinguished sets of input roots and output roots. We show that these generalized strings can be equipped with an associative product so that the resulting algebraic structure is an inverse semigroup. Its natural order is shown to capture existence of root preserving graph mor-phism. A simple set of generators is characterized. As a subsemigroup example, we show how all finite grids are finitely generated. Last, simple additional restrictions on products lead to the definition of subclasses with decidable Monadic Second Order MSO language theory.

Autor: David Janin -



Documentos relacionados