Constraint satisfaction problems (CSPs) form a large class of decision problems that con- tains numerous classical problems like the satisfiability problem for propositional formulas and the graph colourability problem. Feder and Vardi [52] gave the following logical for- malization of the class of CSPs: every finite relational structure A, the template, gives rise to the decision problem of determining whether there exists a homomorphism from a finite input structure B to A. In their seminal paper, Feder and Vardi recognised that CSPs had a particular status in the landscape of computational complexity: despite the generality of these problems, it seemed impossible to construct NP-intermediate problems `a la Ladner [72] within this class. The authors thus conjectured that the class of CSPs satisfies a complexity dichotomy , i.e., that every CSP is solvable in polynomial time or is NP-complete. The Feder-Vardi dichotomy conjecture was the motivation of an intensive line of research over the last two decades. Some of the landmarks of this research are the confirmation of the conjecture for special classes of templates, e.g., for the class of undi- rected graphs [55], for the class of smooth digraphs [5], and for templates with at most three elements [43, 84]. Finally, after being open for 25 years, Bulatov [44] and Zhuk [87] independently proved that the conjecture of Feder and Vardi indeed holds. The success of the research program on the Feder-Vardi conjecture is based on the con- nection between constraint satisfaction problems and universal algebra. In their seminal paper, Feder and Vardi described polynomial-time algorithms for CSPs whose template satisfies some closure properties. These closure properties are properties of the polymor- phism clone of the template and similar properties were later used to provide tractability or hardness criteria [61, 62]. Shortly thereafter, Bulatov, Jeavons, and Krokhin [46] proved that the complexity of the CSP depends only on the equational properties of the poly- morphism clone of the template. They proved that trivial equational properties imply hardness of the CSP, and conjectured that the CSP is solvable in polynomial time if the polymorphism clone of the template satisfies some nontrivial equation. It is this conjecture that Bulatov and Zhuk finally proved, relying on recent developments in universal algebra. As a by-product of the fact that the delineation between polynomial-time tractability and NP-hardness can be stated algebraically, we also obtain that the meta-problem for finite- domain CSPs is decidable. That is, there exists an algorithm that, given a finite relational structure A as input, decides the complexity of the CSP of A.

Network satisfaction problems (NSPs) for finite relation algebras are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polynomial-time algorithms. Since there are known examples of undecidable NSPs of finite relation algebras it is advisable to restrict the scope of such a classification attempt to well-behaved subclasses of relation algebras. The class of relation algebras with a normal representation is such a well-behaved subclass. Many well-known examples of relation algebras, such as the Point Algebra, RCC5, and Allen’s Interval Algebra admit a normal representation. The great advantage of finite relation algebras with normal representations is that their NSP is essentially the same as a constraint satisfaction problem (CSP). For a relational structure B the problem CSP(B) is the computational problem to decide whether a given finite relational structure C has a homomorphism to B. The study of CSPs has a long and rich history, culminating for the time being in the celebrated proofs of the Feder-Vardi dichotomy conjecture. Bulatov and Zhuk independently proved that for every finite structure B the problem CSP(B) is in P or NP-complete. Both proofs rely on the universal-algebraic approach, a powerful theory that connects algebraic properties of structures B with complexity results for the decision problems CSP(B). Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures. The CSPs that emerge from NSPs are typically of the form CSP(B) for an infinite structure B and therefore do not fall into the scope of the dichotomy result for finite structures. In this thesis we study NSPs of finite relation algebras with normal representations by the universal algebraic methods which were developed for the study of finite and infinite-domain CSPs. We additionally make use of model theory and a Ramsey-type result of Nešetril and Rödl. Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs the containment in P implies that the problems can even be solved by Datalog programs, unless P = NP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures.

The determination of semantic equivalence is an undecidable problem; however, this dissertation shows that a reasonable approximation can be obtained using a combination of static and dynamic analysis. This study investigates the detection of functional duplicates, referred to as semantic method clones (SMCs), in Java code. My algorithm extends the input-output notion of observable behavior, used in related work [1, 2], to include the effects of the method. The latter property refers to the persistent changes to the heap, brought about by the execution of the method. To differentiate this from the typical input-output behavior used by other researchers, I have coined the term method IOE-Behavior; which means its input-output and effects behavior [3]. Two methods are defined as semantic method clones, if they have identical IOE-Behavior; that is, for the same inputs (actual parameters and initial heap state), they produce the same output (that is result- for non-void methods, an final heap state). The detection process consists of two static pre-filters used to identify candidate clone sets. This is followed by dynamic tests that actually run the candidate methods, to determine semantic equivalence. The first filter groups the methods by type. The second filter refines the output of the first, grouping methods by their effects. This algorithm is implemented in my tool JSCTracker, used to automate the SMC detection process. The algorithm and tool are validated using a case study comprising of 12 open source Java projects, from different application domains and ranging in size from 2 KLOC (thousand lines of code) to 300 KLOC. The objectives of the case study are posed as 4 research questions: 1. Can method IOE-Behavior be used in SMC detection? 2. What is the impact of the use of the pre-filters on the efficiency of the algorithm? 3. How does the performance of method IOE-Behavior compare to using only inputoutput for identifying SMCs? 4. How reliable are the results obtained when method IOE-Behavior is used in SMC detection? Responses to these questions are obtained by checking each software sample with JSCTracker and analyzing the results. The number of SMCs detected range from 0-45 with an average execution time of 8.5 seconds. The use of the two pre-filters reduces the number of methods that reach the dynamic test phase, by an average of 34%. The IOE-Behavior approach takes an average of 0.010 seconds per method while the input-output approach takes an average of 0.015 seconds. The former also identifies an average of 32% false positives, while the SMCs identified using input-output, have an average of 92% false positives. In terms of reliability, the IOE-Behavior method produces results with precision values of an average of 68% and recall value of 76% on average. These reliability values represent an improvement of over 37% (for precision) and 30% (for recall) of the values in related work [4, 5]. Thus, it is my conclusion that IOE-Behavior can be used to detect SMCs in Java code with reasonable reliability.

Achieving a classification of all clones of operations over a finite set is one of the goals at the heart of universal algebra. In 1921 Post provided a full description of the lattice of all clones over a two-element set. However, over the following years, it has been shown that a similar classification seems arduously reachable even if we only focus on clones over three-element sets: in 1959 Janov and Mučnik proved that there exists a continuum of clones over a k-element set for every k > 2. Subsequent research in universal algebra therefore focused on understanding particular aspects of clone lattices over finite domains. Remarkable results in this direction are the description of maximal and minimal clones. One might still hope to classify all operation clones on finite domains up to some equivalence relation so that equivalent clones share many of the properties that are of interest in universal algebra. In a recent turn of events, a weakening of the notion of clone homomorphism was introduced: a minor-preserving map from a clone C to D is a map which preserves arities and composition with projections. The minor-equivalence relation on clones over finite sets gained importance both in universal algebra and in computer science: minor-equivalent clones satisfy the same set identities of the form f(x_1,...,x_n) = g(y_1,...,y_m), also known as minor-identities. Moreover, it was proved that the complexity of the CSP of a finite structure A only depends on the set of minor-identities satisfied by the polymorphism clone of A. Throughout this dissertation we focus on the poset that arises by considering clones over a three-element set with the following order: we write C ≤_{m} D if there exist a minor-preserving map from C to D. It has been proved that ≤_{m} is a preorder; we call the poset arising from ≤_{m} the pp-constructability poset. We initiate a systematic study of the pp-constructability poset. To this end, we distinguish two cases that are qualitatively distinct: when considering clones over a finite set A, one can either set a boundary on the cardinality of A, or not. We denote by P_n the pp-constructability poset restricted to clones over a set A such that |A|=n and by P_{fin} we denote the whole pp-constructability poset, i.e., we only require A to be finite. First, we prove that P_{fin} is a semilattice and that it has no atoms. Moreover, we provide a complete description of P_2 and describe a significant part of P_3: we prove that P_3 has exactly three submaximal elements and present a full description of the ideal generated by one of these submaximal elements. As a byproduct, we prove that there are only countably many clones of self-dual operations over {0,1,2} up to minor-equivalence.

No description available.

Approximately 10-15% of field-grown eastern white pine (Pinus strobus L.) within a nursery plantation expressed foliar characteristics similar to that induced by oxidant pollution. Sensitive genotypes (based on foliar characteristics), had a 50% reduction in needle growth, severe needle tip burn, mottling, and early needle shed during a high O₃, drought-type growing season (1988) compared to a low O₃, non-drought growing season (1989). Tolerant genotypes showed little difference in needle growth or visible injury during the two growing season. Seasonal needle ascorbate concentrations were similar during the two years however, needle glutathione (GSH) content has not. Total GSH content was two-to three-fold greater in both genotypes during the summer of 1989 compared to 1988. Cloned, tolerant trees also had 23% more total GSH when exposed to forced ambient air compared to charcoal-filtered air in open-top chambers. Cloned sensitive trees had similar GSH concentrations when exposed to different chamber treatments. One-year-old needles always had lower ratios of ascorbate/ dehydroascorbate, ascorbate/α-tocopherol and GSH/GSSG than current year needles. One-year-old needles from the tolerant tree also maintained a higher glutathione reductase (GR) activity than the sensitive tree during the late summer. Needles of eastern white pine had two isoforms of GR (GR_A and GR_B). GR_A and GR_B accounted for 17% and 83% of the GR recovered, respectively. GR_A and GR_B had different physical and kinetic properties. Antibody produced from GRR was reactive with both native and denatured GR_B, but was cross-reactive with only native GR_A. Tolerant and sensitive clones exposed to control (< 0.025 ppm) or high (4.5 ppm∙hr total dose) O₃ for O to 72 hr, showed no increase in GR activity. Only in the high-O₃-treated trees did the amount of GR protein increase. Needles from the sensitive clone contained 14, 62, and 464 ng GR mgP⁻¹ and needles from the tolerant clone contained 21, 138, and 2800 ng GR mgP⁻¹ after 0, 24 and 72 hr O₃ exposure, respectively. The results of this dissertation indicate that differential foliar characteristics in eastern white pine may be correlated with GSH turnover and its regulation by GR during periods of high oxidant stress. / Ph. D.

In this thesis, we consider two problems related to cocommutative comonoids. In the first part, we construct an example of a comonoid which is not cocommutative, yet whose endomorphism operad is a clone. In the second part, we provide a class of examples of algebras which are not smooth, yet whose rings of differential operators are cocommutative Hopf algebroids.

Plant secondary products such as flavonoids have a variety of roles in plants including UV protection, antifeedant activity, pollinator attraction, stress response, flavor, and many more. These compounds also have effects on human physiology. Glucosylation is an important modification of many flavonoids and other plant secondary products. In grapefruit, glucosylation is important in the synthesis of the bitter compound naringin and several flavonoid glucosyltransferase (GT) enzymes have been characterized from young grapefruit leaf tissue. To study structure and function of flavonoid GTs, it is necessary to isolate cDNA’s that can be cloned and manipulated. In prior work, the plant secondary product glucosyltransferase (PSPG) box was used to identify putative GT clones. We report on results from experiments to test the hypothesis that PGT clones 4 and 11 are plant secondary product GTs, specifically flavonoid GTs. Previously, PGT 4 was cloned into a bacterial expression system, however all protein was localized into inclusion bodies and GT activity could not be tested. For this work, recombinant PGT 4 and PGT 11 were transformed into yeast and the proteins expressed and screened for glucosyltransferase activity with a variety of flavonoid substrates including flavanones, flavones, and flavonols.

Made available in DSpace on 2015-03-26T14:01:01Z (GMT). No. of bitstreams: 1 texto completo.pdf: 897624 bytes, checksum: d480d10072d149a1cc7bfa53c79a065b (MD5) Previous issue date: 2010-04-26 / The objective of this study was to analyze the effect of fifteen eucalypt clones forest productivity on wood basic density and kraft pulping yield. Four regions with different raining intensities were used for this study. The base was a trial of genetic and environmental interaction, testing 48 hybrids eucalipt clones, of with 15 with bether silvicultural performance were selected for basic density and kraft pulping yeld analysis. Results obtained demonstrated significant differences in forest annual growth increments and the correlation between forest productivity and wood basic density, showed itself low, concerning genetic aspect and negatively high, considering environmental aspect. It was also detected lower pulping yields for eucalypts clones planted in lower productivity regions and having higher wood density. Differently from other studies published by technical literatures, the alkali charge for pulping did not show significant correlation with pulping yield. / Este estudo teve como objetivo avaliar a influência da produtividade de 15 clones híbridos de eucalipto, plantados em quatro regiões de precipitações pluviométricas distintas, na densidade básica da madeira e na polpação kraft. A base do estudo foi um experimento de interação genótipo x ambiente, em que 48 clones híbridos de eucalipto foram plantados em quatro regiões distintas em termos de precipitação, na região extremo sul da Bahia. Os melhores 15 clones em termos de desempenho silvicultural foram selecionados para análise de densidade básica e polpação Kraft. O delineamento experimental utilizado foi o de blocos ao acaso, com três repetições por local e seis plantas por parcela. Aos 7 anos de idade, os clones foram mensurados e avaliados do ponto de vista silvicultural, ou seja, forma do tronco e da copa, além da incidência de doenças. Os 15 melhores clones tiveram suas madeiras amostradas e transformadas em cavacos, para posterior determinação de suas densidades básicas, também foram submetidos a cozimentos Kraft em digestor Batch, contendo células para 250 gramas de cavacos. Os resultados indicaram diferença significativa de incremento médioanual entre as quatro regiões estudadas, mostrando efeito positivo da precipitação sobre a produtividade e a correlação entre o IMA e a densidade básica da madeira, baixa no aspecto genético e negativamente alta, no aspecto ambiental. Também foi observado menor rendimento de celulose dos clones na região onde ocorreu a menor produtividade e maior densidade da madeira, provavelmente pela maior dificuldade de impregnação dos cavacos pelo álcali. Contrariando outros estudos descritos em literatura, a demanda de álcali para polpação não apresentou correlação com o rendimento decelulose.

The demand for speeding up software development inside corporations triggers a series of issues related to coding organization. Software development teams have to achieve business deadlines, so they adopt the bad practice to copy-and-paste code. In this way, clones populate software repositories and hinder the improvement or maintenance of systems. Programming languages with object-oriented paradigm characteristics tend to make easy coding abstraction and reuse processes. However, a question arises: the same team working with several kinds of programming languages are influenced by their paradigms regarding the decrease of cloning incidence? This work proposed an approach to identify, analyze and compare clones inside heterogeneous software repositories without consider the development team profile. The experimental evaluation of the approach was possible thru two controlled experiments which aimed to detect and evaluate clones, using and adapting tools available on market. This evaluation was executed inside an organizational environment, which owned several applications with closed-source code but available to analysis. The final results showed no relationship to the amount of application code lines. Procedural language systems had a lower clone incidence and, when conflicting open and closed source systems, both had similar results regarding to the manifestation of source-code clones. / A exigência por acelerar o desenvolvimento de software nas empresas desencadeia uma série de problemas relacionados à organização do código. As equipes de desenvolvimento, pressionadas a cumprir prazos ditados pela área de negócio, adotam a prática ruim de copiar e colar código. Assim, os clones são criados e povoam os repositórios de software dessas companhias, tornando o aprimoramento e manutenção dos sistemas cada vez mais dificultado. Linguagens de programação que possuem características do paradigma de orientação a objetos tendem a facilitar ainda mais o processo de abstração de código e de reaproveitamento. No entanto, uma questão pode ser feita: uma mesma equipe, trabalhando com diversos tipos de linguagens, sofre influência destes tipos, no que diz respeito à diminuição da incidência de clones? Este trabalho propôs uma abordagem para identificar, analisar e comparar clones em repositórios heterogêneos de software, com uma análise tênue do perfil da equipe envolvida. A avaliação experimental da abordagem foi realizada por meio de dois experimentos controlados, os quais visaram a detecção e a avaliação de clones, utilizando e adaptando o ferramental disponível no mercado. Esta avaliação foi executada in-vivo, em um ambiente organizacional real, o qual possuía uma grande quantidade de aplicações e linhas de código fechado disponíveis para análise. Os resultados finais não apresentaram relação direta com a quantidade de linhas de código das aplicações. Sistemas de linguagem procedural apresentaram menor incidência de clones e, no conflito entre sistemas de código aberto e fechado, ambos tiveram resultados similares no que diz respeito à manifestação de clones de código-fonte.