Fundamenta Informaticae - Volume 92, issue 4

Authors: Conradie, Willem | Goranko, Valentin | Vakarelov, Dimiter

Article Type: Research Article

Abstract: In earlier papers we have introduced an algorithm, SQEMA, for computing first-order equivalents and proving canonicity of modal formulae. However, SQEMA is not complete with respect to the so called complex Sahlqvist formulae. In this paper we, first, introduce the class of complex inductive formulae, which extends both the class of complex Sahlqvist formulae and the class of polyadic inductive formulae, and second, extend SQEMA to SQEMA^{sub} by allowing suitable substitutions in the process …of transformation. We prove the correctness of SQEMA^{sub} with respect to local equivalence of the input and output formulae and d-persistence of formulae on which the algorithm succeeds, and show that SQEMA^{sub} is complete with respect to the class of complex inductive formulae. Show more

Keywords: SQEMA, correspondence, d-persistence, complex Sahlqvist formulae

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 307-343, 2009

Authors: Halder, Anindya | Ghosh, Ashish | Ghosh, Susmita

Article Type: Research Article

Abstract: The study of ant colonies behavior and their self-organizing capabilities is of interest to machine learning community, because it provides models of distributed adaptive organization which are useful to solve difficult optimization and classification problems among others. Social insects like ants, bees deposit pheromone (a type of chemical) in order to communicate between the members of their community. Pheromone, that causes clumping behavior in a species and brings individuals into a closer proximity, is called …aggregation pheromone. This article presents a new algorithm (called, APC) for pattern classification based on this property of aggregation pheromone found in natural behavior of real ants. Here each data pattern is considered as an ant, and the training patterns (ants) form several groups or colonies depending on the number of classes present in the data set. A new test pattern (ant) will move along the direction where average aggregation pheromone density (at the location of the new ant) formed due to each colony of ants is higher and hence eventually it will join that colony. Thus each individual test pattern (ant) will finally join a particular colony. The proposed algorithm is evaluated with a number of benchmark data sets as well as various kinds of artificially generated data sets using three evaluationmeasures. Results are compared with four other well known conventional classification techniques. Experimental results show the potentiality of the proposed algorithm in terms of all the evaluation measures compared to other algorithms. Show more

Keywords: Swarm intelligence, Ant colony optimization, Aggregation pheromone, Pattern classification

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 345-362, 2009

Authors: Spatharis, Anthony | Foudalis, Ilias | Sideri, Martha | Papadimitriou, Christos

Article Type: Research Article

Abstract: We introduce and evaluate several new models of network growth. Our models are extensions of the FKP model, modifying and improving it in various dimensions. In all these models nodes arrive one by one, and each node is connected to previous nodes by optimizing a trade-off between a geometric objective ("last mile cost") and a topological objective ("position in the network"). Our new models differ from the original FKP model in directions inspired by the real …Internet: two or more edges are attached to each arriving node (while the FKP model produces a tree); these edges are chosen according to various criteria such as robustness; edges may be added to the network between old nodes; or only certain "fertile" nodes (an attribute that changes dynamically) are capable of attracting new edges. We evaluate these models, and compare them with the graph of the Internet's autonomous systems, with respect to a suite of many test parameters (such as average degree, power law exponent, and local clustering rank) proposed in the literature; to this end we have developed the network generation and measurement system Pandora. Show more

Keywords: Internet topology, power law, scale-free graphs, network generators, networkmodeling and simulation, complex networks

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 363-372, 2009

Authors: Sroka, Jacek | Hidders, Jan

Article Type: Research Article

Abstract: Workflow development and enactment workbenches are becoming a standard tool for conducting in silico experiments. Their main advantages are easy to operate user interfaces, specialized and expressive graphical workflow specification languages and integration with a huge number of bioinformatic services. A popular example of such a workbench is Taverna, which has many additional useful features like service discovery, storing intermediate results and tracking data provenance. We discuss a detailed formal semantics for Scufl - …the workflow definition language of the Taverna workbench. It has several interesting features that are notmet in other models including dynamic and transparent type coercion and implicit iteration, control edges, failure mechanisms, and incominglinks strategies. We study these features and investigate their usefulness separately as well as in combination, and discuss alternatives. The formal definition of such a detailed semantics not only allows to exactly understand what is being done in a given experiment, but is also the first step toward automatic correctness verification and allows the creation of auxiliary tools that would detect potential errors and suggest possible solutions to workflow creators, the same way as Integrated Development Environments aid modern programmers. A formal semantics is also essential for work on enactment optimization and in designing the means to effectively query workflow repositories. This paper is the second of two. In the first one [13] we have defined, explained and discussed fundamental notions for describing Scufl graphs and their semantics. Here, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs. Show more

Keywords: formal semantics, Scufl, workflows, Taverna workbench

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 373-396, 2009

Authors: Yang, Cheng-Hsing | Weng, Chi-Yao | Wang, Shiuh-Jeng | Sun, Hung-Min

Article Type: Research Article

Abstract: Digital watermarking techniques are an importantmethod to provide copyright protection of multimedia. In this paper, we proposed a non-embedded watermarking scheme, based on vector quantization (VQ), to protect the image copyright. Our approach applies a codebook to generate a relationship between image blocks and watermark bits, and then the relationship is outputted as the key stream (called KS). With the KS, the relationship between the image and the watermark are confirmed and the copyright of the …image is declared. In our method, the number of bits that are related to a block is adaptive. Compared to the scheme of Lin et al., our approach needs only one codebook, while their approach requires seven. Moreover, in our approach each block can be connected with watermark bits, while some blocks can not be connected with watermark bits in their method. Finally, a method of adjusting the robustness is given for our proposed approach. Our approach not only reduces the length of the key stream, but it also allows for a more flexible application. In addition, our experimental results show that the proposed approach runs faster and is more robust than that of Lin et al. Show more

Keywords: Non-embedded Watermark, Vector Quantization, Image Integrity, Image Copyright

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 397-409, 2009

Authors: Zhong, Sheng

Article Type: Research Article

Abstract: When a database owner needs to disclose her data, she can k-anonymize her data to protect the involved individuals' privacy. However, if the data is distributed between two owners, then it is an open question whether the two owners can jointly k-anonymize the union of their data, such that the information suppressed in one owner's data is not revealed to the other owner. In this paper, we study this problemof distributed k-anonymization. We have two major …results: First, it is impossible to design an unconditionally private protocol that implements any normal k-anonymization function, where normal k-anonymization functions are a very broad class of k-anonymization functions. Second, we give an efficent protocol that implements a normal k-anonymization function and show that it is private against polynomial-time adversaries. Our results have many potential applications and can be extended to three or more parties. Show more

Keywords: k-anonymity, protocol, secure computation

Citation: Fundamenta Informaticae, vol. 92, no. 4, pp. 411-431, 2009