Topological models of concurrency

Abstract

Concurrency theory is the domain of theoretical computer science that deals with systems of simultane ously executing processes. Concurrent systems can be modeled mathematically in many different ways. It turned out relatively recently that directed algebraic topology can be used as a framework for concurrency theory. This dissertation studies the principal topological models of concurrency, namely partially ordered spaces, d-spaces and precubical sets. These models are used to provide semantics for a class of concur rent programs, called simple concurrent PV-programs. Additionally, we propose and implement several algorithms that calculate the mentioned semantics and address doomed and unreachable states/regions.

A teoria da concorrência é o domínio da ciência da computação teórica que estuda sistemas de processos em execução simultânea. Os sistemas concorrentes podem ser modelados matematicamente de muitas formas diferentes. Descobriu-se, há relativamente pouco tempo, que a topologia algébrica dirigida pode ser usada como uma framework para a teoria da concorrência. Esta dissertação estuda os principais modelos topológicos de concorrência, nomeadamente espaços parcialmente ordenados, d-espaços e conjuntos pré-cúbicos. Estes modelos são usados para dar semântica a uma classe de programas concor rentes, chamados programas PV simples. Adicionalmente, propomos e implementamos vários algoritmos que calculam as semânticas mencionadas e abordam estados/regiões doomed e unreachable.