The object of the thesis is the computational complexity of certain combinatorial optimisation problems called \emph{valued constraint satisfaction problems}, or \emph{VCSPs} for short. The requirements and optimisation criteria of these problems are expressed by sums of \emph{(valued) constraints} (also called \emph{cost functions}). More precisely, the input of a VCSP consists of a finite set of variables, a finite set of cost functions that depend on these variables, and a cost $u$; the task is to find values for the variables such that the sum of the cost functions is at most $u$. By restricting the set of possible cost functions in the input, a great variety of computational optimisation problems can be modelled as VCSPs. Recently, the computational complexity of all VCSPs for finite sets of cost functions over a finite domain has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear (PL) and piecewise linear homogeneous (PLH) cost functions. The VCSP for a finite set of PLH cost functions can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by (polynomial-time many-one) reducing the problem to a finite-domain VCSP which can be solved using a linear programming relaxation. We apply this result to show the polynomial-time tractability of VCSPs for {\it submodular} PLH cost functions, for {\it convex} PLH cost functions, and for {\it componentwise increasing} PLH cost functions; in fact, we show that submodular PLH functions and componentwise increasing PLH functions form maximally tractable classes of PLH cost functions. We define the notion of {\it expressive power} for sets of cost functions over arbitrary domains, and discuss the relation between the expressive power and the set of fractional operations improving the same set of cost functions over an arbitrary countable domain. Finally, we provide a polynomial-time algorithm solving the restriction of the VCSP for {\it all} PL cost functions to a fixed number of variables.

<p>Neka je A neprazan skup i L = (L;&middot;) proizvoljna mreža sa nulom i jedinicom. Svako preslikavanje A&macr; : A &iexcl;! L zovemo rasplinuti podskup od A. Uobičajeno je da se rasplinute podgrupe defini&scaron;u na grupi. U radu su fazi podgrupe definisane na polugrupi kao i na rasplinutoj podpolugrupi. Jedan od glavnih rezultata je teorema o particiji rasplinutih kompletno regularnih polugrupa. Takođe su definisane rasplinute kongruencije i rasplinute&nbsp;jednakosti na rasplinutim podalgebrama neke algebre i ispitane njihove osobine. Uvedeni su pojmovi: podalgebre rasplinute podalgebre, rasplinutog homomorfizma rasplinute podalgebre na rasplinutu podalgebru i direktnog proizvoda rasplinutih podalgebri. Jedan od važnijih rezultata je teorema koja je uop&scaron;tenje teoreme Birkhoff-a na rasplinutim strukturama.</p> / <p>Let A be nonemptu set, and let L = (L; 6) be a lattice with 0 and 1. The mapping A&macr; : A ! L is called fuzzy subset of A. It is usual to define fuzzy subgroup on the group. In this work fuzzy semigroups are defined on the semigroup and on the fuzzy subsemigroup, too. As a main result is theorem about partition fuzzy completlu regular semigroup. Also, fuzzy congruences are defined, and fuzzy equolites on fuzzy subalgebras of an algebra and their propertes are investigated. We introduced some new notions: subalgebras of fuzzy subalgebras, fuzzy homomorphism of fuzzy subalgebra, and direct product of fuzzy subalgebras. One of the most important result is extension of Birkhoff&rsquo;s theorem on fuzzy structures.</p>

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.

Temperature is a fundamental environmental force shaping species abundance and distributions through its effects on biochemical reaction rates, metabolism, activity, and reproduction. In light of future climate shifts, mainly driven by temperature increases, how will organisms persist in warmer environments? One molecular mechanism that may play an important role in coping with heat stress is the heat shock response (HSR), which protects against molecular damage. To prevent and repair protein damage specifically, Hsps activate and become up-regulated. However, the functional diversity and relevance of heat shock proteins (Hsps) in extending upper thermal limits in taxonomic groups outside marine and model systems is poorly understood. Ants are a good system to understand the physiological mechanisms for coping with heat stress because they have successfully diversified into thermally stressful environments. To identify and characterize the functional diversity of Hsps in ants, I surveyed Hsp orthologues from published ant genomes to test for signatures of positive selection and to reconstruct their evolutionary history. Within Hymenoptera, ants utilize unique sets of Hsps for the HSR. Stabilizing selection was the prevailing force among Hsp orthologues, suggesting that protein activity is conserved. At the same time, regulatory regions (promoters) governing transcriptional up-regulation diversified: species differ in the number and location of heat shock elements (HSEs). Therefore, Hsp expression patterns may be a target for selection in warm environments. I tested whether Hsp expression corresponded with variation in upper thermal limits in forest ant species within the genus Aphaenogaster. Whole colonies were collected throughout the eastern United States and were lab acclimated. There was a positive relationship between upper thermal limits (Critical Thermal maxima, CTmax) and local temperature extremes. Upper thermal limits were also higher in ant species that lived in open habitats (shrub-oak and long-leaf pine savannah) than species occupying closed habitats (deciduous forest). Ant species with higher CTmax expressed Hsps more slowly, at higher temperatures, and at higher maximum levels than those with low CTmax. Because Hsps sense and repair molecular damage, these results suggest the proteomes of open relative to closed canopy forests are more stable. Although deciduous forest ant species may be buffered from temperature stress, it is likely that temperature interacts with other environmental stressors such as water and nutrient availability that may impact upper thermal limits. I measured the influence of dehydration and nutrition stress on upper thermal limits of forest ants from a single population. Ants that were initially starved were much less thermally tolerant than controls and ants that were initially desiccated. Because ants are likely to experience similar combination of stressors in the wild, upper thermal limits may be severely overestimated in single factor experiments. Therefore, realistic forecasting models need to consider multiple environmental stressors. Overall, adaptive tuning of Hsp expression that reflects better protection and tolerance of protein unfolding may have facilitated ant diversification into warm environments. However, additional stressors and mechanisms may constrain the evolution of upper thermal limits.

The goal of the present thesis is to introduce on a Riemannian Spin- manifold a system of partial differential equations for spinor-valued differ- ential forms called Killing equations. We study basic properties of several types of Killing fields and relationships among them. We provide a simple construction of Killing spinor-valued forms from Killing spinors and Killing forms. We also review the construction of metric cone and discuss the re- lationship between Killing spinor-valued forms on the base manifold and parallel spinor-valued forms on the metric cone.

The thesis introduces a logic which combines intuitionistic implication with de Morgan negation in a way which conservatively extends both classical and intuitionistic logic. This logic is the intuitionistic counterpart of the four-valued Belnap-Dunn logic. In relation to this logic, we study de Morgan algebras and their expansions, in particular their expansion with a constant representing inconsistency. We prove a duality for such algebras extending the Priestley duality. We also introduce a weak notion of modal algebra and prove a duality for such algebras. We then define analytic sequent calculi for various logics of de Morgan negation. Powered by TCPDF (www.tcpdf.org)

Title: Models of integer-valued time series with random coefficients Author: Petra Burdejová Department: Department of Probability and Mathematical Statistics Supervisor: Doc. RNDr. Zuzana Prášková, CSc. Abstract: In the presented thesis, a generalized integer-valued autoregres- sive process of the order p (GINAR(p)) is considered first. The main aim is taken to introduction of random coefficient integer-valued autoregressive process (RCINAR(p)). We use a thinning operator in order to define the processes. The main characteristics of GINAR(p) and RCINAR(p) are obtained. Condi- tions for stationarity and ergodicity are stated. Three methods of estimation (Yule-Walker, Conditional least squares, Generalized method of moments) are given and compared in simulation with respect to the mean squared error (MSE). At the end, RCINAR(3) model is applied to a real dataset representing a number of earthquakes per year. Keywords: thinning operator, random coefficients, integer-valued time se- ries, GINAR, RCINAR

On étudie les fonctions multivaluées vers un espace de Hilbert. Après avoir introduit unebonne notion de p énergie, on donne une définition possible d’espace de Sobolev et on prouveun théorème d’existence des p minimiseurs. Puis on considère les fonctions bivaluées de deuxvariables, stationnaires pour les déformations au départ et à l’arrivée. On démontre qu’ellessont localement lipschitziennes et on utilise cette régularité pour montrer la convergence fortedans W1,2 vers leur unique éclatement en un point. L’ensemble de branchement d’une tellefonction est la réunion localement finie de courbes analytiques qui se rencontrent en faisantdes angles égaux. Nous donnons aussi un exemple de fonction discontinue et stationnaireseulement pour les déformations au départ.Dans un deuxième temps, on prouve qu’il n’existe pas de rétraction uniformément continuede l’espace des champs vectoriels continus vers le sous-espace de ceux dont la divergence estnulle en un sens distributionnel. On généralise ce résultat en toute codimension en utilisant lanotion de m charge et à tout ensemble X ⊂ Rn vérifiant une hypothèse géométrique mineure. / We study multiple valued functions with values in a Hilbert space. We introduce a possibledefinition of Sobolev spaces and the rightful notion of p energy. We prove the existence of pminimizers. Then we consider two-valued real functions of two variables which are stationarywith respect to both domain and range transformations. We prove their local Lipschitzcontinuity and use it to establish strong convergence in W1,2 to their unique blow-up at anypoint. We claim that the branch set of any such function consists of finitely many real analyticcurves meeting at nod points with equal angles. We also provide an example showing thatstationarity with respect to domain transformations only does not imply continuity.In a second part, we prove that there does not exist a uniformly continuous retractionfrom the space of continuous vector fields onto the subspace of vector fields whose divergencevanishes in the distributional sense. We then generalise this result using the concept of mcharges on any subset X _ Rn satisfying a mild geometric condition, there is no uniformlycontinuous representation operator for mcharges in X.

Le cadre général de cette thèse est celui de la propriété d’indépendance en théorie des modèles. Les théories sans cette propriété sont appelées NIP ou dépendantes. L’objectif principal est de trouver de nouveaux exemples de théories appartenant à cette classe. Nous montrons d’abord un résultat isolé qui répond une question de Pillay : dans un groupe NIP possédant une partie infinie de classe de nilpotence finie, on y trouve un sous-groupe définissable de même classe de nilpotence et contenant cette partie infinie. Le reste de la thèse est motivé par deux cadres extrêmement proches : les groupes abéliens munis d’une chaîne de sous-groupes uniformément définissables, et les groupes abéliens valués. Dans le premier cas nous identifions une certaine théorie et nous étudions plusieurs extensions de cette théorie. Nous prouvons une élimination des quantificateurs dans chacune des ses extensions, grâce à laquelle la NIP en découle facilement. Le dernier résultat est le plus substantiel. Nous montrons qu’une théorie naturelle de chaîne colorée munie quasi-automorphismes n’a pas la propriété d’indépendance. Nous appliquons ensuite ce résultat à une certaine théorie de groupes valués, étudiée par Simonetta dans le contexte des groupes C-minimaux, pour en conclure qu’elle est NIP. Nous montrons aussi d’une façon assez directe (en utilisant des résultats de Rubin et Poizat) qu’une chaîne colorée munie d’automorphismes est NIP. / This PhD thesis is in the general area of the independence property in model theory.Theories without this property are called NIP or dependent. The main objective of this thesis is to find new examples belonging to this class. Firstly, we prove an isolated result that answers a question stated by Pillay : if a NIP group contains an infinite set of finite nilpotency class, then there exists a definable subgroup of the same nilpotency class containing this set. The rest of this thesis is motivated by two extremely closed related contexts : abelian groups equipped with an uniformly definable chain of subgroups, and valued groups. In the first case we identify a theory and study several extensions of it. We prove quantifier elimination in each of these extensions, and use it to easily conclude that they are NIP. The last result is the most significant one. We prove that a natural theory of linear orderings equipped with quasi-automorphisms doesn’t have the independence property. Then we apply this result to a particular theory of valued abelian groups, which has been studied by Simonetta in the context of C-minimal groups, to conclude that it is NIP. We also prove in a rather straightforward way (using results by Rubin and Poizat) that a linear ordering equipped with automorphisms is NIP

<p>This thesis consists of three papers on the following topics in functional analysis and probability theory: Riesz bases and frames, weakly stationary stochastic processes and analysis of set-valued stochastic processes. In the first paper we investigate Uniformly Bounded Linearly Stationary stochastic processes from the point of view of the theory of Riesz bases. By regarding these stochastic processes as generalized Riesz bases we are able to gain some new insight into there structure. Special attention is paid to regular UBLS processes as well as perturbations of weakly stationary processes. An infinite sequence of subspaces of a Hilbert space is called regular if it is decreasing and zero is the only element in its intersection. In the second paper we ask for conditions under which the regularity of a sequence of subspaces is preserved when the sequence undergoes a deformation by a linear and bounded operator. Linear, bounded and surjective operators are closely linked with frames and we also investigate when a frame is a regular sequence of vectors. A multiprocess is a stochastic process whose values are compact sets. As generalizations of the class of subharmonic processes and the class of subholomorphic processesas introduced by Thomas Ransford, in the third paper of this thesis we introduce the general notions of a gauge of processes and a multigauge of multiprocesses. Compositions of multiprocesses with multifunctions are discussed and the boundary crossing property, related to the intermediate-value property, is investigated for general multiprocesses. Time changes of multiprocesses are investigated in the environment of multigauges and we give a multiprocess version of the Dambis-Dubins-Schwarz Theorem.</p>