Fundamenta Informaticae - Volume 80, issue 4

Authors: Bergstra, Jan A. | Middelburg, Cornelis A.

Article Type: Research Article

Abstract: We investigate basic issues concerning stored threads and their execution, building upon Maurer's model for computers and the thread algebra of Bergstra et al. We show among other things that a single thread can control the execution on a Maurer machine of any executable finite-state thread stored in the memory of the Maurer machine. We also relate stored threads with programs as considered in the program algebra of Bergstra et al. The work is intended as …a preparation for the development of a formal approach to model micro-architectures and to verify their correctness and anticipated speed-up results. Show more

Keywords: Maurer computer, thread algebra, stored thread, execution, control thread, program algebra

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 333-362, 2007

Authors: Bui, Alain | Sohier, Devan

Article Type: Research Article

Abstract: Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were known. First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. …Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalizations are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent. Then, we propose an algorithm to compute the n^2 hitting times on a weighted graph of n vertices, which we improve to obtain a O(n^3 ) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph. Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O(n^32^n ). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs. Show more

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 363-378, 2007

Authors: Flasiński, Mariusz

Article Type: Research Article

Abstract: A research into a syntactic pattern recognition model based on (edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982), 279-304) has resulted in defining the efficient, O(n^2 ), parsing schemes for the ETPL(k) subclass of these grammars and applying it for scene analysis, CAD/CAMobject analysis and constructingAI systems (Flasiński Patt. Recogn. 21 (1988), 623-629, Flasiński Comp. Vis. …Graph. Image Process. 47 (1989), 1-21, Flasiński Patt. Recogn. 26 (1993), 1-16, Flasiński Comp. Aided-Des. 27 (1995), 403-433, Flasiński Theor. Comp. Sci. 201 (1998), 189-231). In the paper the grammatical inference method for the parsable ETPL(k) graph grammars is defined, completing the development of this syntactic pattern recognition model. Show more

Keywords: syntactic pattern recognition, graph grammar, graph parsing, grammatical inference

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 379-413, 2007

Authors: Hébert, Céline | Bretto, Alain | Crémilleux, Bruno

Article Type: Research Article

Abstract: Finding hypergraph transversals is a major algorithmic issue which was shown having many connections with the data mining area. In this paper, by defining a new Galois connection, we show that this problem is closely related to the mining of the so-called condensed representations of frequent patterns. This data mining formalization enables us to benefit from efficient algorithms dedicated to the extraction of condensed representations. More precisely, we demonstrate how it is possible to use the …levelwise framework to improve the hypergraphminimal transversal computation by exploiting an anti-monotone constraint to safely prune the search space. We propose a new algorithm MTMINER to extract minimal transversals and provide experiments showing that our method is efficient in practice. Show more

Keywords: Datamining, Hypergraphminimal transversals, Levelwise framework, Condensed representations

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 415-433, 2007

Authors: Jiang, Feng | Sui, Yuefei | Cao, Cungen

Article Type: Research Article

Abstract: Since its foundation in the early 1980's, Formal ConceptAnalysis (FCA) has been used in many applications in data analysis, information retrieval, and knowledge discovery. In this paper, we suggest to exploit the framework of relational database model (RDM) and rough relational database model (RRDM) for Formal Concept Analysis. The basic idea is as follows. We firstly treat any relation (R,A) of RDM as a many-valued context of FCA. But for the rough relations of RRDM, we …define a special kind of many-valued context – rough-relational context in FCA (In this kind of context, every attribute value is a subset, but not an element, of the corresponding attribute domain), and treat any rough relation (R,A) of RRDMas a rough-relational context of FCA. Correspondingly, the definitions for concepts or rough concepts in context or rough-relational context (R,A) are given. The basic properties about these concepts or rough concepts in (R,A) are also discussed. Show more

Keywords: Formal Concept Analysis, relational database model, rough relational database model, rough sets

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 435-451, 2007

Authors: Li, Fagen | Hu, Yupu

Article Type: Research Article

Abstract: In 2006, Pomykala and Barabasz [Fundamenta Informaticae 69 (2006) 411–425] proposed an elliptic curve based threshold proxy signature scheme which requires shorter cryptographic keys. They claimed that their scheme satisfies the secrecy, the proxy protected, the unforgeability, the non-repudiation, and the known signers. However, in this paper, we show that their scheme cannot achieve the proxy protected, the unforgeability and the non-repudiation by demonstrating a conspiracy attack. In this attack, any t …malicious proxy signers can collusively impersonate some other proxy signers to generate proxy signatures. Show more

Keywords: cryptography, proxy signature, threshold proxy signature, conspiracy attack

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 453-459, 2007

Authors: Lu, Rongxing | Cao, Zhenfu | Dong, Xiaolei

Article Type: Research Article

Abstract: Identity based cryptography was introduced by Shamir in 1984, which avoids the trust problems encountered in the traditional Public Key Infrastructures. After Boneh and Franklin proposed the first full functional identity based encryption scheme from the bilinear pairings in 2001, many other identity based schemes using pairings have been proposed. However, how to design a practical identity based encryption scheme that avoids using the pairings is still an open problem today. In this paper, after studying …and combining the advantages of the traditional public key system and identity based system, we formally define a new Limited identity based system and present a concrete Limited identity based encryption scheme on a different complexity assumption. The resulting scheme is not only provably secure against the chosen plaintext attack in the random oracle, but also especially suitable for some practical system, such as an email system. Show more

Keywords: Identity based cryptography, Limited identity based encryption, Chosen-plaintext security, Email system

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 461-474, 2007

Authors: Maji, Pradipta | Pal, Sankar K.

Article Type: Research Article

Abstract: A hybrid unsupervised learning algorithm, termed as rough-fuzzy c-means, is proposed in this paper. It comprises a judicious integration of the principles of rough sets and fuzzy sets. While the concept of lower and upper approximations of rough sets deals with uncertainty, vagueness, and incompleteness in class definition, the membership function of fuzzy sets enables efficient handling of overlapping partitions. The concept of crisp lower bound and fuzzy boundary of a class, introduced in rough-fuzzy c-means, …enables efficient selection of cluster prototypes. Several quantitative indices are introduced based on rough sets for evaluating the performance of the proposed c-means algorithm. The effectiveness of the algorithm, along with a comparison with other algorithms, has been demonstrated on a set of real life data sets. Show more

Keywords: Pattern recognition, data mining, clustering, fuzzy c-means, rough sets

Citation: Fundamenta Informaticae, vol. 80, no. 4, pp. 475-496, 2007