Concorrência, redes de petri e teoria da informação: aspectos comuns. - GURJÃO, Edmar Candeia. (2003)
A Teoria da Informação tem grande sucesso quando aplicada a sistemas ponto-a-ponto, porém muitos problemas permanecem em aberto nos sistems multi-ponto (sistemas de comunicação em rede), como por exemplo a determinação da região de capacidade (conjunto de taxas máximas simultâneas para um conjunto de transmissores) de certos canais. A transmissão da informação de uma fonte para um destino consiste na geração de eventos físicos no lado da fonte e na observação de eventos físicos no lado do destino, para sistemas em rede. tais eventos não podem ser totalmente ordenados. A ausência de ordenação entre eventos foi estudada no âmbito da ciência da computação por Carl A. Petri que introduziu precisamente a noção de "concorrência" entre eventos. Assim é natural esperar que os problemas para o cálculo de capacidade de redes de comunicação possam estar relacionados com os problemas da modelagem de sistemas concorrentes, sendo esta relação a principal motivação desta tese. As redes de Petri são uma ferramenta bastante poderosa para a modelagem desses sistemas capturando os conceitos de estado distribuído, as relações de concorrência e causalidade entre eventos. Nesta tese ínícia-se o uso de redes de Petri para a análise da capacidade de sistemas de comunicação multi-ponto. Neste sentido, é feita uma extensão de uma medida de complexidade definida para as rede de Petri, denominada de compressibilidade. Mostra-se que a compressibilidade de uma rede pode ser calculada a partir de uma matriz de adjacências associada ao seu grafo de cobertura. Também são apresentadas algumas propriedades dessa medida. Usando a compressibilidade, são obtidas algumas conclusões a respeito da representação e do comportamento de sistemas concorrentes. São apresentados exemplos de sistemas não-ruidosos concorrentes que geram símbolos obedecendo restrições semelhantes às restrições de um sistema de gravação magnética. Apresenta-se um método para o cálculo da capacidade desses sistemas por meio da modelagem em redes de Petri e de uma função de rotulação