This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

Submitted by Michele Mologni (mologni@unoeste.br) on 2018-07-27T17:57:40Z No. of bitstreams: 1 Gustavo Francisco Rosalin Saraiva.pdf: 5041218 bytes, checksum: 30127a7816b12d3bd7e57182e6229bc2 (MD5) / Made available in DSpace on 2018-07-27T17:57:40Z (GMT). No. of bitstreams: 1 Gustavo Francisco Rosalin Saraiva.pdf: 5041218 bytes, checksum: 30127a7816b12d3bd7e57182e6229bc2 (MD5) Previous issue date: 2017-03-31 / Plants are complex organisms with dynamic processes that, due to their sessile way of life, are influenced by environmental conditions at all times. Plants can accurately perceive and respond to different environmental stimuli intelligently, but this requires a complex and efficient signaling system. Electrical signaling in plants has been known for a long time, but has recently gained prominence with the understanding of the physiological processes of plants. The objective of this thesis was to test the following hypotheses: temporal series of data obtained from electrical signaling of plants have non-random information, with dynamic and oscillatory pattern, such dynamics being affected by environmental stimuli and that there are specific patterns in responses to stimuli. In a controlled environment, stressful environmental stimuli were applied in soybean plants, and the electrical signaling data were collected before and after the application of the stimulus. The time series obtained were analyzed using statistical and computational tools to determine Frequency Spectrum (FFT), Autocorrelation of Values and Approximate Entropy (ApEn). In order to verify the existence of patterns in the series, classification algorithms from the area of machine learning were used. The analysis of the time series showed that the electrical signals collected from plants presented oscillatory dynamics with frequency distribution pattern in power law. The results allow to differentiate with great efficiency series collected before and after the application of the stimuli. The PSD and autocorrelation analyzes showed a great difference in the dynamics of the electric signals before and after the application of the stimuli. The ApEn analysis showed that there was a decrease in the signal complexity after the application of the stimuli. The classification algorithms reached significant values in the accuracy of pattern detection and classification of the time series, showing that there are mathematical patterns in the different electrical responses of the plants. It is concluded that the time series of bioelectrical signals of plants contain discriminant information. The signals have oscillatory dynamics, having their properties altered by environmental stimuli. There are still mathematical patterns built into plant responses to specific stimuli. / As plantas são organismos complexos com processos dinâmicos que, devido ao seu modo séssil de vida, sofrem influência das condições ambientais todo o tempo. Plantas podem percebem e responder com precisão a diferentes estímulos ambientais de forma inteligente, mas para isso se faz necessário um complexo e eficiente sistema de sinalização. A sinalização elétrica em plantas já é conhecida há muito tempo, mas vem ganhando destaque recentemente com seu entendimento em relação aos processos fisiológicos das plantas. O objetivo desta tese foi testar as seguintes hipóteses: séries temporais de dados obtidos da sinalização elétrica de plantas possuem informação não aleatória, com padrão dinâmico e oscilatório, sendo tal dinâmica afetada por estímulos ambientais e que há padrões específicos nas respostas a estímulos. Em ambiente controlado, foram aplicados estímulos ambientais estressantes em plantas de soja, e captados os dados de sinalização elétrica antes e após a aplicação dos mesmos. As séries temporais obtidas foram analisadas utilizando ferramentas estatísticas e computacionais para se determinar o Espectro de Frequências (FFT), Autocorrelação dos valores e Entropia Aproximada (ApEn). Para se verificar a existência de padrões nas séries, foram utilizados algoritmos de classificação da área de aprendizado de máquina. A análise das séries temporais mostrou que os sinais elétricos coletados de plantas apresentaram dinâmica oscilatória com padrão de distribuição de frequências em lei de potência. Os resultados permitem diferenciar com grande eficácia séries coletadas antes e após a aplicação dos estímulos. As análises de PSD e autocorrelação mostraram grande diferença na dinâmica dos sinais elétricos antes e após a aplicação dos estímulos. A análise de ApEn mostrou haver diminuição da complexidade do sinal após a aplicação dos estímulos. Os algoritmos de classificação alcançaram valores significativos na acurácia de detecção de padrões e classificação das séries temporais, mostrando haver padrões matemáticos nas diferentes respostas elétricas das plantas. Conclui-se que as séries temporais de sinais bioelétricos de plantas possuem informação discriminante. Os sinais possuem dinâmica oscilatória, tendo suas propriedades alteradas por estímulos ambientais. Há ainda padrões matemáticos embutidos nas respostas da planta a estímulos específicos.

Made available in DSpace on 2014-12-17T15:26:35Z (GMT). No. of bitstreams: 1 IsaacDBS.pdf: 539336 bytes, checksum: ac9f1f2543159f0c009f0242077b1d5c (MD5) Previous issue date: 2008-07-25 / In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one approaches some necessary definitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation. / Nesta disserta??o estudamos e comparamos dois algoritmos de percola??o, um elaborado por Elias e o outro por Newman e Ziff, utilizando ferramentas te?ricas da complexidade de algoritmos e um algoritmo que efetuou uma compara??o experimental. Dividimos este trabalho em tr?s cap?tulos. O primeiro aborda algumas defini??es e teoremas necess?rios a um estudo matem?tico mais formal da percola??o. O segundo apresenta t?cnicas utilizadas para o c?lculo estimativo de complexidade de algoritmos, sejam elas: pior caso, melhor caso e caso m?dio. Utilizamos a t?cnica do pior caso para estimar a complexidade de ambos algoritmos e assim podermos compar?-los. O ?ltimo cap?tulo mostra diversas caracter?sticas de cada um dos algoritmos e atrav?s da estima- tiva te?rica da complexidade e da compara??o entre os tempos de execu??o da parte mais importante de cada um, conseguimos comparar esses importantes algoritmos que simulam a percola??o