Fundamenta Informaticae - Volume 169, issue 3

Authors: Feuillade, Guillaume | Herzig, Andreas | Rantsoudis, Christos

Article Type: Research Article

Abstract: Active integrity constraints have been introduced in the database community as a way to restore integrity based on a set of preferred update actions. We view active integrity constraints as dynamic logic programs and show how several semantics of database repair that were proposed in the literature can be characterised in Dynamic Logic of Propositional Assignments DL-PA . We moreover propose a new definition of repair which makes use of the programs of Dynamic Logic to provide repair solutions based on an iterating procedure. After an analysis of their properties and a comparison to the previous approaches, we provide complexity …results for the problem of existence of these new repairs. Furthermore, an extension on databases with history is explored and the behavior of the various repairs is adjusted to work in this setting. For all these definitions we provide DL-PA counterparts of reasoning and decision problems, such as the existence of a repair or the existence of a unique repair. Show more

Keywords: active integrity constraints, dynamic logic, propositional assignments

DOI: 10.3233/FI-2019-1843

Citation: Fundamenta Informaticae, vol. 169, no. 3, pp. 179-210, 2019

Authors: Kavand, P. | Mohades, A.

Article Type: Research Article

Abstract: In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n ) words of O (log n ) bits for reading and writing. The algorithm runs in O (n 4 ) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthest-site Voronoi diagram of the corners of the polygon can be computed in the same time …and space. As a sub-result, we present an s -workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O (n 2 /s ) expected time where s ∈ Ω ( log n ) ∩ O ( n log n   log 5 log n ) . Show more

Keywords: Computational geometry, memory-constrained algorithms, geodesic center, geodesic farthest neighbor, geodesic farthest-site Voronoi diagram

DOI: 10.3233/FI-2019-1844

Citation: Fundamenta Informaticae, vol. 169, no. 3, pp. 211-235, 2019

Authors: Zieliński, Bartosz

Article Type: Research Article

Abstract: Recent years have seen the emergence of a data-centric approach to business process modelling as an attractive alternative to the dominant task-centric one. This new paradigm requires new tools for effective specification, simulation and validation of data-centric models. In particular, such tools must include support for expressive query and database update languages. Rewriting logic was proposed (and successfully used) as a generic framework for the specification of dynamic systems. However, though relational and other data models can be easily simulated, rewriting systems lack the direct support for first-order queries. In this paper we describe a novel condition and query …language (at least as expressive as relational algebra), implemented in the term rewriting language Maude, together with a simple framework for relational transition system specification and simulation. The language is designed to be easy to implement on the top of a conditional rewriting system. Its most interesting feature is that it avoids all problems with variable binding. It works with models founded both on sets and multisets, and the language has linear-like facilities to refer to multiplicities of facts (in the case of multiset-founded models). As an example of the use of our language and simulation framework we reproduce some specifications of business processes from the literature. We also compare several methods for choosing the next action and its input during simulation. Show more

Keywords: Term rewriting, Query language, Business process modelling, Maude

DOI: 10.3233/FI-2019-1845

Citation: Fundamenta Informaticae, vol. 169, no. 3, pp. 237-274, 2019