Fundamenta Informaticae - Volume 59, issue 4

Authors: Baaz, Matthias | Ciabattoni, Agata | Montagna, Franco

Article Type: Research Article

Abstract: Monoidal t-norm based logic MTL is the logic of left continuous t-norms. We introduce two analytic calculi for first-order MTL. These are obtained by lifting two sequent calculi for different fragments of this logic to the hypersequent level with subsequent addition of Avron's communication rule. Our calculi enable to prove the mid(hyper)sequent theorem. As corollaries follow Herbrand's theorem for first-order MTL, the decidability of its ∀∃-fragment and admissibility of Skolemization.

Keywords: basic fuzzy logics, monoidal t-norm based logic, hypersequent calculi, mid(hyper)sequent theorem

Citation: Fundamenta Informaticae, vol. 59, no. 4, pp. 315-332, 2004

Authors: Dobrev, Stefan | Pelc, Andrzej

Article Type: Research Article

Abstract: We consider the leader election problem in a ring whose nodes have possibly nonunique labels. Every node knows a priori its own label and two integers, m and M, which are, respectively, a lower and an upper bound on the (unknown) size n of the ring. The aim is to decide whether leader election is possible and to perform it, if so. We consider both the synchronous and the asynchronous version of the problem and we are interested in message …complexity in both cases. For the synchronous version we present an algorithm using O(n log n) messages and working in time O(M). Moreover, our algorithm uses O(n) messages when all identifiers are distinct. For the asynchronous version we show an Ω(nM) lower bound on message complexity for this problem, and present an algorithm for it using O(nM) messages. Show more

Keywords: distributed algorithms, leader election, ring network

Citation: Fundamenta Informaticae, vol. 59, no. 4, pp. 333-347, 2004

Authors: Domaratzki, Michael

Article Type: Research Article

Abstract: We generalize the embedding order to shuffle on trajectories and examine its properties. We give general characterizations of reflexivity, transitivity, anti-symmetry and other properties of binary relations, and investigate the associated decision problems. We also examine the property of convexity of a language with respect to these generalized embedding relations.

Keywords: embedding order, shuffle on trajectories, convexity

Citation: Fundamenta Informaticae, vol. 59, no. 4, pp. 349-363, 2004

Authors: Hartmann, Sven | Link, Sebastian | Schewe, Klaus-Dieter | Thalheim, Bernhard

Article Type: Research Article

Abstract: A database user may be confronted with a relation that contains errors. These errors may result from transmission through a noisy channel, or they may have been added deliberately in order to hide or spoil information. Error-robust functional dependencies provide dependencies that still hold in the case of errors. The paper investigates the finite axiomatisation of such dependencies. It presents a sound and complete system of axioms and rules for the implication of error-robust dependencies including …disjunctions. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 59, no. 4, pp. 365-372, 2004

Authors: Moschoyiannis, Sotiris | Shields, Michael W.

Article Type: Research Article

Abstract: Modern software systems become increasingly complex as they are expected to support a large variety of different functions. We need to create more software in a shorter time, and without compromising the quality of the software. In order to build such systems efficiently, a compositional approach is required. This entails some formal technique for analysis and reasoning on local component properties as well as on properties of the composite. In this paper, we present a mathematical …framework for the composition of software components, at a semantic modelling level. We describe a mathematical concept of a component and identify properties that ensure its potential behaviour can be captured. Based on that, we give a formal definition of composition and examine its effect on the individual components. We argue that properties of the individual components can, under certain conditions, be preserved in the composite. The proposed framework can be used for guiding the composition of components as it advocates formal reasoning about the composite before the actual composition takes place. Show more

Keywords: components, composition, associativity, normality, order theory, vector semantics

Citation: Fundamenta Informaticae, vol. 59, no. 4, pp. 373-396, 2004