Sized Type Analysis for Logic Programs (Technical Communication)

We present a novel analysis for relating the sizes of terms and subterms occurring at diferent argument positions in logic predicates. We extend and enrich the concept of sized type as a representation that incorporates structural (shape) information and allows expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. For example, expressing bounds on the length of lists of numbers, together with bounds on the values of all of their elements. The analysis is developed using abstract interpretation and the novel abstract operations are based on setting up and solving recurrence relations between sized types. It has been integrated, together with novel resource usage and cardinality analyses, in the abstract interpretation framework in the Ciao preprocessor, CiaoPP, in order to assess both the accuracy of the new size analysis and its usefulness in the resource usage estimation application. We show that the proposed sized types are a substantial improvement over the previous size analyses present in CiaoPP, and also benefit the resource analysis considerably, allowing the inference of equal or better bounds than comparable state of the art systems.

Modelado y Comparación de Colecciones en la Web Semántica

En esta tesis se estudia la representación, modelado y comparación de colecciones mediante el uso de ontologías en el ámbito de la Web Semántica. Las colecciones, entendidas como agrupaciones de objetos o elementos con entidad propia, son construcciones que aparecen frecuentemente en prácticamente todos los dominios del mundo real, y por tanto, es imprescindible disponer de conceptualizaciones de estas estructuras abstractas y de representaciones de estas conceptualizaciones en los sistemas informáticos, que definan adecuadamente su semántica. Mientras que en muchos ámbitos de la Informática y la Inteligencia Artificial, como por ejemplo la programación, las bases de datos o la recuperación de información, las colecciones han sido ampliamente estudiadas y se han desarrollado representaciones que responden a multitud de conceptualizaciones, en el ámbito de la Web Semántica, sin embargo, su estudio ha sido bastante limitado. De hecho hasta la fecha existen pocas propuestas de representación de colecciones mediante ontologías, y las que hay sólo cubren algunos tipos de colecciones y presentan importantes limitaciones. Esto impide la representación adecuada de colecciones y dificulta otras tareas comunes como la comparación de colecciones, algo crítico en operaciones habituales como las búsquedas semánticas o el enlazado de datos en la Web Semántica. Para solventar este problema esta tesis hace una propuesta de modelización de colecciones basada en una nueva clasificación de colecciones de acuerdo a sus características estructurales (homogeneidad, unicidad, orden y cardinalidad). Esta clasificación permite definir una taxonomía con hasta 16 tipos de colecciones distintas. Entre otras ventajas, esta nueva clasificación permite aprovechar la semántica de las propiedades estructurales de cada tipo de colección para realizar comparaciones utilizando las funciones de similitud y disimilitud más apropiadas. De este modo, la tesis desarrolla además un nuevo catálogo de funciones de similitud para las distintas colecciones, donde se han recogido las funciones de (di)similitud más conocidas y también algunas nuevas. Esta propuesta se ha implementado mediante dos ontologías paralelas, la ontología E-Collections, que representa los distintos tipos de colecciones de la taxonomía y su axiomática, y la ontología SIMEON (Similarity Measures Ontology) que representa los tipos de funciones de (di)similitud para cada tipo de colección. Gracias a estas ontologías, para comparar dos colecciones, una vez representadas como instancias de la clase más apropiada de la ontología E-Collections, automáticamente se sabe qué funciones de (di)similitud de la ontología SIMEON pueden utilizarse para su comparación. Abstract This thesis studies the representation, modeling and comparison of collections in the Semantic Web using ontologies. Collections, understood as groups of objects or elements with their own identities, are constructions that appear frequently in almost all areas of the real world. Therefore, it is essential to have conceptualizations of these abstract structures and representations of these conceptualizations in computer systems, that define their semantic properly. While in many areas of Computer Science and Artificial Intelligence, such as Programming, Databases or Information Retrieval, the collections have been extensively studied and there are representations that match many conceptualizations, in the field Semantic Web, however, their study has been quite limited. In fact, there are few representations of collections using ontologies so far, and they only cover some types of collections and have important limitations. This hinders a proper representation of collections and other common tasks like comparing collections, something critical in usual operations such as semantic search or linking data on the Semantic Web. To solve this problem this thesis makes a proposal for modelling collections based on a new classification of collections according to their structural characteristics (homogeneity, uniqueness, order and cardinality). This classification allows to define a taxonomy with up to 16 different types of collections. Among other advantages, this new classification can leverage the semantics of the structural properties of each type of collection to make comparisons using the most appropriate (dis)similarity functions. Thus, the thesis also develops a new catalog of similarity functions for the different types of collections. This catalog contains the most common (dis)similarity functions as well as new ones. This proposal is implemented through two parallel ontologies, the E-Collections ontology that represents the different types of collections in the taxonomy and their axiomatic, and the SIMEON ontology (Similarity Measures Ontology) that represents the types of (dis)similarity functions for each type of collection. Thanks to these ontologies, to compare two collections, once represented as instances of the appropriate class of E-Collections ontology, we can know automatically which (dis)similarity functions of the SIMEON ontology are suitable for the comparison. Finally, the feasibility and usefulness of this modeling and comparison of collections proposal is proved in the field of oenology, applying both E-Collections and SIMEON ontologies to the representation and comparison of wines with the E-Baco ontology.

On the stability of Voronoi cells

Let T be a given subset of ℝ n , whose elements are called sites, and let s∈T. The Voronoi cell of s with respect to T consists of all points closer to s than to any other site. In many real applications, the position of some elements of T is uncertain due to either random external causes or to measurement errors. In this paper we analyze the effect on the Voronoi cell of small changes in s or in a given non-empty set P⊂T\{s}. Two types of perturbations of P are considered, one of them not increasing the cardinality of T. More in detail, the paper provides conditions for the corresponding Voronoi cell mappings to be closed, lower and upper semicontinuous. All the involved conditions are expressed in terms of the data.

Étude de l’orientation cardinale sud dans les sépultures mayas de la Période Classique

Ce mémoire porte sur l’étude de l’orientation des sépultures mayas de la Période Classique (250 - 900/1000 de notre ère). Il s’agit d’une recherche visant à comprendre le choix d’une orientation sud des défunts dans la vallée du Belize et ses environs. L’intérêt porté à cette région vient du fait que l’orientation sud des défunts est un phénomène que l’on retrouve rarement sur le territoire maya, sauf à cet endroit. Alors que la présence de la cardinalité en lien avec la cosmovision maya est attestée dans l’architecture, le plan des sites, la forme et la fonction des divinités, dans l’agriculture, etc., il est plutôt rare qu’elle soit analysée dans les études du traitement funéraire. Ainsi, le but de cette recherche est de saisir l’ampleur de la pratique de l’orientation sud des défunts sur le territoire maya, de comprendre son origine et sa ou ses possible(s) signification(s). Les données des sépultures de la Période Classique de cinq sites de la vallée du Belize (Baking Pot, Barton Ramie, Blackman Eddy, Cahal Pech et Xunantunich), de quatre sites du Plateau Vaca (Minanha, Pacbitun, Mountain Cow et Caracol) et de trois sites situés à l’ouest (Holmul) et au nord (San José et Altun Ha) de ces deux régions sont compilées. Les résultats révèlent que le coeur de cette pratique se trouve dans la vallée du Belize, bien qu’une orientation sud des défunts ait été retrouvée partout. Cette pratique semble apparaitre à la fin de la Période Préclassique et les analyses ne révèlent pas de lien entre l’orientation sud et certaines variables (âge, sexe, position du défunt). Finalement, on arrive à la conclusion qu’il est possible que cette orientation sud des défunts soit en lien avec le passage des défunts dans l’inframonde et que cela forme un choix culturel local en lien avec le statut et l’identité du défunt.

Explora: A Visualisation Tool for Metric Analysis of Software Corpora

When analysing software metrics, users find that visualisation tools lack support for (1) the detection of patterns within metrics; and (2) enabling analysis of software corpora. In this paper we present Explora, a visualisation tool designed for the simultaneous analysis of multiple metrics of systems in software corpora. Explora incorporates a novel lightweight visualisation technique called PolyGrid that promotes the detection of graphical patterns. We present an example where we analyse the relation of subtype polymorphism with inheritance and invocation in corpora of Smalltalk and Java systems and find that (1) subtype polymorphism is more likely to be found in large hierarchies; (2) as class hierarchies grow horizontally, they also do so vertically; and (3) in polymorphic hierarchies the length of the name of the classes is orthogonal to the cardinality of the call sites.

Étude de l’orientation cardinale sud dans les sépultures mayas de la Période Classique

Ce mémoire porte sur l’étude de l’orientation des sépultures mayas de la Période Classique (250 - 900/1000 de notre ère). Il s’agit d’une recherche visant à comprendre le choix d’une orientation sud des défunts dans la vallée du Belize et ses environs. L’intérêt porté à cette région vient du fait que l’orientation sud des défunts est un phénomène que l’on retrouve rarement sur le territoire maya, sauf à cet endroit. Alors que la présence de la cardinalité en lien avec la cosmovision maya est attestée dans l’architecture, le plan des sites, la forme et la fonction des divinités, dans l’agriculture, etc., il est plutôt rare qu’elle soit analysée dans les études du traitement funéraire. Ainsi, le but de cette recherche est de saisir l’ampleur de la pratique de l’orientation sud des défunts sur le territoire maya, de comprendre son origine et sa ou ses possible(s) signification(s). Les données des sépultures de la Période Classique de cinq sites de la vallée du Belize (Baking Pot, Barton Ramie, Blackman Eddy, Cahal Pech et Xunantunich), de quatre sites du Plateau Vaca (Minanha, Pacbitun, Mountain Cow et Caracol) et de trois sites situés à l’ouest (Holmul) et au nord (San José et Altun Ha) de ces deux régions sont compilées. Les résultats révèlent que le coeur de cette pratique se trouve dans la vallée du Belize, bien qu’une orientation sud des défunts ait été retrouvée partout. Cette pratique semble apparaitre à la fin de la Période Préclassique et les analyses ne révèlent pas de lien entre l’orientation sud et certaines variables (âge, sexe, position du défunt). Finalement, on arrive à la conclusion qu’il est possible que cette orientation sud des défunts soit en lien avec le passage des défunts dans l’inframonde et que cela forme un choix culturel local en lien avec le statut et l’identité du défunt.

Essays on the Analysis of Dynamic Games

Thesis (Ph.D.)--University of Washington, 2016-06

Optimization and Machine Learning Frameworks for Complex Network Analysis

Thesis (Ph.D.)--University of Washington, 2016-06

Identifiability and definiteness in Chinese

This article explores how the pragmatic notion of identfiability is encoded in Chinese. It presents a detailed analysis of the distinctive linguistic devices, including lexical, morphological, and position in sentence, which are employed in Chinese to indicate the interpretation of referents in respect of identifiability. Of the major determiners in Chinese, demonstratives are developing uses of a definite article, and yi 'one' + classier has developed uses of an indefinite article, although morphologically and in some cases also functionally they have not yet been fully grammaticalized. What makes Chinese further different from languages like English is the interpretation in this regard of what are called indeterminate lexical encodings, which include bare NPs and cardinality expressions. They by themselves are neutral in respect of the interpretation of identifiability. For indeterminate expressions, there is a strong but seldom absolute correlation between the interpretation of identiability or nonidentfiability and their occurrence in different positions in a sentence. Unlike the cases with several other languages without articles like Czech, Hindi, and Indonesian, the features of definiteness and indefiniteness cannot be obligatorily and uniquely specified for nominal expressions in Chinese. The findings in this article lead to the conclusion that definiteness as a grammatical category defined in the narrow sense has not been fully developed in Chinese.

Quality of service in flexible workflows through process constraints

Workflow technology has delivered effectively for a large class of business processes, providing the requisite control and monitoring functions. At the same time, this technology has been the target of much criticism due to its limited ability to cope with dynamically changing business conditions which require business processes to be adapted frequently, and/or its limited ability to model business processes which cannot be entirely predefined. Requirements indicate the need for generic solutions where a balance between process control and flexibility may be achieved. In this paper we present a framework that allows the workflow to execute on the basis of a partially specified model where the full specification of the model is made at runtime, and may be unique to each instance. This framework is based on the notion of process constraints. Where as process constraints may be specified for any aspect of the workflow, such as structural, temporal, etc. our focus in this paper is on a constraint which allows dynamic selection of activities for inclusion in a given instance. We call these cardinality constraints, and this paper will discuss their specification and validation requirements.

Near-ML detection for MDL-impaired few-mode fiber transmission

Few-mode fiber transmission systems are typically impaired by mode-dependent loss (MDL). In an MDL-impaired link, maximum-likelihood (ML) detection yields a significant advantage in system performance compared to linear equalizers, such as zero-forcing and minimum-mean square error equalizers. However, the computational effort of the ML detection increases exponentially with the number of modes and the cardinality of the constellation. We present two methods that allow for near-ML performance without being afflicted with the enormous computational complexity of ML detection: improved reduced-search ML detection and sphere decoding. Both algorithms are tested regarding their performance and computational complexity in simulations of three and six spatial modes with QPSK and 16QAM constellations.

On Multiple Deletion Codes

In 1965 Levenshtein introduced the deletion correcting codes and found an asymptotically optimal family of 1-deletion correcting codes. During the years there has been a little or no research on t-deletion correcting codes for larger values of t. In this paper, we consider the problem of finding the maximal cardinality L2(n;t) of a binary t-deletion correcting code of length n. We construct an infinite family of binary t-deletion correcting codes. By computer search, we construct t-deletion codes for t = 2;3;4;5 with lengths n ≤ 30. Some of these codes improve on earlier results by Hirschberg-Fereira and Swart-Fereira. Finally, we prove a recursive upper bound on L2(n;t) which is asymptotically worse than the best known bounds, but gives better estimates for small values of n.

CAPS in Z(2,n)

We consider point sets in (Z^2,n) where no three points are on a line – also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small n.

On Typical Compact Convex Sets in Hilbert Spaces

Let E be an infinite dimensional separable space and for e ∈ E and X a nonempty compact convex subset of E, let qX(e) be the metric antiprojection of e on X. Let n ≥ 2 be an arbitrary integer. It is shown that for a typical (in the sence of the Baire category) compact convex set X ⊂ E the metric antiprojection qX(e) has cardinality at least n for every e in a dense subset of E.

New Upper Bounds for Some Spherical Codes

The maximal cardinality of a code W on the unit sphere in n dimensions with (x, y) ≤ s whenever x, y ∈ W, x 6= y, is denoted by A(n, s). We use two methods for obtaining new upper bounds on A(n, s) for some values of n and s. We find new linear programming bounds by suitable polynomials of degrees which are higher than the degrees of the previously known good polynomials due to Levenshtein [11, 12]. Also we investigate the possibilities for attaining the Levenshtein bounds [11, 12]. In such cases we find the distance distributions of the corresponding feasible maximal spherical codes. Usually this leads to a contradiction showing that such codes do not exist.