Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-12-12T17:57:13Z No. of bitstreams: 1 HanielMoreiraBarbosa_TESE.pdf: 2203436 bytes, checksum: 38477e5641001f5d9fdcb2ab0ac16855 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-12-13T18:11:52Z (GMT) No. of bitstreams: 1 HanielMoreiraBarbosa_TESE.pdf: 2203436 bytes, checksum: 38477e5641001f5d9fdcb2ab0ac16855 (MD5) / Made available in DSpace on 2017-12-13T18:11:52Z (GMT). No. of bitstreams: 1 HanielMoreiraBarbosa_TESE.pdf: 2203436 bytes, checksum: 38477e5641001f5d9fdcb2ab0ac16855 (MD5) Previous issue date: 2017-09-05 / Em muitas aplica??es de m?todos formais, como verifica??o formal, s?ntese de programas, testes autom?ticos e an?lise de programas, ? comum depender de solucionadores de satisfatibilidade m?dulo teorias (SMT) como backends para resolver automaticamente condi??es que precisam ser verificadas e fornecer certificados de seus resultados. Nesta tese, objetivamos melhorar a efici?ncia dos solucionadores SMT e aumentar sua confiabilidade. Nossa primeira contribui??o ? fornecer um arcabou?o uniforme e eficiente para raciocinar com f?rmulas quantificadas em solucionadores SMT, em que, geralmente, v?rias t?cnicas de instancia??o s?o empregadas para lidar com quantificadores. Mostramos que as principais t?cnicas de instancia??o podem ser lan?adas neste arcabou?o unificador para lidar com f?rmulas quantificadas com igualdade e fun??es n?o interpretadas. O arcabou?o baseia-se no problema de E-ground (dis)unifica??o, uma varia??o do problema cl?ssico de E-unifica??o r?gida. Apresentamos um c?lculo correto e completo para resolver esse problema na pr?tica: Fechamento de Congru?ncia com Vari?veis Livres (CCFV). Uma avalia??o experimental ? apresentada, na qual medimos o impacto das otimiza??es e t?cnicas de instancia??o baseadas no CCFV nos solucionadores SMT veriT e CVC4. Mostramos que nossas implementa??es exibem melhorias em rela??o ?s abordagens de ?ltima gera??o em v?rias bibliotecas de refer?ncia, decorrentes de aplica??es do mundo real. Nossa segunda contribui??o ? uma estrutura para o processamento de f?rmulas ao mesmo tempo que produz demonstra??es detalhadas. Nosso objetivo ? aumentar a confiabilidade nos resultados de solucionadores SMT e sistemas de racioc?nio automatizado similares, fornecendo justificativas que podem ser verificadas com efici?ncia de forma independente e para melhorar sua usabilidade por aplicativos externos. Os assistentes de demonstra??o, por exemplo, geralmente requerem a reconstru??o da justifica??o fornecida pelo solucionador em uma determinada obriga??o de prova. Os principais componentes da nossa estrutura de produ??o de demonstra??es s?o um algoritmo gen?rico de recurs?o contextual e um conjunto extens?vel de regras de infer?ncia. Clausifica??o, Skolemiza??o, simplifica??es espec?ficas de teorias e expans?o das express?es "let" s?o exemplos dessa estrutura. Com estruturas de dados adequadas, a gera??o de demonstra??es cria apenas uma sobrecarga de tempo linear, e as demonstra??es podem ser verificadas em tempo linear. Tamb?m implementamos a abordagem em veriT. Isso nos permitiu simplificar drasticamente a base do c?digo, aumentando o n?mero de problemas para os quais demonstra??es detalhadas podem ser produzidas. / In many formal methods applications it is common to rely on SMT solvers to automatically discharge conditions that need to be checked and provide certificates of their results. In this thesis we aim both to improve their efficiency of and to increase their reliability. Our first contribution is a uniform framework for reasoning with quantified formulas in SMT solvers, in which generally various instantiation techniques are employed. We show that the major instantiation techniques can be all cast in this unifying framework. Its basis is the problem of E-ground (dis)unification, a variation of the classic rigid E-unification problem. We introduce a decision procedure to solve this problem in practice: Congruence Closure with Free Variables (CCFV). We measure the impact of optimizations and instantiation techniques based on CCFV in the SMT solvers veriT and CVC4, showing that our implementations exhibit improvements over state-of-the-art approaches in several benchmark libraries stemming from real world applications. Our second contribution is a framework for processing formulas while producing detailed proofs. The main components of our proof producing framework are a generic contextual recursion algorithm and an extensible set of inference rules. With suitable data structures, proof generation creates only a linear-time overhead, and proofs can be checked in linear time. We also implemented the approach in veriT. This allowed us to dramatically simplify the code base while increasing the number of problems for which detailed proofs can be produced.

Made available in DSpace on 2014-12-17T15:03:19Z (GMT). No. of bitstreams: 1 AryTAN.pdf: 1949309 bytes, checksum: 336240ee8606021d63e4dcca774a40b1 (MD5) Previous issue date: 2008-12-22 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / The aim of this approach is to describe the design and construction of a low-cost automated water sampler prototype. In recent years, there is an increasing need on the use of automated equipments for hydro climatic variables to be use in urban and rural environments. Such devices are always used to provide measured information which is of crucial importance on the development of water resources strategies at watershed scale. Actually, many research and water public institutions have been using these kinds of equipments. In most of the cases, automated equipments are expensive and need to be imported, generating a situation of technologic dependency. The prototype is based on an electronic system which controls a peristaltic pump functioning, five solenoid valves and an ultrasonic sensor connected to a datalloger. An interface with the user allows communication with a PC, when the equipment functioning parameters can be provided. The equipment has a hydraulic module composed by a 12V peristaltic pump connected to a distribution circuit composed by five solenoid valves, one of them being used to clean the circuit before each sampling procedure. Samples are collected by four 1.95 polyethylene bottles. The sampler body was made of acrylic material, with a cylindrical shape, and dimensions 0.72 m and 0.38 m height and diameter, respectively. The weight of the equipment without samples is approximately 15 kg, which infers to its portability. The prototype development total cost budget was approximately US$ 1,560.00. Laboratory tests aimed to evaluate the equipment performance and functioning demonstrated satisfactory results / O objetivo deste estudo ? desenvolver e apresentar um prot?tipo de coletor autom?tico de amostras de ?gua. Nos ?ltimos anos, tem havido uma crescente necessidade no uso de equipamentos autom?ticos no monitoramento de vari?veis hidro-clim?ticas, tanto em ambientes rurais como urbanos. Esses equipamentos s?o normalmente usados para gerar informa??o de vital import?ncia no desenvolvimento de a??es em recursos h?dricos na bacia hidrogr?fica. Atualmente, v?rias institui??es p?blicas e de pesquisa t?m usado esses tipos de equipamentos. Na maioria dos casos, os equipamentos autom?ticos s?o caros e necessitam ser importados, gerando uma situa??o de depend?ncia tecnol?gica. O prot?tipo desenvolvido tem como base um sistema eletr?nico que controla o funcionamento de uma bomba perist?ltica, cinco v?lvulas solen?ides e de um sensor ultra-s?nico acoplados a um datalogger. Uma interface com o usu?rio permite comunica??o com um PC, quando os par?metros de funcionamento do equipamento podem ser introduzidos. O equipamento disp?e de um m?dulo hidr?ulico composto de uma bomba perist?ltica 12V acoplada a um circuito de distribui??o com cinco v?lvulas solen?ides, uma delas usada na limpeza do circuito antes de cada coleta de amostra. As amostras s?o coletadas em quatro garrafas de polietileno, capacidade 1,95 ml. A estrutura do equipamento ? feita em acr?lico, com um formato cil?ndrico, dimens?es 0,72 m e 0,38 m de altura e di?metro, respectivamente. O peso do equipamento sem as amostras ? de aproximadamente 15 kg, o que lhe confere portabilidade. O or?amento referente ao custo total de desenvolvimento do equipamento foi de aproximadamente 1.560 d?lares americanos. Testes em laborat?rio, realizados para avaliar seu desempenho e funcionamento, foram bastante satisfat?rios