<div>We further the research in o-minimal topology by studying in full generality definable topological spaces in o-minimal structures. These are topological spaces $(X, \tau)$, where $X$ is a definable set in an o-minimal structure and the topology $\tau$ has a basis that is (uniformly) definable. Examples include the canonical o-minimal "euclidean" topology, “definable spaces” in the sense of van den Dries [17], definable metric spaces [49], as well as generalizations of classical non-metrizable topological spaces such as the Split Interval and the Alexandrov Double Circle.</div><div><br></div><div>We develop a usable topological framework in our setting by introducing definable analogues of classical topological properties such as separability, compactness and metrizability. We characterize these notions, showing in particular that, whenever the underlying o-minimal structure expands $(\mathbb{R},<)$, definable separability and compactness are equivalent to their classical counterparts, and a similar weaker result for definable metrizability. We prove the equivalence of definable compactness and various other properties in terms of definable curves and types. We show that definable topological spaces in o-minimal expansions of ordered groups and fields have properties akin to first countability. Along the way we study o-minimal definable directed sets and types. We prove a density result for o-minimal types, and provide an elementary proof within o-minimality of a statement related to the known connection between dividing and definable types in o-minimal theories.</div><div><br></div><div>We prove classification and universality results for one-dimensional definable topological spaces, showing that these can be largely described in terms of a few canonical examples. We derive in particular that the three element basis conjecture of Gruenhage [25] holds for all infinite Hausdorff definable topological spaces in o-minimal structures expanding $(\mathbb{R},<)$, i.e. any such space has a definable copy of an interval with the euclidean, discrete or lower limit topology.</div><div><br></div><div>A definable topological space is affine if it is definably homeomorphic to a euclidean space. We prove affineness results in o-minimal expansions of ordered fields. This includes a result for Hausdorff one-dimensional definable topological spaces. We give two new proofs of an affineness theorem of Walsberg [49] for definable metric spaces. We also prove an affineness result for definable topological spaces of any dimension that are Tychonoff in a definable</div><div>sense, and derive that a large class of locally affine definable topological spaces are affine.</div>

<p>This work strengthens and extends an algorithm for computing Betti numbers of symmetric semialgebraic sets developed by Basu and Riener in, <em>Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-Algebraic Sets</em>. We first adapt a construction of Gabrielov and Vorobjov in, <em>Approximation of Definable Sets by Compact Families, and Upper Bounds on Homotopy and Homology,</em> for replacing arbitrary definable sets by compact ones to the symmetric case. The original construction provided maps from the homotopy and homology groups of the replacement set to those of the original; we show that for sets symmetric relative to the action of some finite reflection group <em>G</em>, we may construct these maps to be equivariant. This modification to the construction for compact replacement allows us to extend Basu and Riener's theorem on which submodules appear in the isotypic decomposition of each cohomology space to sets not necessarily closed and bounded. Furthermore, by utilizing this equivariant compact approximation, we may obtain a precise description of the aforementioned decomposition of each cohomology space, and not merely the final dimension of the space, from Basu and Riener's algorithm.</p> <p><br></p> <p>    Though our equivariant compact replacement holds for <em>G</em> any finite reflection group, Basu and Riener's results only consider the case of the action the of symmetric group, sometimes termed type <em>A</em>. As a first step towards generalizing Basu and Riener's work, we examine the next major class of symmetry: the action of the group of signed permutations (known as type <em>B</em>). We focus our attention on Vandermonde varieties, a key object in Basu and Riener's proofs. We show that the intersection of a type <em>B</em> Vandermonde variety with a fundamental region of type <em>B</em> symmetry is topologically regular. We also prove a result about the intersection of a type <em>B</em> Vandermonde variety with the walls of this fundamental region, leading to the elimination of factors in a different decomposition of the homology spaces.</p>

No description available.

In this thesis we present a framework for automatic formal analysis of competitive stochastic systems, such as sensor networks, decentralised resource management schemes or distributed user-centric environments. We model such systems as stochastic multi-player games, which are turn-based models where an action in each state is chosen by one of the players or according to a probability distribution. The specifications, such as “sensors 1 and 2 can collaborate to detect the target with probability 1, no matter what other sensors in the network do” or “the controller can ensure that the energy used is less than 75 mJ, and the algorithm terminates with probability at least 0.5'', are provided as temporal logic formulae. We introduce a branching-time temporal logic rPATL and its multi-objective extension to specify such probabilistic and reward-based properties of stochastic multi-player games. We also provide algorithms for these logics that can either verify such properties against the model, providing a yes/no answer, or perform strategy synthesis by constructing the strategy for the players that satisfies the specification. We conduct a detailed complexity analysis of the model checking problem for rPATL and its multi-objective extension and provide efficient algorithms for verification and strategy synthesis. We also implement the proposed techniques in the PRISM-games tool and apply them to the analysis of several case studies of competitive stochastic systems.

In this thesis we study a reasoning module for agents that have cognitive abilities, such as memory, perception, action, and are expected to function autonomously for long periods of time. The module provides the ability to reason about action and change using the language of the situation calculus and variants of the basic action theories. The main focus of this thesis is on the logical problem of progressing an action theory. First, we investigate the conjecture by Lin and Reiter that a practical first-order definition of progression is not appropriate for the general case. We show that Lin and Reiter were indeed correct in their intuitions by providing a proof for the conjecture, thus resolving the open question about the first-order definability of progression and justifying the need for a second-order definition. Then we proceed to identify three cases where it is possible to obtain a first-order progression with the desired properties: i) we extend earlier work by Lin and Reiter and present a case where we restrict our attention to a practical class of queries that may only quantify over situations in a limited way; ii) we revisit the local-effect assumption of Liu and Levesque that requires that the effects of an action are fixed by the arguments of the action and show that in this case a first-order progression is suitable; iii) we investigate a way that the local-effect assumption can be relaxed and show that when the initial knowledge base is a database of possible closures and the effects of the actions are range-restricted then a first-order progression is also suitable under a just-in-time assumption. Finally, we examine a special case of the action theories with range-restricted effects and present an algorithm for computing a finite progression. We prove the correctness and the complexity of the algorithm, and show its application in a simple example that is inspired by video games.

Answer set programming (ASP) is a declarative approach to solving search problems. Logic programming constitutes the foundation of ASP. ASP is not a proof-theoretical approach where you get solutions by answer substitutions. Instead, the problem is represented by a logic program in such a way that models of the program according to the answer set semantics correspond to solutions of the problem. Answer set solvers (Smodels, Cmodels, Clasp, and Dlv) are used for finding answer sets of a given program. Although users can write programs with variables for convenience, current answer set solvers work on ground logic programs where there are no variables. The grounding step of ASP generates a propositional instance of a logic program with variables. It may generate a huge propositional instance and make the search process of answer set solvers more difficult. Model generation theorem provers (Paradox, Darwin, and FM-Darwin) have the capability of producing a model when the first-order input theory is satisfiable. This work proposes the use of model generation theorem provers as computational engines for ASP. The main motivation is to eliminate the grounding step of ASP completely or to perform it more intelligently using the model generation system. Additionally, regardless of grounding, model generation systems may display better performance than the current solvers. The proposed method can be seen as lifting SAT-based ASP, where SAT solvers are used to compute answer sets, to the first-order level for tight programs. A completion procedure which transforms a logic program to formulas of first-order logic is utilized. Besides completion, other transformations which are necessary for forming a firstorder theory suitable for model generation theorem provers are investigated. A system called Completor is implemented for handling all the necessary transformations. The empirical results demonstrate that the use of Completor and the theorem provers together can be an eective way of computing answer sets. Especially, the run time results of Paradox in the experiments has showed that using Completor and Paradox together is favorable compared to answer set solvers. This advantage has been more clearly observed for programs with large propositional instances, since grounding can be a bottleneck for such programs.

In this thesis we study a reasoning module for agents that have cognitive abilities, such as memory, perception, action, and are expected to function autonomously for long periods of time. The module provides the ability to reason about action and change using the language of the situation calculus and variants of the basic action theories. The main focus of this thesis is on the logical problem of progressing an action theory. First, we investigate the conjecture by Lin and Reiter that a practical first-order definition of progression is not appropriate for the general case. We show that Lin and Reiter were indeed correct in their intuitions by providing a proof for the conjecture, thus resolving the open question about the first-order definability of progression and justifying the need for a second-order definition. Then we proceed to identify three cases where it is possible to obtain a first-order progression with the desired properties: i) we extend earlier work by Lin and Reiter and present a case where we restrict our attention to a practical class of queries that may only quantify over situations in a limited way; ii) we revisit the local-effect assumption of Liu and Levesque that requires that the effects of an action are fixed by the arguments of the action and show that in this case a first-order progression is suitable; iii) we investigate a way that the local-effect assumption can be relaxed and show that when the initial knowledge base is a database of possible closures and the effects of the actions are range-restricted then a first-order progression is also suitable under a just-in-time assumption. Finally, we examine a special case of the action theories with range-restricted effects and present an algorithm for computing a finite progression. We prove the correctness and the complexity of the algorithm, and show its application in a simple example that is inspired by video games.

A critical set in a Latin square of order n is a set of entries in an n x n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n2-n. In Chapter 4, it is shown that lcs(n)<=n2-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders mX2^alpha (m odd, alpha>=2) and mX2^alpha+1 (m odd, alpha>=2 and alpha not equal to 3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n2 divided by 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n x n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n2-n. In Chapter 4, it is shown that lcs(n)<=n2-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders mX2^alpha (m odd, alpha>=2) and mX2^alpha+1 (m odd, alpha>=2 and alpha not equal to 3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n2 divided by 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

Orientador: Marcelo Esteban Coniglio / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-04T20:57:48Z (GMT). No. of bitstreams: 1 Fernandez_VictorLeandro_D.pdf: 6531217 bytes, checksum: 2a972c9e9fa860af8f9cc57b3e1bb73d (MD5) Previous issue date: 2005 / Resumo: Neste trabalho investigamos com um enfoque abstrato um processo de combinações de lógicas conhecido como Fibrilação de lógicas. Em particular estudamos a transferência, mediante fibrilação, de certas propriedades intrínsecas às lógicas proposicionais. As noções mencionadas são as de protoalgebrizabilidade, equivalencialidade e algebrizabilidade. Ditas noções fazem parte da "Hierarquia de Leibniz" , conceito fundamental da chamada Lógica Algébrica Abstrata. Tal hierarquia classifica as diferentes lógicas segundo o seu grau de algebrizabilidade. Assim, nesta tese estudaremos se, quando duas lógicas possuem alguma dessas propriedades, a fibrilação delas possui também tal característica. Com o objetivo de diferençar os diferentes modos de fibrilação existentes na literatura, analisamos duas maneiras de fibrilar lógicas: Fibrilação categorial (ou C-fibrilação) e Fibrilação no sentido de D. Gabbay (G-fibrilação). Também estudamos uma variante da Gfibrilação de lógicas conhecida como Fusão de lógicas. Assim, damos diferentes condições que devem valer para que a C-fibrilação de uma lógica protoalgébrica seja também protoalgébrica, e procedemos de forma similar com as outras propriedades que constituem a Hierarquia de Leibniz. No caso da G-fibrilação e da fusão de lógicas chegamos a diversos resultados análogos aos anteriores, os quais permitem ter uma visão geral da relação entre Lógica Algébrica Abstrata e as Combinações de lógicas / Abstract: ln this thesis we investigate, with an abstract approach, a process of combinations of logics known as fibring of logics. ln particular we study the transference by fibring of certain properties, intrinsic to propositionallogics: protoalgebricity, equivalenciality and algebraizability. The notions above belong to the "Leibniz Hierarchy", a fundamental concept of the so-called Abstract Algebraic Logic. Such hierarchy classifies the logics according to its algebraizability degree. So, in this thesis we will study whether, given two logics having some of these properties, the fibring of them still has that property. With the aim of distinguishing the different techniques of fibring existing in the literature, we analyze two methods of fibring logics: Categorial Fibring (or C-fibring) and Fibring in D. Gabbay's sense (G-fibring). We also study a variant of G-fibring known as fusion of logics. So, we give different conditions that must hold in order to obtain a protoalgebraic logic by means of C-fibring of protoalgebric logics. We proceed in a similar way with the other properties that constitutes the Leibniz Hierarchy. With respect to G-fibring and fusion, we arrive to similar results which allow us to get an overview of the relation between Abstract AIgebraic Logic and the subject of combinations of logics / Doutorado / Doutor em Filosofia