Generating Relation Algebras for Qualitative Spatial Reasoning

Basic relationships between certain regions of space are formulated in natural language in everyday situations. For example, a customer specifies the outline of his future home to the architect by indicating which rooms should be close to each other. Qualitative spatial reasoning as an area of artificial intelligence tries to develop a theory of space based on similar notions. In formal ontology and in ontological computer science, mereotopology is a first-order theory, embodying mereological and topological concepts, of the relations among wholes, parts, parts of parts, and the boundaries between parts. We shall introduce abstract relation algebras and present their structural properties as well as their connection to algebras of binary relations. This will be followed by details of the expressiveness of algebras of relations for region based models. Mereotopology has been the main basis for most region based theories of space. Since its earliest inception many theories have been proposed for mereotopology in artificial intelligence among which Region Connection Calculus is most prominent. The expressiveness of the region connection calculus in relational logic is far greater than its original eight base relations might suggest. In the thesis we formulate ways to automatically generate representable relation algebras using spatial data based on region connection calculus. The generation of new algebras is a two pronged approach involving splitting of existing relations to form new algebras and refinement of such newly generated algebras. We present an implementation of a system for automating aforementioned steps and provide an effective and convenient interface to define new spatial relations and generate representable relational algebras.

Generating finite integral relation algebras

Relation algebras and categories of relations in particular have proven to be extremely useful as a fundamental tool in mathematics and computer science. Since relation algebras are Boolean algebras with some well-behaved operations, every such algebra provides an atom structure, i.e., a relational structure on its set of atoms. In the case of complete and atomic structure (e.g. finite algebras), the original algebra can be recovered from its atom structure by using the complex algebra construction. This gives a representation of relation algebras as the complex algebra of a certain relational structure. This property is of particular interest because storing the atom structure requires less space than the entire algebra. In this thesis I want to introduce and implement three structures representing atom structures of integral heterogeneous relation algebras, i.e., categorical versions of relation algebras. The first structure will simply embed a homogeneous atom structure of a relation algebra into the heterogeneous context. The second structure is obtained by splitting all symmetric idempotent relations. This new algebra is in almost all cases an heterogeneous structure having more objects than the original one. Finally, I will define two different union operations to combine two algebras into a single one.

ReAlM - a system to manipulate relations

Given a heterogeneous relation algebra R, it is well known that the algebra of matrices with coefficient from R is relation algebra with relational sums that is not necessarily finite. When a relational product exists or the point axiom is given, we can represent the relation algebra by concrete binary relations between sets, which means the algebra may be seen as an algebra of Boolean matrices. However, it is not possible to represent every relation algebra. It is well known that the smallest relation algebra that is not representable has only 16 elements. Such an algebra can not be put in a Boolean matrix form.[15] In [15, 16] it was shown that every relation algebra R with relational sums and sub-objects is equivalent to an algebra of matrices over a suitable basis. This basis is given by the integral objects of R, and is, compared to R, much smaller. Aim of my thesis is to develop a system called ReAlM - Relation Algebra Manipulator - that is capable of visualizing computations in arbitrary relation algebras using the matrix approach.

Extending relAPS to first order logic

RelAPS is an interactive system assisting in proving relation-algebraic theorems. The aim of the system is to provide an environment where a user can perform a relation-algebraic proof similar to doing it using pencil and paper. The previous version of RelAPS accepts only Horn-formulas. To extend the system to first order logic, we have defined and implemented a new language based on theory of allegories as well as a new calculus. The language has two different kinds of terms; object terms and relational terms, where object terms are built from object constant symbols and object variables, and relational terms from typed relational constant symbols, typed relational variables, typed operation symbols and the regular operations available in any allegory. The calculus is a mixture of natural deduction and the sequent calculus. It is formulated in a sequent style but with exactly one formula on the right-hand side. We have shown soundness and completeness of this new logic which verifies that the underlying proof system of RelAPS is working correctly.

RelMDD-A Library for Manipulating Relations Based on MDDs

Relation algebras is one of the state-of-the-art means used by mathematicians and computer scientists for solving very complex problems. As a result, a computer algebra system for relation algebras called RelView has been developed at Kiel University. RelView works within the standard model of relation algebras. On the other hand, relation algebras do have other models which may have different properties. For example, in the standard model we always have L;L=L (the composition of two (heterogeneous) universal relations yields a universal relation). This is not true in some non-standard models. Therefore, any example in RelView will always satisfy this property even though it is not true in general. On the other hand, it has been shown that every relation algebra with relational sums and subobjects can be seen as matrix algebra similar to the correspondence of binary relations between sets and Boolean matrices. The aim of my research is to develop a new system that works with both standard and non-standard models for arbitrary relations using multiple-valued decision diagrams (MDDs). This system will implement relations as matrix algebras. The proposed structure is a library written in C which can be imported by other languages such as Java or Haskell.

Region Connection Calculus: Composition Tables and Constraint Satisfaction Problems

Qualitative spatial reasoning (QSR) is an important field of AI that deals with qualitative aspects of spatial entities. Regions and their relationships are described in qualitative terms instead of numerical values. This approach models human based reasoning about such entities closer than other approaches. Any relationships between regions that we encounter in our daily life situations are normally formulated in natural language. For example, one can outline one's room plan to an expert by indicating which rooms should be connected to each other. Mereotopology as an area of QSR combines mereology, topology and algebraic methods. As mereotopology plays an important role in region based theories of space, our focus is on one of the most widely referenced formalisms for QSR, the region connection calculus (RCC). RCC is a first order theory based on a primitive connectedness relation, which is a binary symmetric relation satisfying some additional properties. By using this relation we can define a set of basic binary relations which have the property of being jointly exhaustive and pairwise disjoint (JEPD), which means that between any two spatial entities exactly one of the basic relations hold. Basic reasoning can now be done by using the composition operation on relations whose results are stored in a composition table. Relation algebras (RAs) have become a main entity for spatial reasoning in the area of QSR. These algebras are based on equational reasoning which can be used to derive further relations between regions in a certain situation. Any of those algebras describe the relation between regions up to a certain degree of detail. In this thesis we will use the method of splitting atoms in a RA in order to reproduce known algebras such as RCC15 and RCC25 systematically and to generate new algebras, and hence a more detailed description of regions, beyond RCC25.

Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

Nil graded self-similar algebras

In [19], [24] we introduced a family of self-similar nil Lie algebras L over fields of prime characteristic p > 0 whose properties resemble those of Grigorchuk and Gupta-Sidki groups. The Lie algebra L is generated by two derivations v(1) = partial derivative(1) + t(0)(p-1) (partial derivative(2) + t(1)(p-1) (partial derivative(3) + t(2)(p-1) (partial derivative(4) + t(3)(p-1) (partial derivative(5) + t(4)(p-1) (partial derivative(6) + ...))))), v(2) = partial derivative(2) + t(1)(p-1) (partial derivative(3) + t(2)(p-1) (partial derivative(4) + t(3)(p-1) (partial derivative(5) + t(4)(p-1) (partial derivative(6) + ...)))) of the truncated polynomial ring K[t(i), i is an element of N vertical bar t(j)(p) =0, i is an element of N] in countably many variables. The associative algebra A generated by v(1), v(2) is equipped with a natural Z circle plus Z-gradation. In this paper we show that for p, which is not representable as p = m(2) + m + 1, m is an element of Z, the algebra A is graded nil and can be represented as a sum of two locally nilpotent subalgebras. L. Bartholdi [3] andYa. S. Krylyuk [15] proved that for p = m(2) + m + 1 the algebra A is not graded nil. However, we show that the second family of self-similar Lie algebras introduced in [24] and their associative hulls are always Z(p)-graded, graded nil, and are sums of two locally nilpotent subalgebras.

Toda lattice field theories, discrete W algebras, Toda lattice hierarchies and quantum groups

In analogy with the Liouville case we study the sl3 Toda theory on the lattice and define the relevant quadratic algebra and out of it we recover the discrete W3 algebra. We define an integrable system with respect to the latter and establish the relation with the Toda lattice hierarchy. We compute the relevant continuum limits. Finally we find the quantum version of the quadratic algebra.

Unitary Operator Bases and Q-deformed Algebras

Starting from the Schwinger unitary operator bases formalism constructed out of a finite dimensional state space, the well-known q-deformed commutation relation is shown to emerge in a natural way, when the deformation parameter is a root of unity.

Higher algebras and mesonic spectrum in two-dimensional QCD

We construct composite operators in two-dimensional bosonized QCD, which obey a W∞ algebra, and discuss their relation to analogous objects recently obtained in the fermionic language. A complex algebraic structure is unravelled, supporting the idea that the model is integrable. For singlets we find a mass spectrum obeying the Regge behavior.

Perception Of Oral And Maxillofacial Surgeons, Orthodontists And Laypersons In Relation To The Harmony Of The Smile.

Harmony is one of the main objectives in surgical and orthodontic treatment and this harmony must be present in the smile, as well as in the face. The aim of the present study was to assess the perceptions of professionals and laypersons in relation to the harmony of the smile of patients with or without vertical maxillary alterations. Sixty observers (oral and maxillofacial surgeons, orthodontists and laypersons) reported the degree of harmony of six smiles using an objective questionnaire and the participants indicated if there was a need for corrective surgery or not. The classification of observers was recorded on a Likert scale from 1 to 5. Mixed regression was used to determine differences between the three groups. Statistically significant differences were found only for the harmony of the smile between the oral and maxillofacial surgeons and laypersons, with laypersons being more critical when assessing the smile. There was no statistical difference between the other groups for the harmony of the smile or the indication of corrective surgery. The patterns of greater or lesser harmony determined by observers during the smile were similar to those found in the literature as the ideal standard in relation to vertical maxillary positioning. Laypersons had a tendency to be more critical in relation to facial harmony than surgeons, although no statistical differences were found in the other groups in relation to the harmony of the smile or indication for the corrective surgery. In addition, the patterns of greater or lesser harmony of the smile determined by the participants were similar to those found in the literature as the ideal standard in relation to vertical maxillary positioning. Overall, the present study demonstrates that adequate interaction between surgeons, orthodontists and laypersons is essential in order to achieve facial harmony with orthodontic and/or surgical treatment. Opinion of specialists and laypersons about the smile in relation to the vertical positioning of the maxilla.

Prostatic Angiogenic Responses In Late Life: Antiangiogenic Therapy Influences And Relation With The Glandular Microenvironment In The Transgenic Adenocarcinoma Of Mouse Prostate (tramp) Model.

Aging is considered one of the main predisposing factors for the development of prostate malignancies. Angiogenesis is fundamental for tumor growth and its inhibition represents a promising therapeutic approach in cancer treatment. Thus, we sought to determine angiogenic responses and the effects of antiangiogenic therapy in the mouse prostate during late life, comparing these findings with the prostatic microenvironment in the Transgenic Adenocarcinoma of Mouse Prostate (TRAMP) model. Male mice (52 week-old FVB) were submitted to treatments with SU5416 (6 mg/kg; i.p.) and/or TNP-470 (15 mg/kg; s.c.). Finasteride was administered (20 mg/kg; s.c.), alone or in association to both inhibitors. The dorsolateral prostate was collected for VEGF, HIF-1α, FGF-2 and endostatin immunohistochemical and Western Blotting analyses and for microvessel density (MVD) count. Senescence led to increased MVD and VEGF, HIF-1α and FGF-2 protein levels in the prostatic microenvironment, similarly to what was observed in TRAMP mice prostate. The angiogenic process was impaired in all the treated groups, demonstrating significantly decreased MVD. Antiangiogenic and/or finasteride treatments resulted in decreased VEGF and HIF-1α levels, especially following TNP-470 administration, either alone or associated to SU5416. The combination of these agents resulted in increased endostatin levels, regardless of the presence of finasteride. Prostatic angiogenesis stimulation during senescence favored the development of neoplastic lesions, considering the pro-angiogenic microenvironment as a common aspect also observed during cancer progression in TRAMP mice. The combined antiangiogenic therapy was more efficient, leading to enhanced imbalance towards angiogenic inhibition in the organ. Finally, finasteride administration might secondarily upregulate the expression of pro-angiogenic factors, pointing to the harmful effects of this therapy. Prostate 75: 484-499, 2015. © 2014 Wiley Periodicals, Inc.

Self-perception and malocclusion and their relation to oral appearance and function

The aim of this study was to evaluate the relationship between malocclusion and self-perception of oral appearance/function, in 12/15-year-old Brazilian adolescents. The cluster sample consisted of 717 teenagers attending 24 urban public (n=611) and 5 rural public (n=107) schools in Maringá/PR. Malocclusion was measured using the Dental Aesthetic Index (DAI), in accordance with WHO recommendations. A parental questionnaire was applied to collect information on esthetic perception level and oral variables related to oral health. Univariate and multiple logistic regression analyses were performed. Multiple logistic regression confirmed that for 12-year-old, missing teeth (OR=2.865) and presence of openbite (open occlusal relationship) (OR=2.865) were risk indicators for speech capability. With regard to 15-year-old, presence of mandibular overjet (horizontal overlap) (OR=4.016) was a risk indicator for speech capability and molar relationship (OR=1.661) was a risk indicator for chewing capability. The impact of malocclusion on adolescents' life was confirmed in this study. Speech and chewing capability were associated with orthodontic deviations, which should be taken into consideration in oral health planning, to identify risk groups and improve community health services.

Relation between implant/abutment vertical misfit and torque loss of abutment screws

This study investigated whether there is a direct correlation between the level of vertical misfit at the abutment/implant interface and torque losses (detorque) in abutment screws. A work model was obtained from a metal matrix with five 3.75 x 9 mm external hex implants with standard platform (4.1 mm). Four frameworks were waxed using UCLA type abutments and one-piece cast in commercially pure titanium. The misfit was analyzed with a comparator microscope after 20 Ncm torque. The highest value of misfit observed per abutment was used. The torque required to loose the screw was evaluated using a digital torque meter. The torque loss values, measured by the torque meter, were assumed as percentage of initial torque (100%) given to abutment screws. Pearson's correlation (α=0.05) between the misfit values (29.08 ± 8.78 µm) and the percentage of detorque (50.71 ± 11.37%) showed no statistically significant correlation (p=0.295). Within the limitations of this study, it may be concluded that great vertical misfits dot not necessarily implies in higher detorque values.