Fundamenta Informaticae - Volume 158, issue 4

Authors: Amadini, Roberto | Gange, Graeme | Gauthier, François | Jordan, Alexander | Schachte, Peter | Søndergaard, Harald | Stuckey, Peter J. | Zhang, Chenyi

Article Type: Research Article

Abstract: Abstract interpretation is a well established theory that supports reasoning about the run-time behaviour of programs. It achieves tractable reasoning by considering abstractions of run-time states, rather than the states themselves. The chosen set of abstractions is referred to as the abstract domain. We develop a novel framework for combining (a possibly large number of) abstract domains. It achieves the effect of the so-called reduced product without requiring a quadratic number of functions to translate information among abstract domains. A central notion is a reference domain, a medium for information exchange. Our approach suggests a novel and simpler way to …manage the integration of large numbers of abstract domains. We instantiate our framework in the context of string analysis. Browser-embedded dynamic programming languages such as JavaScript and PHP encourage the use of strings as a universal data type for both code and data values. The ensuing vulnerabilities have made string analysis a focus of much recent research. String analysis tends to combine many elementary string abstract domains, each designed to capture a specific aspect of strings. For this instance the set of regular languages, while too expensive to use directly for analysis, provides an attractive reference domain, enabling the efficient simulation of reduced products of multiple string abstract domains. Show more

DOI: 10.3233/FI-2018-1650

Citation: Fundamenta Informaticae, vol. 158, no. 4, pp. 297-326, 2018

Authors: Badia, Antonio | Lemire, Daniel

Article Type: Research Article

Abstract: Codd’s relational model describes just one possible world. To better cope with incomplete information, extended database models allow several possible worlds. Vague tables are one such convenient extended model where attributes accept sets of possible values (e.g., the manager is either Jill or Bob). However, conceptual database design in such cases remains an open problem. In particular, there is no canonical definition of functional dependencies (FDs) over possible worlds (e.g., each employee has just one manager). We identify several desirable properties that the semantics of such FDs should meet including Armstrong’s axioms, the independence from irrelevant attributes, seamless satisfaction and …implied by strong satisfaction. We show that we can define FDs such that they have all our desirable properties over vague tables. However, we also show that no notion of FD can satisfy all our desirable properties over a more general model (disjunctive tables). Our work formalizes a trade-off between having a general model and having well-behaved FDs. Show more

Keywords: Relational Database, Functional Dependencies, Database Design, Incomplete Information, Conceptual Design

DOI: 10.3233/FI-2018-1651

Citation: Fundamenta Informaticae, vol. 158, no. 4, pp. 327-352, 2018

Authors: Dost, Şenol

Article Type: Research Article

Abstract: In this paper, we propose the notion of precise sets in texture spaces. Precise sets are defined by using textural sections and presections under a direlation. We obtain some properties of definability; it is proved that the family of precise sets under reflexive and transitive direlation is an Alexandroff ditopology. It is observed that sections and presections, which are approximation operators in the textural meaning, are Galois connections. Finally, effective results are given for definability by using textural precise sets.

Keywords: Precise set, Definability, Texture space, Direlation, Approximation operator

DOI: 10.3233/FI-2018-1652

Citation: Fundamenta Informaticae, vol. 158, no. 4, pp. 353-368, 2018

Authors: Pérez, Claudia | Abarca, Mario | Rivera, Daniel

Article Type: Research Article

Abstract: Inflations algorithm is a procedure that appears implicitly in Ovsienko’s classical proof for the classification of positive definite integral quadratic forms. The best known upper asymptotic bound for its time complexity is an exponential one. In this paper we show that this bound can be tightened to O ( n 6 ) for the naive implementation. Also, we propose a new approach to show how to decide whether an admissible quasi-Cartan matrix is positive definite and compute the Dynkin type in just O ( n 3 ) …operations taking an integer matrix as input. Show more

Keywords: quasi-Cartan matrix, Dynkin diagram, integral quadratic form, root system, inflations algorithm

DOI: 10.3233/FI-2018-1653

Citation: Fundamenta Informaticae, vol. 158, no. 4, pp. 369-384, 2018

Authors: Wang, Xiang-yang | Xu, Huan | Zhang, Si-yu | Liang, Lin-lin | Niu, Pan-pan | Yang, Hong-ying

Article Type: Research Article

Abstract: Digital watermarking has been proposed as an effective technology of copyright protection and content authentication, yet up to now, research on the robust watermarking against geometric attacks is still a challenging task. This paper presents a novel robust watermarking algorithm in nonsubsampled shearlet transform (NSST) domain using quaternion polar harmonic transform (PHT) and least squares support vector regression (LS-SVR), which is a recently developed geometric correction algorithm for digital color image. The major innovative works of the proposed approach lie in that (1) the NSST is applied to embed the watermark, which can provide the image function with nearly optimal …approximation and employ fully the properties of human visual system (HVS), (2) the robust 2D transform, namely quaternion PHT is introduced to represent the characteristics of color image, and (3) the novel synchronous correction method is proposed using the excellent LS-SVR and quaternion PHTs, which can accurately estimate the geometric distortions parameters. In our experiments, we applied the proposed method to the standard color image test dataset, and the experimental results demonstrate that the proposed algorithm is not only invisible, but also robustness against common signal processing operations and geometric attacks. Show more

Keywords: Color image watermarking, geometric distortions, nonsubsampled shearlet transform, quaternion polar harmonic transform, least squares support vector regression

DOI: 10.3233/FI-2018-1654

Citation: Fundamenta Informaticae, vol. 158, no. 4, pp. 385-407, 2018