Fundamenta Informaticae - Volume 18, issue 1

Article Type: Other

DOI: 10.3233/FI-1993-18101

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. i-vii, 1993

Authors: Pagliani, Piero

Article Type: Research Article

Abstract: The paper presents general logic-algebraic structures related to Wille’s Concept Lattices, Pawlak’s theory of Information Systems and Approximation Spaces. These structures are studied in order to analyse increasing concepts definitions and decreasing objects identifications. Here they are investigated starting from the notions of polarity and quantum at a point , applying the approach used in Bell’s representation theorem for ortholattices and the mathematical tools provided by pointless topology. In this way we intend to connect this analysis to the notion of topology of positive information introduced in Scott’s Information Systems and Scott’s Domains. In particular, notions connected to …the concept of ‘objects definition improvement’ (via attributes, or parameters) are algebraically investigated in order to analyse general and particular characteristics of Information Systems and a related classification for them is proposed. Show more

DOI: 10.3233/FI-1993-18102

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. 1-25, 1993

Authors: Kari, Lila

Article Type: Research Article

Abstract: The customary language-theoretic derivative of a word u with respect to a word v means the deletion of v from the beginning or end of u . We investigate the natural generalization, where v can be deleted from an arbitrary position in u . Apart from general closure and decidability properties, we pay special attention to regular languages, obtaining an exhaustive characterization.

DOI: 10.3233/FI-1993-18103

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. 27-39, 1993

Authors: Komorowski, Jan

Article Type: Research Article

Abstract: Partial deduction is a specialization principle related to the law of syllogism. It has several computational applications in logic programming but it has been recently also used in deductive databases, machine learning, software synthesis and other areas of computing. This article is a systematic introduction to partial deduction, its applications and open problems. Starting from an informal and intuitive presentation, the fundamental notions such as correctness and completeness are discussed. A selection of applications is presented to illustrate partial deduction in different contexts.

DOI: 10.3233/FI-1993-18104

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. 41-64, 1993

Authors: Stewart, Iain A.

Article Type: Research Article

Abstract: We consider three sub-logics of the logic (±HP )*[FO s ] and show that these sub-logics capture the complexity classes obtained by considering logspace deterministic oracle Turing machines with oracles in NP where the number of oracle calls is unrestricted and constant, respectively; that is, the classes LNP and LNP [O (1)]. We conclude that if certain logics are of the same expressibility then the Polynomial Hierarchy collapses. We also exhibit some new complete problems for the complexity class LNP via projection translations (the first to be discovered: projection translations are extremely weak logical reductions between problems) …and characterize the complexity class LNP [O (1)] as the closure of NP under a new, extremely strict truth-table reduction (which we introduce in this paper). Show more

DOI: 10.3233/FI-1993-18105

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. 65-92, 1993

Authors: Stewart, Iain A.

Article Type: Research Article

Abstract: This paper continues an investigation into the expressibility of the logic (±HP )*[FO S ]. In particular, we show that the logic (±HP )*[FO S ] has the same expressibility as its sub-logic (±HP )1 [FO S ] which is known to capture the complexity class LNP (this class being those sets of strings accepted by some logspace deterministic oracle Turing machine with an oracle in NP). We consequently show that a naturally defined hierarchy within PNP collapses.

DOI: 10.3233/FI-1993-18106

Citation: Fundamenta Informaticae, vol. 18, no. 1, pp. 93-105, 1993