Formal studies of models of concurrency are usually focused on two major models: Interleaving abstraction (Bergstra, 2001; Milner, 1990) and partially ordered causality (Diekert and Rozenberg, 1995; Jensen, 1997; Reisig, 1998). Although very mature, these models retain a known limitation: Neither of them can model the “not later than” relationship effectively, which causes problems with specifying priorities, error recovery, time testing, inhibitor nets, etc. See for reference: Best and Koutny (1992); Janicki (2008); Janicki and Koutny (1995); Juhas et al. (2006); Kleijn and Koutny (2004). A solution, proposed independently (in this order) in (Lamport, 1986; Gaifman and Pratt, 1987) and (Janicki and Koutny, 1991), suggests to model concurrent behaviours by an ordered structure, i.e. a triple (X, R1, R2), where X is the set of event occurrences, and R1 and R2 are two binary relations on X. The relation R1 is interpreted as “causality”, i.e. an abstraction of the “earlier than” relationship, and R2 is interpreted as “weak causality”, an abstraction of the “not later than” relationship. For ordered structures’ model, the following two kinds of relational structures are of special importance: stratified order structures (SO-structures) and interval order structures (IO-structures). The SO-structures can fully model concurrent behaviours when system executions (operational semantics) are described in terms of stratified orders, while the IO-structures can fully model concurrent behaviours when system executions are described in terms of interval orders (Janicki, 2008; Janicki and Koutny, 1997). It was argued in (Janicki and Koutny, 1993), and also implicitly in a 1914 Wiener’s paper Wiener (1914), that any execution that can be observed by a single observer must be an interval order. Thus, IO-structures provide a very definitive model of concurrency. However, the theory of IO-structures remains far less developed than its simpler counterpart - the theory of SO-structures. One of the most important concepts lying at the core of partial orders and algebraic structures theory is the concept of transitive closure of relations. The equivalent of transitive closure for SO-structures, called <>-closure, has been proposed in (Janicki and Koutny, 1995) and consequently used in (Janicki and Koutny, 1995; Juhas et al., 2006; Kleijn and Koutny, 2004) and others. However, a similar concept for IO-structures has not been proposed. In this thesis we define that concept. We introduce the transitive closure for IO-structures, called the []-closure. We prove that it has same properties as the standard transitive closure for partial orders and []-closure for SO-structures (published in Janicki and Zubkova (2009); Janicki et al. (2009)), and provide some comparison of different versions of transitive closure used in various relational structures. Some properties of another recently introduced *-closure (Janicki et al., 2013) are also discussed. / Thesis / Master of Science (MSc)

In this thesis, we develop a relational localisation theory for topological algebras, i.e., a theory that studies local approximations of a topological algebra’s relational counterpart. In order to provide an appropriate framework for our considerations, we first introduce a general Galois theory between continuous functions and closed relations on an arbitrary topological space. Subsequently to this rather foundational discussion, we establish the desired localisation theory comprising the identification of suitable subsets, the description of local structures, and the retrieval of global information from local data. Among other results, we show that the restriction process with respect to a sufficiently large collection of local approximations of a Hausdorff topological algebra extends to a categorical equivalence between the topological quasivariety generated by the examined structure and the one generated by its localisation. Furthermore, we present methods for exploring topological algebras possessing certain operational compactness properties. Finally, we explain the developed concepts and obtained results in the particular context of three important classes of topological algebras by analysing the local structure of essentially unary topological algebras, topological lattices, and topological modules of compact Hausdorff topological rings.

In this thesis, we develop a relational localisation theory for topological algebras, i.e., a theory that studies local approximations of a topological algebra’s relational counterpart. In order to provide an appropriate framework for our considerations, we first introduce a general Galois theory between continuous functions and closed relations on an arbitrary topological space. Subsequently to this rather foundational discussion, we establish the desired localisation theory comprising the identification of suitable subsets, the description of local structures, and the retrieval of global information from local data. Among other results, we show that the restriction process with respect to a sufficiently large collection of local approximations of a Hausdorff topological algebra extends to a categorical equivalence between the topological quasivariety generated by the examined structure and the one generated by its localisation. Furthermore, we present methods for exploring topological algebras possessing certain operational compactness properties. Finally, we explain the developed concepts and obtained results in the particular context of three important classes of topological algebras by analysing the local structure of essentially unary topological algebras, topological lattices, and topological modules of compact Hausdorff topological rings.

Made available in DSpace on 2016-04-27T17:27:13Z (GMT). No. of bitstreams: 1 Carlos Roberto Teixeira Alves.pdf: 1331347 bytes, checksum: cebe03a83120937101a3595710844df2 (MD5) Previous issue date: 2015-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work aims to show the current treatment of the semantic notion of satisfiability to the logic of the first order, the relevant problems of Tarski's solution to define this notion - in this case, the use of infinite sequences to satisfy the formulas - and propose an alternative to circumvent this problem. The notion established by Tarski became, in discussions on the subject, standard solution and resulted in rich tools to work with the languages, in particular tools such as the Theory of Models. However, from a philosophical point of view, it is very important to broaden perspectives and look at the problem from a new dimension. Our proposal is to avoid the counterintuitive idea of using infinite sequences of objects to satisfy the finite formulas, knowing that these infinite sequences are composed almost entirely of 'superfluous terms', expendable in the process of satisfaction, but they should and are listed and indexed in the process. It would be interesting to solve the issue involving sequences without 'superfluous terms'. We propose a structure of first-order language that dispenses variables and constants. The notion of satisfaction in this case is distinct, which increases the possibilities and provides an alternative to the satisfaction of infinite sequences. In the end, we show how our solution can produce the satisfaction of formulas of a first-order language within a framework where satisfaction is interpreted according to certain specific criteria and can be performed by finite sequences, differing essentially from Tarski solution / Este trabalho tem por objetivo mostrar o tratamento atual da noção semântica de satisfatibilidade para as lógicas de primeira ordem, os problemas relevantes da solução de Tarski para definir essa noção no caso, o uso de sequências infinitas para a satisfação das fórmulas , e propor uma alternativa que contorne esse problema. A noção estabelecida por Tarski tornou-se, nas discussões a respeito do tema, a solução padrão e resultou em ferramentas ricas para operar com as linguagens, em especial ferramentas como a Teoria dos Modelos. No entanto, de um ponto de vista filosófico, é sadio ampliar as perspectivas e olhar o problema sob uma dimensão nova. Nossa proposta é superar a ideia contraintuitiva de elencarmos sequências infinitas de objetos para satisfação das formulas finitas, sabendo que essas sequências infinitas são compostas quase que totalmente de termos supérfluos , dispensáveis no processo de satisfação, mas que devem e são enumerados e indexados no processo. Seria interessante solucionar a questão envolvendo sequências sem termos supérfluos . Proporemos uma estrutura de linguagem de primeira ordem que dispensa variáveis e constantes. A noção de satisfação nesse caso é distinta, o que amplia as possibilidades e fornece uma alternativa à satisfação por sequências infinitas. No fim, mostraremos como nossa solução consegue produzir a satisfação de fórmulas de uma linguagem de primeira ordem dentro de uma estrutura interpretada onde a satisfação ocorre segundo certos critérios específicos e consegue ser realizada por sequências finitas, diferindo essencialmente da solução de Tarski

This work analyses properties of relational structures that imply a high degree of symmetry. A structure is called homogeneous if every mapping from any finite substructure can be extended to a mapping over the whole structure. The various types of these mappings determine corresponding types of homogeneity. A prominent position belongs to ultrahomogeneity, for which every local isomorphism can be extended to an automorphism. In contrast to graphs, the classification of ultrahomogeneous relational struc- tures is still an open problem. The task of this work is to characterize "the distance" to homogeneity using two approaches. Firstly, the classification of homogeneous structures is studied when the "complexity" of a structure is increased by introducing more relations. This leads to various classifications of homomorphism-homogeneous L-colored graphs for different L, where L- colored graphs are graphs having sets of colors from a partially ordered set L assigned to vertices and edges. Moreover a hierarchy of classes of ho- mogeneous structures defined via types of homogeneity is studied from the viewpoint of classes coincidence. The second approach analyses for fixed classes of structures the least way to extend their language so as to achieve homogeneity. We obtain results about relational complexity for finite...

This thesis extends a localisation theory for finite algebras to certain classes of infinite structures. Based on ideas and constructions originally stemming from Tame Congruence Theory, algebras are studied via local restrictions of their relational counterpart (Relational Structure Theory). In this respect, first those subsets are identified that are suitable for such a localisation process, i. e. that are compatible with the relational clone structure of the counterpart of an algebra. It is then studied which properties of the global algebra can be transferred to its localisations, called neighbourhoods. Thereafter, it is discussed how this process can be reversed, leading to the concept of covers. These are collections of neighbourhoods that allow information retrieval about the global structure from knowledge about the local restrictions. Subsequently, covers are characterised in terms of a decomposition equation, and connections to categorical equivalences of algebras are explored. In the second half of the thesis, a refinement concept for covers is introduced in order to find optimal, non-refinable covers, eventually leading to practical algorithms for their determination. Finally, the text establishes further theoretical foundations, e. g. several irreducibility notions, in order to ensure existence of non-refinable covers via an intrinsic characterisation, and to prove under some conditions that they are uniquely determined in a canonical sense. At last, the applicability of the developed techniques is demonstrated using two clear expository examples. / Diese Dissertation erweitert eine Lokalisierungstheorie für endliche Algebren auf gewisse Klassen unendlicher Strukturen. Basierend auf Ideen und Konstruktionen, die ursprünglich der Tame Congruence Theory entstammen, werden Algebren über lokale Einschränkungen ihres relationalen Gegenstücks untersucht (Relationale Strukturtheorie). In diesem Zusammenhang werden zunächst diejenigen Teilmengen identifiziert, welche für einen solchen Lokalisierungsprozeß geeignet sind, d. h., die mit der Relationenklonstruktur auf dem Gegenstück einer Algebra kompatibel sind. Es wird dann untersucht, welche Eigenschaften der globalen Algebra auf ihre Lokalisierungen, genannt Umgebungen, übertragen werden können. Nachfolgend wird diskutiert, wie dieser Vorgang umgekehrt werden kann, was zum Begriff der Überdeckungen führt. Dies sind Systeme von Umgebungen, welche die Rückgewinnung von Informationen über die globale Struktur aus Kenntnis ihrer lokalen Einschränkungen erlauben. Sodann werden Überdeckungen durch eine Zerlegungsgleichung charakterisiert und Bezüge zu kategoriellen Äquivalenzen von Algebren hergestellt. In der zweiten Hälfte der Arbeit wird ein Verfeinerungsbegriff für Überdeckungen eingeführt, um optimale, nichtverfeinerbare Überdeckungen zu finden, was letztlich zu praktischen Algorithmen zu ihrer Bestimmung führt. Schließlich erarbeitet der Text weitere theoretische Grundlagen, beispielsweise mehrere Irreduzibilitätsbegriffe, um die Existenz nichtverfeinerbarer Überdeckungen vermöge einer intrinsischen Charakterisierung sicherzustellen und, unter gewissen Bedingungen, zu beweisen, daß sie in kanonischer Weise eindeutig bestimmt sind. Schlußendlich wird die Anwendbarkeit der entwickelten Methoden an zwei übersichtlichen Beispielen demonstriert.

This thesis extends a localisation theory for finite algebras to certain classes of infinite structures. Based on ideas and constructions originally stemming from Tame Congruence Theory, algebras are studied via local restrictions of their relational counterpart (Relational Structure Theory). In this respect, first those subsets are identified that are suitable for such a localisation process, i. e. that are compatible with the relational clone structure of the counterpart of an algebra. It is then studied which properties of the global algebra can be transferred to its localisations, called neighbourhoods. Thereafter, it is discussed how this process can be reversed, leading to the concept of covers. These are collections of neighbourhoods that allow information retrieval about the global structure from knowledge about the local restrictions. Subsequently, covers are characterised in terms of a decomposition equation, and connections to categorical equivalences of algebras are explored. In the second half of the thesis, a refinement concept for covers is introduced in order to find optimal, non-refinable covers, eventually leading to practical algorithms for their determination. Finally, the text establishes further theoretical foundations, e. g. several irreducibility notions, in order to ensure existence of non-refinable covers via an intrinsic characterisation, and to prove under some conditions that they are uniquely determined in a canonical sense. At last, the applicability of the developed techniques is demonstrated using two clear expository examples.:1 Introduction 2 Preliminaries and Notation 2.1 Functions, operations and relations 2.2 Algebras and relational structures 2.3 Clones 3 Relational Structure Theory 3.1 Finding suitable subsets for localisation 3.2 Neighbourhoods 3.3 The restricted algebra A|U 3.4 Covers 3.5 Refinement 3.6 Irreducibility notions 3.7 Intrinsic description of non-refinable covers 3.8 Elaborated example 4 Problems and Prospects for Future Research Acknowledgements Index of Notation Index of Terms Bibliography / Diese Dissertation erweitert eine Lokalisierungstheorie für endliche Algebren auf gewisse Klassen unendlicher Strukturen. Basierend auf Ideen und Konstruktionen, die ursprünglich der Tame Congruence Theory entstammen, werden Algebren über lokale Einschränkungen ihres relationalen Gegenstücks untersucht (Relationale Strukturtheorie). In diesem Zusammenhang werden zunächst diejenigen Teilmengen identifiziert, welche für einen solchen Lokalisierungsprozeß geeignet sind, d. h., die mit der Relationenklonstruktur auf dem Gegenstück einer Algebra kompatibel sind. Es wird dann untersucht, welche Eigenschaften der globalen Algebra auf ihre Lokalisierungen, genannt Umgebungen, übertragen werden können. Nachfolgend wird diskutiert, wie dieser Vorgang umgekehrt werden kann, was zum Begriff der Überdeckungen führt. Dies sind Systeme von Umgebungen, welche die Rückgewinnung von Informationen über die globale Struktur aus Kenntnis ihrer lokalen Einschränkungen erlauben. Sodann werden Überdeckungen durch eine Zerlegungsgleichung charakterisiert und Bezüge zu kategoriellen Äquivalenzen von Algebren hergestellt. In der zweiten Hälfte der Arbeit wird ein Verfeinerungsbegriff für Überdeckungen eingeführt, um optimale, nichtverfeinerbare Überdeckungen zu finden, was letztlich zu praktischen Algorithmen zu ihrer Bestimmung führt. Schließlich erarbeitet der Text weitere theoretische Grundlagen, beispielsweise mehrere Irreduzibilitätsbegriffe, um die Existenz nichtverfeinerbarer Überdeckungen vermöge einer intrinsischen Charakterisierung sicherzustellen und, unter gewissen Bedingungen, zu beweisen, daß sie in kanonischer Weise eindeutig bestimmt sind. Schlußendlich wird die Anwendbarkeit der entwickelten Methoden an zwei übersichtlichen Beispielen demonstriert.:1 Introduction 2 Preliminaries and Notation 2.1 Functions, operations and relations 2.2 Algebras and relational structures 2.3 Clones 3 Relational Structure Theory 3.1 Finding suitable subsets for localisation 3.2 Neighbourhoods 3.3 The restricted algebra A|U 3.4 Covers 3.5 Refinement 3.6 Irreducibility notions 3.7 Intrinsic description of non-refinable covers 3.8 Elaborated example 4 Problems and Prospects for Future Research Acknowledgements Index of Notation Index of Terms Bibliography