Fundamenta Informaticae - Volume 70, issue 4

Authors: Berghammer, Rudolf | Fronk, Alexander

Article Type: Research Article

Abstract: A feedback vertex set of a graph is a subset of vertices containing at least one vertex from every cycle of the graph. Given a directed graph by its adjacency relation, we develop a relational algorithm for computing a feedback vertex set of minimum size. In combination with a BDD-implementation of relations, it allows to exactly solve this NP-hard problem for medium-sized graphs.

Keywords: Directed graphs, feedback vertex sets, elementary chordless cycles, relational algebra, RELVIEW tool

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 301-316, 2006

Authors: Hu, Yu-Chen | Lin, Min-Hui | Jiang, Ji-Han

Article Type: Research Article

Abstract: In this paper, a novel color image hiding scheme that is capable of hiding two color secret images into a color host image is proposed. The secret images to be embedded are first compressed by the single bit map block truncation coding. DES encryption is then conducted on the compressed message before the secret image is embedded into the rightmost 3, 2, 3 bits of the R, G, B channels of every pixel in the host image. The …experimental results show that our scheme provides an average secret image quality of 29.220 dB. In addition to the improved quality of both host images and retrieved secret images, our scheme further strengthens the protection of the secret images by conducting image compression and DES encryption on the secret image in advance. Therefore, our scheme not only extends the hiding capability of host images, but also is practical and secure. Show more

Keywords: Steganography, color image hiding, block truncation coding, DES

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 317-331, 2006

Authors: Mani, A.

Article Type: Research Article

Abstract: In [22] the problem of the logics corresponding to topological quasi-boolean algebras [27, 1] has been recently solved by the present author. The semantics provided involved convex amalgams of boolean algebras with additional total and partial operations. Canonical extensions of the structure was also investigated. In the present research, this semantics is generalized to a wide class of logics including distributive logics. It is also shown that the semantics is a proper generalization of the general …theory of algebraizable logics due to Blok-Pigozzi [5] and Czelakowski [7]. Show more

Keywords: Di-Algebraic Semantics of Logics, Distributive Logics, Convex Amalgams of Algebras, Inner Completions of Partial Algebras, Generalized Algebraic Logics, Canonical Models

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 333-350, 2006

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: We prove that negative hyper-resolution using any liftable and well-founded ordering refinement is a sound and complete procedure for answering queries in disjunctive logic programs. In our formulation, answers of queries are defined using disjunctive substitutions, which are more flexible than answer literals used in theorem proving systems.

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 351-366, 2006

Authors: Pestov, Vladimir | Stojmirović, Aleksandar

Article Type: Research Article

Abstract: We suggest a variation of the Hellerstein – Koutsoupias – Papadimitriou indexability model for datasets equipped with a similarity measure, with the aim of better understanding the structure of indexing schemes for similarity-based search and the geometry of similarity workloads. This in particular provides a unified approach to a great variety of schemes used to index into metric spaces and facilitates their transfer to more general similarity measures such as quasi-metrics. We discuss links between …performance of indexing schemes and high-dimensional geometry. The concepts and results are illustrated on a very large concrete dataset of peptide fragments equipped with a biologically significant similarity measure. Show more

Keywords: Similarity workload, metrics, quasi-metrics, indexing schemes, the curse of dimensionality

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 367-385, 2006

Authors: Yen, Hsu-Chun | Yu, Lien-Po

Article Type: Research Article

Abstract: For a variety of infinite-state systems, the problem of deciding whether a given system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for lossy vector addition systems with states, one-counter machines, and conflict-free Petri nets. For lossy counter machines and lossy channel systems, in contrast, the self-stabilization problem is shown to be undecidable.

Keywords: Decidability, infinite-state systems, self-stabilization, Petri nets

Citation: Fundamenta Informaticae, vol. 70, no. 4, pp. 387-402, 2006