Home  About us  Contact
 

Relation Algebras (relation + algebra)

Distribution by Scientific Domains
Information Science and Computing100%

Selected Abstracts

Granularity in Relational Formalisms,With Application to Time and Space Representation

COMPUTATIONAL INTELLIGENCE, Issue 4 2001
Jérôme Euzenat
Temporal and spatial phenomena can be seen at a more or less precise granularity, depending on the kind of perceivable details. As a consequence, the relationship between two objects may differ depending on the granularity considered. When merging representations of different granularity, this may raise problems. This paper presents general rules of granularity conversion in relation algebras. Granularity is considered independently of the specific relation algebra, by investigating operators for converting a representation from one granularity to another and presenting six constraints that they must satisfy. The constraints are shown to be independent and consistent and general results about the existence of such operators are provided. The constraints are used to generate the unique pairs of operators for converting qualitative temporal relationships (upward and downward) from one granularity to another. Then two fundamental constructors (product and weakening) are presented: they permit the generation of new qualitative systems (e.g. space algebra) from existing ones. They are shown to preserve most of the properties of granularity conversion operators. [source]

A simple construction of representable relation algebras with non-representable completions

MLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 3 2009
Tarek Sayed Ahmed
Abstract We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source]

Weakly associative relation algebras with projections

MLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 2 2009
Agi Kurucz
Abstract Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first-order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on increasing the expressive power of WA by adding new operations [1, 4, 11, 13, 20]. Extensions of this kind usually also have decidable universal theories. Here we give an example , extending WA's with set-theoretic projection elements , where this is not the case. These "logical" connectives are set-theoretic counterparts of the axiomatic quasi-projections that have been investigated in the representation theory of relation algebras [22, 6, 19]. We prove that the quasi-equational theory of the extended class PWA is not recursively enumerable. By adding the difference operator D one can turn WA and PWA to discriminator classes where each universal formula is equivalent to some equation. Hence our result implies that the projections turn the decidable equational theory of "WA + D " to non-recursively enumerable (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source]