Made available in DSpace on 2014-06-12T15:59:39Z (GMT). No. of bitstreams: 2 arquivo5428_1.pdf: 1146136 bytes, checksum: 397adc67935622083166ac6104064af6 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / A busca constante pelo desenvolvimento de sistemas de software com qualidade vem despertando o interesse das grandes empresas na aplicação de técnicas formais. Dentre as linguagens formais, existem aquelas próprias para a modelagem de dados complexos, tal como Z, e outras próprias para a modelagem de comunicação e concorrência, tal como CSP. Circus é uma linguagem de especificação, projeto e programação que combina Z e CSP. Além de possibilitar a especificação de aspectos de dados e comportamentais de sistema concorrentes, Circus inclui um cálculo de refinamentos. Este é seu diferencial em relação a outras integrações de Z com uma álgebra de processos. Circus vem despertando interesse no meio industrial, manifestado através de colaboraçõoes científicas e tecnológicas, e possui uma equipe envolvida na construção de ferramentas que visam facilitar sua utilização. Muitas destas ferramentas precisam de um verificador de tipos para prover mais garantias quanto a consistência das especificações e programas, e, consequentemente, de seus resultados. Neste trabalho, apresentamos uma definição formal para o sistema de tipos de Circus, com o intuito de auxiliar o desenvolvimento de um verificador de tipos para a linguagem. Optamos por primeiramente definir as regras de tipos de Circus para depois implementar o software que automatiza a aplicação dessas regras. Esta decisão de projeto contribuiu para a construção robusta do verificador, pois a implementação consiste em um mapeamento direto das regras de tipos para linhas de código. O verificador desenvolvido também oferece recursos adicionais, tais como, a disponibilidade de informações de tipos para cada fragmento da especificação ou programa passado para análise, e o fornecimento de mensagens claras e objetivas dos possíveis erros de tipos detectados ao longo da verificação. Adicionalmente, projetamos o verificador como um componente de fácil integração, manutenção e extensão. Também apresentamos neste trabalho a nossa estratégia de validação do verificador. Elaboramos testes de pequeno e grande porte, a partir de estudos de casos de sistemas reais, tal como o sistema de SmartCard que descrevemos neste trabalho. Adicionalmente, integramos o verificador com outra ferramenta: o JCircus, que é um tradutor de Circus para Java. Também implementamos uma versão inicial de uma ferramenta de refinamentos, chamada CircusRefine, para integrar o verificador de tipos. Apesar de não termos construído uma versão completa de CircusRefine, nos preocupamos em definir a arquitetura da ferramenta de tal forma que sejam possíveis futuras evoluções de forma simples e estruturada. Os testes e integrações contribuíram para a correção de defeitos da implementação e para a evolução e verificação de consistência do verificador de tipos de Circus. Ao definir o sistema de tipos de Circus, e disponibilizar um verificador de tipos, acreditamos que estamos dando uma importante contribuição na evolução de Circus, esclarecendo pontos essenciais de sua definição como uma linguagem fortemente tipada e compatível com Z e CSP, e estamos também contribuindo para o desenvolvimento de outras ferramentas da linguagem.Esperamos que o nosso trabalho possa servir de base para a definição e implementação dos sistemas de tipos das extensões de Circus

Os sistemas computacionais estão tomando proporções cada vez maiores envolvendo situações bastante complexas, onde muitas vezes erros são inaceitáveis, como em sistemas bancários, sistemas de controle de tráfego aéreo, etc... Para obter software confiável e com desempenho aceitável, pode-se aliar técnicas de desenvolvimento formal de software a técnicas de simulação de sistemas. O ambiente PLATUS reúne essas duas áreas: modelos de simulação são descritos usando gramáticas de grafos uma linguagem de especificação formal. Gramáticas de grafos são uma generalização de gramáticas de Chomsky, substituindo strings por grafos. Neste trabalho, serão tratadas gramáticas de grafos baseados em objetos, um modelo onde vértices e arcos são tipados, e as especificações são modulares (a especificação de um sistema consiste em várias gramáticas de grafos combinadas). Assim, o modelo de um sistema pode ser descrito de forma precisa, e a linguagem de especificação é bastante abstrata e expressiva. Num ambiente de simulação a questão da recuperação de dados merece uma atenção especial, uma vez que a eficiência do simulador está diretamente ligada a agilidade na obtenção das informações. Neste trabalho, o objetivo principal é definir uma representação para gramáticas de grafos que facilite o armazenamento, a recuperação e análise das estruturas identificadas no ambiente PLATUS, ou seja, gramáticas de grafos baseadas em objetos. São definidas também funções que implementam os procedimentos necessários, para a recuperação de dados durante a simulação. A eficiência dessas funções é demonstrada através do cálculo de sua ordem de complexidade. As estruturas são validadas através da implementação de um protótipo de banco de dados.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar. / The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar. / The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

Os sistemas computacionais estão tomando proporções cada vez maiores envolvendo situações bastante complexas, onde muitas vezes erros são inaceitáveis, como em sistemas bancários, sistemas de controle de tráfego aéreo, etc... Para obter software confiável e com desempenho aceitável, pode-se aliar técnicas de desenvolvimento formal de software a técnicas de simulação de sistemas. O ambiente PLATUS reúne essas duas áreas: modelos de simulação são descritos usando gramáticas de grafos uma linguagem de especificação formal. Gramáticas de grafos são uma generalização de gramáticas de Chomsky, substituindo strings por grafos. Neste trabalho, serão tratadas gramáticas de grafos baseados em objetos, um modelo onde vértices e arcos são tipados, e as especificações são modulares (a especificação de um sistema consiste em várias gramáticas de grafos combinadas). Assim, o modelo de um sistema pode ser descrito de forma precisa, e a linguagem de especificação é bastante abstrata e expressiva. Num ambiente de simulação a questão da recuperação de dados merece uma atenção especial, uma vez que a eficiência do simulador está diretamente ligada a agilidade na obtenção das informações. Neste trabalho, o objetivo principal é definir uma representação para gramáticas de grafos que facilite o armazenamento, a recuperação e análise das estruturas identificadas no ambiente PLATUS, ou seja, gramáticas de grafos baseadas em objetos. São definidas também funções que implementam os procedimentos necessários, para a recuperação de dados durante a simulação. A eficiência dessas funções é demonstrada através do cálculo de sua ordem de complexidade. As estruturas são validadas através da implementação de um protótipo de banco de dados.

Os sistemas computacionais estão tomando proporções cada vez maiores envolvendo situações bastante complexas, onde muitas vezes erros são inaceitáveis, como em sistemas bancários, sistemas de controle de tráfego aéreo, etc... Para obter software confiável e com desempenho aceitável, pode-se aliar técnicas de desenvolvimento formal de software a técnicas de simulação de sistemas. O ambiente PLATUS reúne essas duas áreas: modelos de simulação são descritos usando gramáticas de grafos uma linguagem de especificação formal. Gramáticas de grafos são uma generalização de gramáticas de Chomsky, substituindo strings por grafos. Neste trabalho, serão tratadas gramáticas de grafos baseados em objetos, um modelo onde vértices e arcos são tipados, e as especificações são modulares (a especificação de um sistema consiste em várias gramáticas de grafos combinadas). Assim, o modelo de um sistema pode ser descrito de forma precisa, e a linguagem de especificação é bastante abstrata e expressiva. Num ambiente de simulação a questão da recuperação de dados merece uma atenção especial, uma vez que a eficiência do simulador está diretamente ligada a agilidade na obtenção das informações. Neste trabalho, o objetivo principal é definir uma representação para gramáticas de grafos que facilite o armazenamento, a recuperação e análise das estruturas identificadas no ambiente PLATUS, ou seja, gramáticas de grafos baseadas em objetos. São definidas também funções que implementam os procedimentos necessários, para a recuperação de dados durante a simulação. A eficiência dessas funções é demonstrada através do cálculo de sua ordem de complexidade. As estruturas são validadas através da implementação de um protótipo de banco de dados.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar. / The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-26T17:52:58Z (GMT). No. of bitstreams: 1 Bonifacio_AdilsonLuiz_M.pdf: 21453626 bytes, checksum: de7be74dafd77bc551c7395989d64b6f (MD5) Previous issue date: 2000 / Resumo: Sistemas distribuídos híbridos advêm da interconexão de sistemas de dinâmica contínua com sistemas de dinâmica discreta. A noção de autômatos híbridos oferece meios para a construção de especificações formais para tais sistemas. Autômatos híbridos são autômatos finitos, onde cada estado descreve um perfil dinâmico do sistema e cujas transições entre estados provocam alterações nestes perfis dinâmicos. Neste trabalho, alguns sistemas híbridos reais são modelados através de autômatos híbridos. Em seguida, os modelos construídos são verificados, usando-se das facilidades de uma ferramenta computacional. Além disso, alguns parâmetros importantes, que afetam o comportamento operacional dos modelos, têm seus valores sintetizados. Os sistemas alvo desse trabalho são segmentos de via de uma malha metroviária e um sistema de gerenciamento de tráfego aéreo. As verificações foram sempre conduzidas de maneira a garantir uma operação segura dos sistemas estudados. As sínteses realizadas contribuíram para determinar valores mais justos para os parâmetros operacionais enfocados, mantendo a segurança na operação dos sistemas alvo. / Abstract: Distributed hybrid systems result from the interplay of continuous and discrete dynamics systems. The notion of hybrid automata offers a way to formally specify such systems. A hybrid automaton is a finite state automaton, where each state is extended to contain a description for a system dynamie profile. Transitions between states model a change in the system dynamies. In this work, some real hybrid systems are modeled using the formalism of hybrid automata. Next, the models constructed are verified, using the support of a computational tool. Moreover, values are synthesized for some important parameters that affect the system operational behavior. The target systems treated here are segments of a subway mesh and an air traffice control system. The verification sessions aimed at certifying that the system operates safely. Results from the synthesis contributed to obtain tighter values for operational system parameters, while still guaranteeing its safe operation. / Mestrado / Mestre em Ciência da Computação

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro de Filosofia e Ciências Humanas. / Made available in DSpace on 2012-10-18T22:28:55Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-09T02:23:42Z : No. of bitstreams: 1 150950.pdf: 7650809 bytes, checksum: 542b0f25306ed93ca6f3203b350e3f4f (MD5)

Made available in DSpace on 2014-06-12T15:59:17Z (GMT). No. of bitstreams: 2 arquivo4988_1.pdf: 1332321 bytes, checksum: d7fe11f8136beac6845d4e2ab642bbda (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Circus é uma linguagem de especificação e programação que combina CSP, Z, e construtores do Cálculo do Refinamento. A semântica de Circus está baseada na Unifying Theories of Programming (UTP). Neste trabalho, estendemos um subconjunto de Circus com operadores de tempo. A nova linguagem é denominada de Circus Time Action. Propomos um modelo novo do tempo que estende o modelo da UTP, adicionando variáveis de observação para registrar a passagem de tempo. O novo modelo é usado para dar a semântica formal de Circus Time Action. Propriedades algébricas do modelo original de Circus são validadas no novo modelo; propriedades novas são exploradas e validadas dentro do contexto de Circus Time Action. A vantagem de utilizar o padrão de unificação proposto pela UTP é poder comparar e relacionar diferentes modelos. Definimos uma função de abstração, L, que faz o mapeamento das observações registradas no novo modelo (com tempo) para observações no modelo original (sem tempo); uma função inversa, R, é também definida. O objetivo é estabelecer uma ligação formal entre o modelo novo com tempo e o modelo original da UTP. A função L e sua função inversa R formam uma Galois Connection. Usando a função de abstração, nós introduzimos a definição de programas insensíveis ao tempo. A função de abstração permite a exploração de algumas propriedades não temporais de um programa. Apresentamos um exemplo simples para ilustrar o uso da função de abstração na validação de propriedades que não têm tempo associado. Entretanto, sistemas de tempo real têm requisitos temporais que necessitam ser validados. Neste sentido, propomos um framework para a validação de requisitos não temporais usando os dois modelos e a relação entre eles. A estrutura do framework é baseada em um processo de particionamento. Tendo como ponto de partida o programa e sua especificação escritos em Circus Time Action, aplicamos uma função sintática que gera uma forma normal do programa e sua especificação. A forma normal consiste de duas partes: a primeira é um programa sem operadores de tempo, mas com eventos que, por convenção, representam ações temporais; a segunda é uma coleção de temporizadores (timers) usados pelo programa. A composição paralela de ambas as partes é semanticamente equivalente ao programa original. Usando apenas o componente da forma normal que não envolve tempo explicitamente, mostramos que é possível raciocinar sobre propriedades de tempo no modelo não temporal; provamos formalmente a validade deste resultado. Para ilustrar o uso do framework, utilizamos um sistema de alarme simplificado como estudo de caso. Como a validação é reduzida ao modelo sem tempo, usamos a ferramenta de Model-Checking de CSP (FDR) para realizar as provas mecanicamente. Esta é uma outra contribuição importante deste trabalho