Fundamenta Informaticae - Volume 55, issue 3-4

Authors: Aydin, Suna | Bordihn, Henning

Article Type: Research Article

Abstract: For tabled Lindenmayer systems and their languages, the degree of synchronization and the degree of nondeterminism are well investigated measures of descriptional complexity. In this paper the sequential counterparts of tabled Lindenmayer systems, namely cooperating distributed grammar systems and their pure variant (working in the so-called t-mode of derivation) are treated with respect to these complexity measures. In the pure case, where no distinction between terminal and nonterminal symbols is made, the sequential …mechanisms are compared with the parallel ones, investigating whether one mechanism may have a better descriptional complexity than the other one when the same language is described. Show more

Keywords: grammar systems, tabled Lindenmayer systems, degree of nondeterminism, degree of synchronization

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 243-254, 2003

Authors: Cattaneo, Gianpiero | Ciucci, Davide

Article Type: Research Article

Abstract: BZMV^{dM} algebras are introduced as an abstract environment to describe both shadowed and fuzzy sets. This structure is endowed with two unusual complementations: a fuzzy one ¬ and an intuitionistic one ∼. Further, we show how to define in any BZMV^{dM} algebra the Boolean sub-algebra of exact elements and to give a rough approximation of fuzzy elements through a pair of exact elements using an interior and an exterior mapping. Then, we introduce the weaker notion …of pre-BZMV^{dM} algebra. This structure still have as models fuzzy and shadowed sets but with respect to a weaker notion of intuitionistic negation ∼_α with α ∈ [0, ½). In pre-BZMV^{dM} algebras it is still possible to define an interior and an exterior mapping but, in this case, we have to distinguish between open and closed exact elements. Finally, we see how it is possible to define α-cuts and level fuzzy sets in the pre-BZMV^{dM} algebraic context of fuzzy sets. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 255-284, 2003

Authors: Chlebus, Bogdan S. | Gasieniec, Leszek | Pelc, Andrzej

Article Type: Research Article

Abstract: We consider Parallel Random Access Machine (PRAM) which has some processors and memory cells faulty. The faults considered are static, i.e., once the machine starts to operate, the operational/faulty status of PRAM components does not change. We develop a deterministic simulation of a fully operational PRAM on a similar faulty machine which has constant fractions of faults among processors and memory cells. The simulating PRAM has n processors and m memory cells, and simulates a PRAM …with n processors and a constant fraction of m memory cells. The simulation is in two phases: it starts with preprocessing, which is followed by the simulation proper performed in a step-by-step fashion. Preprocessing is performed in time O(({m/n}+log n)log n). The slowdown of a step-by-step part of the simulation is O(log m). Show more

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 285-306, 2003

Authors: Lee, Cheng-Chi | Yang, Wei-Pang | Hwang, Min-Shiang

Article Type: Research Article

Abstract: With the help of a blind signature scheme, a requester can obtain a signature on a message from a signer such that the signer knows nothing about the content of the messages and is unable to link the resulting message-signature pair; namely, a blind signature scheme can achieve both blindness and untraceability. Due to the above properties, the blind signature scheme can be used in cryptographic applications such as electronic voting systems and cash payment systems. So far, most of …the proposed blind signature schemes are based on the difficulty of solving the factoring problem and quadratic residues. In this paper, the authors intend to propose two new untraceable blind signature schemes based on the difficulty of solving the discrete logarithm problem. The two blind signature schemes are two variations of the DSA signature scheme and can fully satisfy all of the properties a blind signature scheme can have. Show more

Keywords: Blind signature, cryptography, DSA, RSA

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 307-320, 2003

Authors: Diaconescu, Răzvan

Article Type: Research Article

Abstract: We generalise the ultraproducts method from conventional model theory to an institution-independent (i.e. independent of the details of the actual logic formalised as an institution) framework based on a novel very general treatment of the semantics of some important concepts in logic, such as quantification, logical connectives, and ground atomic sentences. Unlike previous abstract model theoretic approaches to ultraproducts based on category theory, our work makes essential use of concepts central to institution theory, …such as signature morphisms and model reducts. The institution-independent fundamental theorem on ultraproducts is presented in a modular manner, different combinations of its various parts giving different results in different logics or institutions. We present applications to institution-independent compactness, axiomatizability, and higher order sentences, and illustrate our concepts and results with examples from four different algebraic specification logics. In the introduction we also discuss the relevance of our institution-independent approach to the model theory of algebraic specification and computing science, but also to classical and abstract model theory. Show more

Keywords: Institutions, model theory, algebraic specification, ultraproducts

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 321-348, 2003

Authors: Kandulski, Maciej

Article Type: Research Article

Abstract: We introduce the notion of derived tree corresponding with a derivation in the nonassociative Lambek calculus with product, and examine languages of derived trees determined by categorial grammars employing the calculus as a type reduction system. We prove that the class of derived tree languages of nonassociative Lambek grammars with product contains only regular tree languages.

Keywords: Categorial grammars, Lambek calculus, derived tree languages

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 349-362, 2003

Authors: Li, Sanjiang | Ying, Mingsheng

Article Type: Research Article

Abstract: This paper is mainly concerned with the RCC8 composition table entailed by the Region Connection Calculus (RCC), a well-known formalism for Qualitative Spatial Reasoning. This table has been independently generated by Egenhofer in the context of Geographic Information Systems. It has been known for some time that the table is not extensional for each RCC model. This paper however shows that the Egenhofer model is indeed an extensional one for the RCC8 composition table. Moreover this …model is the maximal extensional one for the RCC8 composition table in a sense. Show more

Keywords: region connection calculus, qualitative spatial reasoning, weak composition, composition table, RCC8 relations, extensionality

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 363-385, 2003

Authors: Weicker, Karsten | Weicker, Nicole

Article Type: Research Article

Abstract: Evolutionary algorithms are often successfully applied to hard optimization problems. However, besides rules of thumb and experience, trial and error is still the leading design technique for evolutionary algorithms. A profound theoretical foundation guiding those applications is still missing. This article outlines a networked understanding of evolutionary algorithms. As a first step towards that goal, it reviews and interrelates major theoretical results and working principles in order to give an extensive insight into the …internal processing of evolutionary algorithms. This not only helps to understand success and failure of evolutionary algorithms in applications but, in addition, could lead to a theory-guided design process enrichening and relieving today's heuristic techniques. Show more

Keywords: evolutionary algorithm, optimization theory, working principles, schema theory

Citation: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 387-403, 2003