Fundamenta Informaticae - Volume 56, issue 3

Authors: Balbiani, Philippe

Article Type: Research Article

Abstract: We devote this paper to the completeness of an axiom system for PDL^{∩}_{0} — a variant of PDL which includes the program operations of composition and intersection. Most of the difficulty in the proof of the completeness theorem for PDL^{∩}_{0} lies in the fact that intersection of accessibility relations is not modally definable. We overcome this difficulty by considering the concepts of theory and large program. Theories are sets of formulas that contain PDL^{∩}_{0} and are …closed under the inference rule of modus ponens. Large programs are built up from program variables and theories by means of the operations of composition and intersection, just as programs are built up from program variables and tests. Adapting these concepts to the subordination method, we can prove the completeness of our deductive system for PDL^{∩}_{0}. Show more

Keywords: propositional modal logic, propositional dynamic logic, composition of programs, intersection of programs, test on a formula, deductive completeness, subordination method

Citation: Fundamenta Informaticae, vol. 56, no. 3, pp. 211-242, 2003

Authors: Huang, Hui-Feng | Chang, Chin-Chen

Article Type: Research Article

Abstract: Previously, all of the proposed threshold proxy signature schemes which have been based on the discrete logarithms required a protocol to generate and verify a shared secret among the proxy group. Therefore, it is necessary for the proxy signers to execute a lot of expensive modular exponential computations and communications to obtain and verify a shared secret. Thus, it is very time-consuming to construct the proxy signature. Moreover, some of the existing threshold proxy signature schemes …reveal that the receiver cannot find out who signed the proxy signatures. In this paper, we proposed a practical, efficient, and low communications (t, n) threshold proxy signature scheme based on RSA cryptosystem. By using our way, not only the original signer can know who generated the proxy signature, but also everyone can be a verifier to certify the actuality of the group signers who made it. So, it is very convenient to clarify the responsibility of the document's signers fairly. Show more

Keywords: RSA cryptosystem, proxy signature, threshold proxy signature

Citation: Fundamenta Informaticae, vol. 56, no. 3, pp. 243-253, 2003

Authors: Margenstern, Maurice

Article Type: Research Article

Abstract: In this paper, we pay a new visit to an object of hyperbolic geometry which, perhaps, did not draw on itself all the attention it may deserve. The paper gives a simple definition of this object, infinigons, which was implicit in general considerations about tilings of the hyperbolic plane, and which was not definied in its all possible extensions. From the simple construction of the infinigons and using the ideas of the splitting method being introduced …by the author in the case of tilings being based on the replication of regular polygons, we give an algorithmic construction of the infinigrids. On the way, we give a simple geometrical characterisation of the infinigons in terms of pencils of lines. Show more

Keywords: hyperbolic geometry, tilings, combinatorial geometry

Citation: Fundamenta Informaticae, vol. 56, no. 3, pp. 255-272, 2003

Authors: Ord, Toby | Kieu, Tien D.

Article Type: Research Article

Abstract: We show how to determine the k-th bit of Chaitin's algorithmically random real number Ω by solving k instances of the halting problem. From this we then reduce the problem of determining the k-th bit of Ω to determining whether a certain Diophantine equation with two parameters, k and N, has solutions for an odd or an even number of values of N. We also demonstrate two further examples of Ω in number theory: an exponential …Diophantine equation with a parameter k which has an odd number of solutions iff the k-th bit of Ω is 1, and a polynomial of positive integer variables and a parameter k that takes on an odd number of positive values iff the k-th bit of Ω is 1. Show more

Keywords: diophantine equation, Ω, algorithmic information theory, randomness, Hilbert's tenth problem

Citation: Fundamenta Informaticae, vol. 56, no. 3, pp. 273-284, 2003

Authors: Wojna, Arkadiusz

Article Type: Research Article

Abstract: The paper addresses the problem of indexing data for k nearest neighbors (k-nn) search. Given a collection of data objects and a similarity measure the searching goal is to find quickly the k most similar objects to a given query object. We present a top-down indexing method that employs a widely used scheme of indexing algorithms. It starts with the whole set of objects at the root of an indexing tree and iteratively splits data at each level of …indexing hierarchy. In the paper two different data models are considered. In the first, objects are represented by vectors from a multi-dimensional vector space. The second, more general, is based on an assumption that objects satisfy only the axioms of a metric space. We propose an iterative k-means algorithm for tree node splitting in case of a vector space and an iterative k-approximate-centers algorithm in case when only a metric space is provided. The experiments show that the iterative k-means splitting procedure accelerates significantly k-nn searching over the one-step procedure used in other indexing structures such as GNAT, SS-tree and M-tree and that the relevant representation of a tree node is an important issue for the performance of the search process. We also combine different search pruning criteria used in BST, GHT nad GNAT structures into one and show that such a combination outperforms significantly each single pruning criterion. The experiments are performed for benchmark data sets of the size up to several hundreds of thousands of objects. The indexing tree with the k-means splitting procedure and the combined search criteria is particularly effective for the largest tested data sets for which this tree accelerates searching up to several thousands times. Show more

Citation: Fundamenta Informaticae, vol. 56, no. 3, pp. 285-310, 2003