Fundamenta Informaticae - Volume 57, issue 1

Authors: Demolombe, Robert

Article Type: Research Article

Abstract: Answers to queries in terms of abstract objects are defined in the logical framework of first order predicate calculus. A partial algebraic characterisation of the supremum and of the infimum of abstract answers is given in an extended Relational Algebra of the Cylindric Algebra kind. Then, the form of queries is restricted in order to be able to compute answers without the cylindrification operator. For these restricted queries we give a technique to compute an upper …bound and a lower bound of abstract answers using only the operators of the standard Relational Algebra. Show more

Keywords: relational algebra, cylindric algebra, first order logic, abstraction

Citation: Fundamenta Informaticae, vol. 57, no. 1, pp. 1-15, 2003

Authors: Jain, Sanjay

Article Type: Research Article

Abstract: The theory of learning in the limit has been a focus of study by several researchers over the last three decades. There have been several suggestions on how to measure the complexity or hardness of learning. In this paper we survey the work done in one specific such measure, called intrinsic complexity of learning. We will be mostly concentrating on learning languages, with only a brief look at function learning.

Citation: Fundamenta Informaticae, vol. 57, no. 1, pp. 17-37, 2003

Authors: Malerba, Donato

Article Type: Research Article

Abstract: Induction of recursive theories in the normal ILP setting is a difficult learning task whose complexity is equivalent to multiple predicate learning. In this paper we propose computational solutions to some relevant issues raised by the multiple predicate learning problem. A separate-and-parallel-conquer search strategy is adopted to interleave the learning of clauses supplying predicates with mutually recursive definitions. A novel generality order to be imposed on the search space of clauses is …investigated, in order to cope with recursion in a more suitable way. The consistency recovery is performed by reformulating the current theory and by applying a layering technique, based on the collapsed dependency graph. The proposed approach has been implemented in the ILP system ATRE and tested on some laboratory-sized and real-world data sets. Experimental results demonstrate that ATRE is able to learn correct theories autonomously and to discover concept dependencies. Finally, related works and their main differences with our approach are discussed. Show more

Keywords: machine learning, inductive logic programming (ILP), learning recursive theories, multiple predicate learning

Citation: Fundamenta Informaticae, vol. 57, no. 1, pp. 39-77, 2003

Authors: Wang, Shu-Ching | Cheng, Chieng-Fu

Article Type: Research Article

Abstract: The Byzantine Agreement (BA) problem is a fundamental problem to consider in designing a fault-tolerance distributed system. Most BA protocols require all the fault-free processors to reach a common agreement at the same round, called an Immediate Byzantine Agreement (IBA), whereas another type of BA protocol allows the fault-free processors to reach a common agreement, called an Eventual Byzantine Agreement (EBA), at different rounds when they receive enough information. Up to now, all the existing EBA …protocols are designed to solve the EBA problem based on the single failure type assumption (dormant fault only or malicious fault only) as to fallible processors over a reliable fully connected network. However, in practice, most network topologies would not be fully connected, and the underlying network would not be reliable, which means both dormant and malicious faults may occur within the same network simultaneously. In this study, we shall propose a new protocol to solve the EBA problem with dual failure mode on both processors and communication media (both dormant and malicious faults can happen simultaneously to either the processors or the communication media or both) over an unreliable un-fully connected network. The proposed protocol is the optimal when the above assumptions are considered. Show more

Keywords: immediate byzantine agreement, eventual byzantine agreement, distributed computing, parallel processing

Citation: Fundamenta Informaticae, vol. 57, no. 1, pp. 79-99, 2003