For a locally compact group G, the papers [13] and [7] have many results about G-invariant subsets of G-modules, and the relationship between G-module maps, L1(G)-module maps and M(G)-module maps. In both papers, the results were given for one specific module action. In this thesis we extended many of their results to arbitrary Banach G-modules. In addition, we give detailed proofs of most of the results found in the first section of the paper [21].

For a locally compact group G, the papers [13] and [7] have many results about G-invariant subsets of G-modules, and the relationship between G-module maps, L1(G)-module maps and M(G)-module maps. In both papers, the results were given for one specific module action. In this thesis we extended many of their results to arbitrary Banach G-modules. In addition, we give detailed proofs of most of the results found in the first section of the paper [21].

Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise. / Graph homomorphisms are functions from the vertex set of a graph to the vertex set of another graph that preserve adjacencies. The study of graph homomorphisms is very broad, and there are several lines of research about this topic. In this dissertation, we present results about graph homomorphisms related to convergence of graph sequences and connection matrices of graph parameters. This line of research has been proved to be very rich, not only for its results, but also for the proof techniques. In particular, we highlight the diversity of mathematical tools used, including classical results from Algebra, Probability and Analysis.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-06T14:53:31Z No. of bitstreams: 1 ALEX RAMOS BORGES - DISSERTAÇÃO PPGMAT 2012..pdf: 550720 bytes, checksum: cd1d40089c6d522f3d44501f683dc900 (MD5) / Made available in DSpace on 2018-08-06T14:53:31Z (GMT). No. of bitstreams: 1 ALEX RAMOS BORGES - DISSERTAÇÃO PPGMAT 2012..pdf: 550720 bytes, checksum: cd1d40089c6d522f3d44501f683dc900 (MD5) Previous issue date: 2012-12 / Neste trabalho serão estudadas as graduações e identidades polinomiais graduadas da álgebra Un(K) das matrizes triangulares superiores n×n sobre um corpo K, o qual será sempre in nito. Primeiramente, será estudado o caso n = 2, para o qual será mostrado que existe apenas uma graduação não trivial e serão descritos as identidades, as codimensões e os cocaracteres graduados. Para o caso n qualquer, serão estudadas as identidades e codimensões graduadas, considerando-se a Zn-graduação natural de Un(K). Finalmente, será apresentada uma classi cação das graduações de Un(K) por um grupo qualquer. / In this work we study the gradings and the graded polynomial identities of the upper n × n triangular matrices algebra Un(K) over a eld K, which is always in nity. The case n = 2 will be rstly studied, for which will be shown that there is only one nontrivial grading and we shall describe the graded identities, codimensions and cocharacters. For the general n case, we shall study graded identities and codimensions, considering the natural Zn-grading of Un(K). Finally, we will present a classi cation of the gradings of Un(K) by any group.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les programmeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d’ordre supérieur synthétisant le comportement d’algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l’effort de programmation nécessaire sur OSL et d’autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d’utilisation tout en produisant des performances acceptables. / Parallel architectures have now reached every computing device, but software developers generally lackthe skills to program them through explicit models such as MPI or the Pthreads. There is a need for moreabstract models such as the algorithmic skeletons which are a structured approach. They can be viewed ashigher order functions that represent the behaviour of common parallel algorithms, and those are combinedby the programmer to generate parallel programs. Programmers want to obtain better performances through the usage of parallelism, but the development time implied is also an important factor. Algorithmic skeletons provide interesting results in both those fields. The Orléans Skeleton Library or OSL provides a set of algorithmic skeletons for data parallelism within the bulk synchronous parallel model for the C++ language. It uses advanced metaprogramming techniques to obtain good performances. We improved OSL in order to obtain better performances from its generated programs, and extended its expressivity. We wanted to analyze the ratio between the performance of programs and the development effort needed within OSL and other parallel programming models. The comparison between parallel programs written within OSL and their equivalents in low level parallel models shows a better productivity for high level models : they are easy to use for the programmers while providing decent performances.

Cette thèse étudie les aspects combinatoires, algorithmiques et la complexité de problèmes de théorie des graphes, et tout spécialement de problèmes liés aux notions de marches, de transitions et de distance dans les graphes. Nous nous intéressons d’abord au problème de traffic monitoring, qui consiste à placer aussi peu de capteurs que possible sur les arcs d’un graphe de façon à pouvoir reconstituer des marches d’objets. La caractérisation d’instances intéressantes dans la pratique nous amène à la notion de transitions interdites, qui renforce le modèle de graphe. Notre travail sur les graphes à transitions interdites comprend aussi l’étude de la notion d’ensemble de transitions connectant, que l’on peut voir comme l’analogue en terme de transitions de la notion d’arbre couvrant. Une partie importante de cette thèse porte sur les graphes géométriques, qui sont des graphes dont les sommets sont des points de l’espace réel et dont les arêtes sont déterminées par les distances géométriques entre les sommets. Ces graphes sont au coeur du célèbre problème de Hadwiger-Nelson et nous sont d’une grande aide dans notre étude de la densité des ensembles qui évitent la distance 1 dans plusieurs types d’espaces normés. Nous développons des outils pour étudier ces problèmes et les utilisons pour prouver la conjecture de Bachoc-Robins sur plusieurs paralléloèdres. Nous nous penchons aussi sur le cas du plan euclidien et améliorons les bornes sur la densité des ensembles évitant la distance 1 et sur son nombre chromatique fractionnaire. Enfin, nous étudions la complexité de problèmes d’homomorphismes de graphes et établissons des théorèmes de dichotomie sur la complexité des homomorphismes localement injectifs vers les tournois réflexifs. / This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs. We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees. A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger- Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number. Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.

<p>The research work carried out in this thesis is aimed&nbsp;&nbsp; at fuzzifying algebraic and relational structures in the framework of Ω-sets, where Ω is a complete lattice.<br />Therefore we attempt to synthesis universal algebra and fuzzy set theory. Our&nbsp; investigations of Ω-algebraic structures are based on Ω-valued equality, satisability of identities and cut techniques. We introduce Ω-algebras, Ω-valued congruences,&nbsp; corresponding quotient&nbsp; Ω-valued-algebras and&nbsp; Ω-valued homomorphisms and we investigate connections among these notions. We prove that there is an Ω-valued homomorphism from an Ω-algebra to the corresponding quotient Ω-algebra. The kernel<br />of an Ω-valued homomorphism is an Ω-valued congruence. When dealing with cut structures, we prove that an Ω-valued homomorphism determines classical homomorphisms among the corresponding quotient structures over cut&nbsp; subalgebras. In addition, an&nbsp; Ω-valued congruence determines a closure system of classical congruences on cut subalgebras. In addition, identities are preserved under Ω-valued homomorphisms. Therefore in the framework of Ω-sets we were able to introduce Ω-attice both as an ordered and algebraic structures. By this Ω-poset is defined as an Ω-set equipped with&nbsp; Ω-valued order which is&nbsp; antisymmetric with respect to the corresponding Ω-valued equality. Thus defining the notion of pseudo-infimum and pseudo-supremum we obtained the definition of Ω-lattice as an ordered structure. It is also defined that the an Ω-lattice as an algebra is a bi-groupoid equipped with an Ω-valued equality fulfilling some particular lattice Ω-theoretical formulas. Thus using axiom of choice we proved that the two approaches are equivalent. Then we also introduced the notion of complete Ω-lattice based on Ω-lattice. It was defined as a generalization of the classical complete lattice.<br />We proved results that characterizes Ω-structures and many other interesting results.<br />Also the connection between Ω-algebra and the notion of weak congruences is presented.<br />We conclude with what we feel are most interesting areas for future work.</p> / <p>Tema ovog rada je fazifikovanje algebarskih i relacijskih struktura u okviru omega- skupova, gdeje Ω kompletna mreza. U radu se bavimo sintezom oblasti univerzalne algebre i teorije rasplinutih (fazi) skupova. Na&scaron;a istraživanja omega-algebarskih struktura bazirana su na omega-vrednosnoj jednakosti,zadovoljivosti identiteta i tehnici rada sa nivoima. U radu uvodimo omega-algebre,omega-vrednosne kongruencije, odgovarajuće omega-strukture, i omega-vrednosne homomorfizme i istražujemo veze izmedju ovih pojmova. Dokazujemo da postoji Ω -vrednosni homomorfizam iz Ω -algebre na odgovarajuću količničku Ω -algebru. Jezgro Ω -vrednosnog homomorfizma je Ω- vrednosna kongruencija. U vezi sa nivoima struktura, dokazujemo da Ω -vrednosni homomorfizam odredjuje klasične homomorfizme na odgovarajućim količničkim strukturama preko nivoa podalgebri. Osim toga, Ω-vrednosna kongruencija odredjuje sistem zatvaranja klasične kongruencije na nivo podalgebrama. Dalje, identiteti su očuvani u Ω- vrednosnim homomorfnim slikama.U nastavku smo u okviru Ω-skupova uveli Ω-mreže kao uredjene skupove i kao algebre i dokazali ekvivalenciju ovih pojmova. Ω-poset je definisan kao Ω -relacija koja je antisimetrična i tranzitivna u odnosu na odgovarajuću Ω-vrednosnu jednakost. Definisani su pojmovi pseudo-infimuma i pseudo-supremuma i tako smo dobili definiciju Ω-mreže kao uredjene strukture. Takodje je definisana Ω-mreža kao algebra, u ovim kontekstu nosač te strukture je bi-grupoid koji je saglasan sa Ω-vrednosnom jednako&scaron;ću i ispunjava neke mrežno-teorijske formule. Koristeći aksiom izbora dokazali smo da su dva pristupa ekvivalentna. Dalje smo uveli i pojam potpune Ω-mreže kao uop&scaron;tenje klasične potpune mreže. Dokazali smo jo&scaron; neke rezultate koji karakteri&scaron;u Ω-strukture.Data je i veza izmedju Ω-algebre i pojma slabih kongruencija.Na kraju je dat prikaz pravaca daljih istrazivanja.</p>

<p>In this work a comparative analysis of several approaches to fuzzy algebraic structures and comparison of previous approaches to the recent one developed at University of&nbsp; Novi Sad has been done. Special attention is paid to reducts and expansions of algebraic structures in fuzzy settings. Besides mentioning all the relevant algebras and properties developed in this setting, particular new algebras and properties are developed and investigated. Some new structures, in particular Omega Boolean algebras, Omega Boolean lattices and Omega Boolean rings are developed in the framework of omega structures. Equivalences among these structures are elaborated in details. Transfers from Omega groupoids to Omega groups and back are demonstrated. Moreover, normal subgroups are introduced in a particular way. Their connections to congruences are elaborated in this settings. Subgroups, congruences and normal subgroups are investigated for Ω-groups. These are latticevalued algebraic structures, defined on crisp algebras which are not necessarily groups, and in which the classical equality is replaced by a lattice-valued one. A normal Ω-subgroup is defined as a particular class in an Ω-congruence. Our main result is that the quotient groups over cuts of a normal Ω- subgroup of an Ω-group G, are classical normal subgroups of the corresponding quotient groups over G. We also describe the minimal normal Ω-subgroup of an Ω-group, and some other constructions related to Ω-valued congruences.Further results that are obtained are theorems that connect various approaches of fuzzy algebraic structures. A special notion of a generalized lattice valued Boolean algebra is introduced. The universe of this structure is an algebra with two binary, an unary and two nullary operations (as usual), but which is not a crisp Boolean algebra in general. A main element in our approach is a fuzzy&nbsp; quivalence relation such that the Boolean algebras identities are approximately satisfied related to the considered fuzzy equivalence. Main properties of the new introduced notions are proved, and a connection with the notion of a structure of a generalized fuzzy lattice is provided.</p> / <p>Ovaj rad bavi se komparativnom analizom različitih pristupa rasplinutim (fazi) algebarskim strukturama i odnosom tih struktura sa odgovarajućim klasičnim&nbsp;&nbsp; algebrama. Posebna pažnja posvećena je poredenju postojećih pristupa ovom&nbsp;&nbsp; problemu sa novim tehnikama i pojmovima nedavno razvijenim na Univerzitetu u Novom Sadu. U okviru ove analize, proučavana su i pro&scaron;irenja kao i redukti algebarskih struktura u kontekstu rasplinutih algebri. Brojne važne konkretne algebarske strukture istraživane su u ovom kontekstu, a neke nove uvedene su i ispitane. Bavili smo se detaljnim istrazivanjima Ω-grupa, sa stanovista kongruencija, normalnih podgrupa i veze sa klasicnim grupama. Nove strukture koje su u radu uvedene u posebnom delu, istrazene su sa aspekta svojstava i medusobne ekvivalentnosti. To su Ω-Bulove algebre, kao i odgo-varajuce mreže i Bulovi prsteni. Uspostavljena je uzajamna ekvivalentnost tih struktura analogno odnosima u klasičnoj algebri. U osnovi na&scaron;e konstrukcije su mrežno vrednosne algebarske strukture denisane na klasičnim algebrama koje ne zadovoljavaju nužno identitete ispunjene na odgovarajucim klasičnim strukturama (Bulove algebre, prsteni, grupe itd.), već su to samo algebre istog tipa. Klasična jednakost zamenjena je posebnom kompatibilnom rasplinutom (mrežno-vrednosnom) relacijom ekvivalencije. Na navedeni nacin i u cilju koji je u osnovi teze (poredenja sa postojecim pristupima u ovoj naucnoj oblasti) proucavane su (vec denisane)&nbsp; Ω-grupe. U nasim istraživanju uvedene su odgovarajuće normalne podgrupe. Uspostavljena je i istražena njihova veza sa Ω-kongruencijama. Normalna podgrupa&nbsp; Ω-grupe definisana je kao posebna&nbsp; klasa Ω-kongruencije. Jedan od rezultata u ovom delu je da su količničke grupe definisane pomocu nivoa Ω-jednakosti klasične normalne podgrupe odgovarajućih količničkih podgrupa polazne&nbsp; -grupe. I u ovom slučaju osnovna&nbsp; struktura na kojoj je denisana Ω-grupa je grupoid, ne nužno grupa. Opisane su osobine najmanje normalne podgrupe u terminima Ω-kongruencija, a date su i neke konstrukcije&nbsp; Ω-kongruencija.</p><p>Rezultati koji su izloženi u nastavku povezuju različite pristupe nekim mrežno- vrednosnim strukturama. Ω-Bulova algebra je uvedena na strukturi sa dve binarne, unarnom i dve nularne operacije, ali za koju se ne zahteva ispunjenost klasičnih aksioma. Identiteti za Bulove algebre važe kao mrežno-teoretske formule u odnosu na mrežno-vrednosnu jednakost. Klasicne Bulove algebre ih zadovoljavaju, ali obratno ne vazi: iz tih formula ne slede standardne aksiome za Bulove algebre. Na analogan nacin uveden je i&nbsp; Ω-Bulov prsten. Glavna svojstva ovih struktura su opisana. Osnovna osobina je da se klasične Bulove algebre odnosno Bulovi prsteni javljaju kao količničke strukture na nivoima Ω -jednakosti. Veza ove strukture sa Ω-Bulovom mrežom je pokazana.</p><p>Kao ilustracija ovih istraživanja, u radu je navedeno vi&scaron;e primera.</p>

Normalformen drücken semantische Eigenschaften einer Logik durch syntaktische Restriktionen aus. Sie ermöglichen es Algorithmen, Grenzen der Ausdrucksstärke einer Logik auszunutzen. Ein Beispiel ist die Lokalität der Logik erster Stufe (FO), die impliziert, dass Graph-Eigenschaften wie Erreichbarkeit oder Zusammenhang nicht FO-definierbar sind. Gaifman-Normalformen drücken die Bedeutung einer FO-Formel als Boolesche Kombination lokaler Eigenschaften aus. Sie haben eine wichtige Rolle in Model-Checking Algorithmen für Klassen dünn besetzter Graphen, deren Laufzeit durch die Größe der auszuwertenden Formel parametrisiert ist. Es ist jedoch bekannt, dass Gaifman-Normalformen im Allgemeinen nur mit nicht-elementarem Aufwand konstruiert werden können. Dies führt zu einer enormen Parameterabhängigkeit der genannten Algorithmen. Ähnliche nicht-elementare untere Schranken sind auch für Feferman-Vaught-Zerlegungen und für die Erhaltungssätze von Lyndon, Łoś und Tarski bekannt. Diese Arbeit untersucht die Komplexität der genannten Normalformen auf Klassen von Strukturen beschränkten Grades, für welche die nicht-elementaren unteren Schranken nicht gelten. Für diese Einschränkung werden Algorithmen mit elementarer Laufzeit für die Konstruktion von Gaifman-Normalformen, Feferman-Vaught-Zerlegungen, und für die Erhaltungssätze von Lyndon, Łoś und Tarski entwickelt, die in den ersten beiden Fällen worst-case optimal sind. Wichtig hierfür sind Hanf-Normalformen. Es wird gezeigt, dass eine Erweiterung von FO durch unäre Zählquantoren genau dann Hanf-Normalformen erlaubt, wenn alle Zählquantoren ultimativ periodisch sind, und wie Hanf-Normalformen in diesen Fällen in elementarer und worst-case optimaler Zeit konstruiert werden können. Dies führt zu Model-Checking Algorithmen für solche Erweiterungen von FO sowie zu Verallgemeinerungen der Algorithmen für Feferman-Vaught-Zerlegungen und die Erhaltungssätze von Lyndon, Łoś und Tarski. / Normal forms express semantic properties of logics by means of syntactical restrictions. They allow algorithms to benefit from restrictions of the expressive power of a logic. An example is the locality of first-order logic (FO), which implies that properties like reachability or connectivity cannot be defined in FO. Gaifman's local normal form expresses the satisfaction conditions of an FO-formula by a Boolean combination of local statements. Gaifman normal form serves as a first step in fixed-parameter model-checking algorithms, parameterised by the size of the formula, on sparse graph classes. However, it is known that in general, there are non-elementary lower bounds for the costs involved in transforming a formula into Gaifman normal form. This leads to an enormous parameter-dependency of the aforementioned algorithms. Similar non-elementary lower bounds also hold for Feferman-Vaught decompositions and for the preservation theorems by Lyndon, Łoś, and Tarski. This thesis investigates the complexity of these normal forms when restricting attention to classes of structures of bounded degree, for which the non-elementary lower bounds are known to fail. Under this restriction, the thesis provides algorithms with elementary and even worst-case optimal running time for the construction of Gaifman normal form and Feferman-Vaught decompositions. For the preservation theorems, algorithmic versions with elementary running time and non-matching lower bounds are provided. Crucial for these results is the notion of Hanf normal form. It is shown that an extension of FO by unary counting quantifiers allows Hanf normal forms if, and only if, all quantifiers are ultimately periodic, and furthermore, how Hanf normal form can be computed in elementary and worst-case optimal time in these cases. This leads to model-checking algorithms for such extensions of FO and also allows generalisations of the constructions for Feferman-Vaught decompositions and preservation theorems.