Fundamenta Informaticae - Volume 86, issue 4

Authors: Abdelli, Abdelkrim | Badache, Nadjib

Article Type: Research Article

Abstract: In this paper, we propose an enumerative approach to build the state class graph of the TSPN (Time Stream Petri Net) model. A TSPN model is a Petri net augmented with intervals on arcs and synchronization rules on transitions. It can be used to model complex systems, and it is proved to be more expressive than TPN (Time Petri Nets). In contrast with TPN where each class accessible in the graph is given as a pair (M,D) where M is …a marking and D is a system of DBM inequalities, a TSPN class in this form is much complex to compute. To tackle this issue, we introduce a new formalism called the time distance function to define a TSPN class. This function makes it possible to determine an efficient algorithm to compute each class of the graph in a square complexity time. Finally, we show how to exploit the TSPN state class graph (when finite), to check over either linear properties of the model, or to compute minimal and maximal time distances of any firing sequence. Show more

Keywords: Time Stream Petri Net, Time Petri Net, State class graph, Time distance function, Difference bound Matrix, Multimedia

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 371-409, 2008

Authors: Mukhopadhyay, Anirban | Maulik, Ujjwal

Article Type: Research Article

Abstract: A popular approach for landcover classification in remotely sensed satellite images is clustering the pixels in the spectral domain into several fuzzy partitions. It has been observed that performance of the clustering algorithms deteriorate with more and more overlaps in the data sets. Motivated by this observation, in this article a two-stage fuzzy clustering algorithm is described that utilizes the concept of points having significant membership to multiple classes. The points situated in the overlapped regions …of different clusters are first identified and excluded from consideration while clustering. Thereafter, these points are given class labels based on Support vector Machine classifier which is trained by the remaining points. The well known Fuzzy C-Means algorithm and some recently proposed genetic clustering schemes are utilized in the process. The effectiveness of the two-stage clustering technique has been demonstrated on IRS remote sensing satellite images of the cities of Bombay and Calcutta and compared with other well known clustering techniques. Also statistical significance test has been carried out to establish the statistical significance of the clustering results. Show more

Keywords: Unsupervised pixel classification, significant multiclass membership, cluster validity index, variable string length genetic algorithm, multiobjective genetic algorithm, Support Vector Machine

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 411-428, 2008

Authors: Chaitin, Gregory

Article Type: Research Article

Abstract: Using work of Hao Wang, we exhibit a tiling characterization of the bits of the halting probability.

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 429-433, 2008

Authors: Chang, Chin-Chen | Chou, Yung-Chen | Kieu, The Duc

Article Type: Research Article

Abstract: High embedding capacity and low image distortion factors are main concerns of information hiding researchers. No scheme can achieve these two factors simultaneously. The purpose of achieving either high embedding capacity or low image distortion varies from application to application. This paper presents a high embedding capacity information hiding method for grayscale images. The proposed method converts binary secret data into secret digits in the base-5 numeral system first. Next, one secret digit in the base-5 …numeral system is embedded into one cover pixel. The experimental results show that the proposed method can be used to embed two secret bits into one cover pixel with the imperceptible image distortion. Comparing with some other works, we found that our method indeed outperforms all others in terms of embedding capacity. Show more

Keywords: Covert communication, data hiding, steganography

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 435-446, 2008

Authors: Chen, Chien-Chang | Chien, Yu-Wei

Article Type: Research Article

Abstract: This work presents a secret image sharing approach for sharing several secret images while reducing each participants possessing load to only one shared image. The proposed approach employs a random image and a hash function to create corresponding random-like shift images for each secret image, and then publishes the generated images. The random image is then secretly shared to each participant, such that each participant can only possess one shared image to recover the random image, …thus enabling the computation of all secret images. The contiguous hash results modify the secret images to random-like public images that are secure for malicious attacks. Experimental results indicate that the proposed method can share several secret images but reduce the possessing load of each participant efficiently. Attacks on shared or public images are also discussed. Show more

Keywords: multistage secret sharing, secret image sharing, hash function

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 447-458, 2008

Authors: Drewes, Frank | du Toit, Christine | Ewert, Sigrid | van der Merwe, Brink | van der Walt, Andries

Article Type: Research Article

Abstract: We introduce bag context as a device for regulated rewriting in tree grammars. Bag context represents information that is not part of a developing tree, but instead evolves separately during a derivation. We present several results. First, we give some normal forms and equivalent formulations for bag context tree grammars. Then we compare bag context tree grammars to their random context counterparts. We show that bag context is strictly more powerful than random context; in doing …so, we show that the class of bag context tree languages is the closure of the class of random context tree languages under linear top-down tree transductions. Finally, we consider the structural limitations of bag context tree grammars. We establish a necessary condition for languages generated by bag context tree grammars, and use it to present a tree language that cannot be generated by such a grammar. Moreover, we show that the class of bag context tree languages is incomparable with the class of branching synchronization tree languages. Show more

Keywords: formal languages, tree grammars, regulated rewriting, bag context

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 459-480, 2008

Authors: Ha, Minghu | Pedrycz, Witold | Zhang, Aiquan | Fan, Yijun

Article Type: Research Article

Abstract: Given a widespread interest in rough sets as being applied to various tasks of data analysis, it is not surprising at all that we have witnessed a wave of further generalizations and algorithmic enhancements of this original concept. In this study, we investigate an idea of rough fuzzy random sets. This construct provides us with a certain generalization of rough sets by introducing the concept of inclusion degree. The underlying objective behind this development is to …address the problems which involve co-existing factors of fuzziness and randomness thus giving rise to a notion of the fuzzy random approximation space based on inclusion degree. Some essential properties of rough approximation operators of such rough fuzzy random sets are discussed. Further theoretical foundations for the formation of rules constructed on a basis of available decision tables are offered as well. Show more

Keywords: Rough sets, Fuzzy random sets, Inclusion degree, Rough approximation operators, Decision tables

Citation: Fundamenta Informaticae, vol. 86, no. 4, pp. 481-502, 2008