Fundamenta Informaticae - Volume 167, issue 4

Authors: Bazhenov, Nikolay

Article Type: Research Article

Abstract: We investigate computability-theoretic properties of contact algebras. These structures were introduced by Dimov and Vakarelov in [Fundam. Inform. 74 (2006), 209–249] as an axiomatization for the region-based theory of space. We prove that the class of countable contact algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. This means that the class of contact algebras is very rich from the computability-theoretic point of view. As an application of our result, we show that the ∏3 -theory of contact algebras is hereditarily undecidable. This is a refinement of the …result of Koppelberg, Düntsch, and Winter [Algebra Univers., 68 (2012), 353–366]. Show more

Keywords: Contact algebra, computable structure, Boolean algebra, degree spectrum, computable dimension, contact relation, region-based theory of space, elementary definability, hereditary undecidability

DOI: 10.3233/FI-2019-1817

Citation: Fundamenta Informaticae, vol. 167, no. 4, pp. 257-269, 2019

Authors: Rudi, Ali Gholami

Article Type: Research Article

Abstract: We study the problem of finding hotspots, i.e. regions, in which a moving entity spends a significant amount of time, for polygonal trajectories. The fastest exact algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in O (n 2 ) for a trajectory with n edges. Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or to the y -axis, we present an approximation algorithm with the time complexity O (n log3 n ) and approximation factor 1/2.

Keywords: Trajectory hotspots, Kinetic tournament, Computational geometry

DOI: 10.3233/FI-2019-1818

Citation: Fundamenta Informaticae, vol. 167, no. 4, pp. 271-285, 2019

Authors: Grahne, Gösta | Moallemi, Ali

Article Type: Research Article

Abstract: Incomplete Information research is quite mature when it comes to so called existential nulls , where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls , that is, values representing all possible objects, have received almost no attention. We remedy the situation in this paper, by showing that a suitable finite representation mechanism, called Star Cylinders , handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra …, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. All cylindric star-algebra expressions can be evaluated in time polynomial in the size of the database. The representation mechanism is then extended to Naive Star Cylinders , which are star-cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬(x i ≈ x j ) are allowed, reasoning over existential databases is known to be ∏ 2 p -complete, and it remains in ∏ 2 p when universal nulls and full first order queries are allowed. Show more

Keywords: Relational Algebra, Cylindric Set Algebra, Incomplete Information, Query Languages

DOI: 10.3233/FI-2019-1819

Citation: Fundamenta Informaticae, vol. 167, no. 4, pp. 287-321, 2019

Authors: Klaudel, Hanna | Koutny, Maciej | Duan, Zhenhua | Moszkowski, Ben

Article Type: Research Article

Abstract: In this paper, we further develop a recently introduced semantic link between temporal logics and Petri nets. We focus on two specific formalisms, Interval Temporal Logic (ITL ) and Box Algebra (BA ), which are closely related by their compositional approach to constructing system descriptions. The overall goal of our investigation is to translate Petri nets into behaviourally equivalent logical formulas. As a result, the analysis of system properties can be carried out using either of the two formalisms, exploiting their respective strengths and powerful tool support. The contribution of this paper is twofold. First, we extend the existing …translation from BA to ITL , by removing restrictions concerning the way control flow of concurrent system is modelled, and by allowing a fully general synchronisation operator. Second, we strengthen the notion of equivalence between a Petri net and the corresponding logical formula by proving such an equivalence at the level of transition-based executions of Petri nets rather than just by looking at their labels. We also show that the complexity of the proposed translation compares favourably with the complexity of the translation from BA expressions to Petri nets. Show more

Keywords: Interval Temporal Logic, Petri nets, box algebra, composition, semantics, general synchronisation, step sequence, equivalence

DOI: 10.3233/FI-2019-1820

Citation: Fundamenta Informaticae, vol. 167, no. 4, pp. 323-354, 2019