Fundamenta Informaticae - Volume 91, issue 3-4

Authors: ter Beek, Maurice H. | Kleijn, Jetty

Article Type: Research Article

Abstract: Motivated by different ways to obtain team automata from synchronizing component automata, we consider various definitions of synchronized shuffles of words. A shuffle of two words is an interleaving of their symbol occurrenceswhich preserves the original order of these occurrences within each of the two words. In a synchronized shuffle, however, also two occurrences of one symbol, each from a different word, may be identified as a single occurrence. In case at least one of the …words involved is infinite, a (synchronized) shuffle can also be unfair in the sense that an infinite word may prevail fromsome point onwards even when the other word still has occurrences to contribute to the shuffle. We prove that for the synchronized shuffle operations under consideration, every (fair or unfair) synchronized shuffle can be obtained as a limit of synchronized shuffles of the finite prefixes of the words involved. In addition, it is shown that with the exception of one, all synchronized shuffle operations that we consider satisfy a natural notion of associativity, also in case of unfairness. Finally, using these results, some compositionality results for team automata are established. Show more

Keywords: Team automata, synchronized shuffling, infinite words, fairness, associativity, compositionality

DOI: 10.3233/FI-2009-0051

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 437-461, 2009

Authors: Bernot, Gilles | Tahi, Fariza

Article Type: Research Article

Abstract: The main contribution of this work is a mathematical theorem which establishes a necessary and sufficient condition to preserve the behaviour of a genetic regulatory network when it is embedded into a larger network. We adopt the modelling approach of René Thomas, which provides a discrete representation of biological regulatory networks. This framework is entirely formalized using labelled graphs with semantics defined in terms of state graphs with transitions. Our theorem offers the possibility to automatically …verify whether a subnetwork has autonomous behaviour. It will allow biologists to better identify relevant sets of genes which should be studied together. Show more

DOI: 10.3233/FI-2009-0052

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 463-485, 2009

Authors: Bhowmick, Partha | Bhattacharya, Bhargab B.

Article Type: Research Article

Abstract: There are several algorithms for digitization of a real disc (circle) to derive a digital disc, and also for finding the real disc corresponding to a digital disc. However, the correspondence of a digital disc with a regular polygon in the real plane is not well studied. This paper presents some theories and related experiments on setting the correspondence from a digital disc to its polygonal cover in the real plane. For an ideal regular polygon …covering a digital disc, all the grid points of the digital disc should lie on and inside the polygon, and vice versa. That an ideal regular polygon corresponding to a digital disc is possible for some of the digital discs, especially for the ones having smaller radii, is shown. Further, for a disc whose ideal regular polygon is not possible, an approximate polygon, tending to the ideal one, is possible, in which the error of approximation can be controlled by the number of vertices of the approximate polygon. These (ideal or approximate) polygonal covers of digital discs have several applications in many problems of point set pattern matching. We have reported the conditions under which an ideal regular polygon always exists corresponding to a digital disc, and the conditions under which the existence of an ideal regular polygon becomes uncertain. Experimental results have been given to demonstrate the possibilities of approximation and the trade-off in terms of error versus the number of vertices in the approximate polygon. Show more

Keywords: digital disc, digital circle, polygonal approximation, digital geometry

DOI: 10.3233/FI-2009-0053

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 487-505, 2009

Authors: Damaševičius, Robertas

Article Type: Research Article

Abstract: To achieve better software quality, to shorten software development time and to lower development costs, software engineers are adopting generative reuse as a software design process. The usage of generic components allows increasing reuse and design productivity in software engineering. Generic component design requires systematic domain analysis to identify similar components as candidates for generalization. However, component feature analysis and identification of components for generalization usually is done ad hoc. In this …paper, we propose to apply a data visualization method, called Multidimensional Scaling (MDS), to analyze software components in the multidimensional feature space. Multidimensional data that represent syntactical and semantic features of source code components are mapped to 2D space. The results of MDS are used to partition an initial set of components into groups of similar source code components that can be further used as candidates for generalization. STRESS value is used to estimate the generalizability of a given set of components. Case studies for Java Buffer and Geom class libraries are presented. Show more

Keywords: component based software engineering, feature engineering, domain analysis, software similarity, generalization, multidimensional scaling

DOI: 10.3233/FI-2009-0054

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 507-522, 2009

Authors: Gao, Chong-zhi | Yao, Zheng-an

Article Type: Research Article

Abstract: Online/offline signatures are used in a particular scenario where the signer must respond quickly once the message to be signed is presented. In this paper, we present a general method to efficiently convert a trapdoor hash family into an online/offline signature scheme without resorting to any additional signature scheme. We prove that the new scheme is secure in the randomoraclemodel if the underlying trapdoor hash family is collision resistant. Compared to Shamir and Tauman's paradigm, there …is an almost 50% reduction in overall computational cost by using the new scheme. Show more

Keywords: Cryptography, Signature Schemes, Online/Offline, Trapdoor Hash Family

DOI: 10.3233/FI-2009-0055

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 523-532, 2009

Authors: Gillibert, Luc | Bretto, Alain

Article Type: Research Article

Abstract: Hypergraphs are a large generalisation of graphs; they are now used for many low-level image processing, by example for noise reduction, edge detection and segmentation [3, 4, 7]. In this paper we define a generic 2D and 3D-image representation based on a hypergraph. We present the mathematical definition of the hypergraph representation of an image and we show how this representation conducts to an efficient lossless compression algorithm for 2D and 3D-images. Then we introduce both …2D and 3D version of the algorithm and we give some experimental results on some various sets of images: 2D photo, 2D synthetic pictures, 3D medical images and some short animated sequences. Show more

Keywords: Hypergraph image model, lossless compression

DOI: 10.3233/FI-2009-0056

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 533-546, 2009

Authors: Hristea, Florentina | Popescu, Marius

Article Type: Research Article

Abstract: The present paper extends a new word sense disambiguation method [9] to the case of adjectives. The method lies at the border between unsupervised and knowledge-based techniques. It performs unsupervised word sense disambiguation based on an underlying Naïve Bayes model, while using WordNet as knowledge source for feature selection. The proposed extension of the disambiguation method makes ample use of the WordNet semantic relations that are typical of adjectives. Its performance is compared to that of …previous approaches that rely on completely different feature sets. Test results show that feature selection using a knowledge source of type WordNet is more effective in the disambiguation of adjective senses than local type features (like part-of-speech tags) are. Show more

Keywords: word sense disambiguation, unsupervised disambiguation, knowledge-based disambiguation , Bayesian classification, the EM algorithm

DOI: 10.3233/FI-2009-0057

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 547-562, 2009

Authors: Huang, Chang-Chin | Tsai, Du-Shiau | Horng, Gwoboa

Article Type: Research Article

Abstract: In vector quantization, the codebook generation problem can be formulated as a classification problem of dividing N_{p} training vectors into N_{c} clusters, where N_{p} is the training size of input vectors and N_{c} is the codeword size of codebook. For large N_{p} and N_{c} , a traditional search algorithmsuch as the LBG method can hardly find the global optimal classification and …needs a great deal of calculation. In this paper, a novel VQ codebook generation method based on Otsu histogram threshold is proposed. The computational complexity of squared Euclidean distance can be reduced to O(N_{p} log_{2} N_{c} ) for a codebook with gray levels. Our method provides better image quality than recent proposed schemes in high compression ratio. The experimental results and the comparisons show that this method can not only reduce the computational complexity of squared Euclidean distance but also find better codewords to improve the quality of the resulted VQ codebook. Show more

Keywords: Vector quantization, codebook generation, histogram thresholding, clustering, withinclass variance, between-class variance, LBG algorithm

DOI: 10.3233/FI-2009-0058

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 563-579, 2009

Authors: Lin, Ching-Chiuan | Yang, Shun-Ping | Hsueh, Nien-Lin

Article Type: Research Article

Abstract: This paper proposes a reversible data hiding scheme based on three-circular-pixel (TCP) difference expansion. To embed a message in an image, the image is divided into three-pixel blocks, each of which is, then, transformed into a TCP block with two differences. When the pixel value of the largest pixel in the TCP block is increased, two differences are increased – one is between the largest and the smallest, and the other is between the largest and …the middle. Expanding the two differences in the block by increasing the largest pixel value may make the image less modified. In addition, the number of pixel pairs is increased to two thirds of the number of pixels in the image. Compared to Tian's study, both the visual quality and the embedding capacity of the image are significantly improved. Show more

Keywords: Difference expansion , information hiding, reversible data hiding, steganography

DOI: 10.3233/FI-2009-0059

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 581-595, 2009

Authors: Lu, Tzu-Chuen | Chang, Chin-Chen | Liu, Yi-Long

Article Type: Research Article

Abstract: Information hiding is a technique that embeds secret data in digital media for using in a variety of applications, including ownership protection, authentication, access control, annotation and so on. In this paper, we propose an information hiding scheme based on quantization-based embedding technique to conceal information in gray-scale image. The proposed scheme was tested with a variety of gray images. According to the experimental results, hidden information can be extracted correctly and quickly from the stego …image. In addition, the stego image has only a little distortion compared with the cover image. The proposed scheme can not only hide a large amount of information in the cover image, but can also repair the stego image such that the repaired image is almost the same as the cover image. Show more

Keywords: information hiding, steganography, quantization-based embedding

DOI: 10.3233/FI-2009-0060

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 597-610, 2009

Authors: Moreira, Nelma | Reis, Rogério

Article Type: Research Article

Abstract: Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^{2} log n) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of …automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices. Show more

DOI: 10.3233/FI-2009-0061

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 611-629, 2009

Authors: Mu, Kedian | Liu, Weiru | Jin, Zhi | Lu, Ruqian | Yue, Anbu | Bell, David

Article Type: Research Article

Abstract: Developing a desirable framework for handling inconsistencies in software requirements specifications is a challenging problem. It has been widely recognized that the relative priority of requirements can help developers to make some necessary trade-off decisions for resolving con- flicts. However, for most distributed development such as viewpoints-based approaches, different stakeholders may assign different levels of priority to the same shared requirements statement from their own perspectives. The disagreement in the local levels …of priority assigned to the same shared requirements statement often puts developers into a dilemma during the inconsistency handling process. The main contribution of this paper is to present a prioritized merging-based framework for handling inconsistency in distributed software requirements specifications. Given a set of distributed inconsistent requirements collections with the local prioritization, we first construct a requirements specification with a prioritization from an overall perspective. We provide two approaches to constructing a requirements specification with the global prioritization, including a merging-based construction and a priority vector-based construction. Following this, we derive proposals for handling inconsistencies from the globally prioritized requirements specification in terms of prioritized merging. Moreover, from the overall perspective, these proposals may be viewed as the most appropriate to modifying the given inconsistent requirements specification in the sense of the ordering relation over all the consistent subsets of the requirements specification. Finally, we consider applying negotiation-based techniques to viewpoints so as to identify an acceptable common proposal from these proposals. Show more

Keywords: Inconsistency, Requirements Engineering, Prioritized Merging, Local Prioritization

DOI: 10.3233/FI-2009-0062

Citation: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 631-670, 2009