Fundamenta Informaticae - Volume 10, issue 1

Article Type: Other

DOI: 10.3233/FI-1987-10101

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. i-vii, 1987

Authors: Börger, Egon | Löwen, Ulrich

Article Type: Research Article

Abstract: We survey and give new results on logical characterizations of complexity classes in terms of the computational complexity of decision problems of various classes of logical formulas. There are two main approaches to obtain such results: The first approach yields logical descriptions of complexity classes by semantic restrictions (to e.g. finite structures) together with syntactic enrichment of logic by new expressive means (like e.g. fixed point operators). The second approach characterizes complexity classes by (the decision problem of) classes of formulas determined by purely syntactic restrictions on the formation of formulas.

DOI: 10.3233/FI-1987-10102

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 1-33, 1987

Authors: Wong, S.K.M. | Ziarko, Wojciech

Article Type: Research Article

Abstract: We introduce a new information retrieval model, the generalized vector space model (GVSM). In the GVSM, Boolean-like queries can be transformed into vectors spanned by the atoms of the free Boolean algebra generated by the index terms. Documents can, therefore, be ranked with respect to a query as in the conventional vector space model. Most significantly, the GVSM provides a unified view of the Boolean retrieval and vector-processing systems.

Keywords: Information Storage and Retrieval, Vector Space Model

DOI: 10.3233/FI-1987-10103

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 35-55, 1987

Authors: Orlowska, Ewa

Article Type: Research Article

Abstract: Algebraic methods of proving database constraints are proposed. The first method is based on the formulation of constraints in terms of inclusions of some binary relations associated with database. The relations are generated by indiscernibility relations by means of the operations of the algebra of binary relations. The second method is based on the matrix representation of constraints.

DOI: 10.3233/FI-1987-10104

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 57-68, 1987

Authors: Păun, Gheorghe | Novotný, Miroslav

Article Type: Research Article

Abstract: J. Ostravský considered two classes of languages – BS and BC – and described an effective construction assigning a pure grammar Gj k (V,L) to any j∈{s,c}, to any language (V,L), and to any integer k⩾1. He proved that (V,L)∈Bj if and only if there exists k0 ⩾1 such that Gj k (V,L) = Gj k0 (V,L) for any k⩾k0 . The least integer k0 with this property is a complexity measure of the language (V,L)∈Bj . Besides this complexity measure, we study another one introduced in connection with the above mentioned construction. We compare …the complexity of languages with the complexity of languages obtained by usual operations from the given ones. Show more

Keywords: pure grammar, s-grammatizable language, c-grammatizable language, minimum k zero of the language, maximum preequality of the language, s-faithful language, c-faithful language

DOI: 10.3233/FI-1987-10105

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 69-80, 1987

Authors: Michalewicz, Zbigniew

Article Type: Research Article

Abstract: We consider the problem of compromisability of a statistical database. This paper is an attempt to evaluate the implications of using “yes-no” queries instead of the usual statistical queries; for this purpose we solve a certain coin-weighing problem.

DOI: 10.3233/FI-1987-10106

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 81-91, 1987

Authors: Cockett, J.R.B.

Article Type: Research Article

Abstract: A basic concern when using decision trees for the solution of taxonomic or similar problems is their efficiency. Often the information that is required to completely optimize a tree is simply not available. This is especially the case when a criterion based on probabilities is used. It is shown how it is often possible, despite the absence of this information, to improve the design of the tree. The approach is based on algebraic methods for manipulating decision trees and the identification of some particularly desirable forms.

DOI: 10.3233/FI-1987-10107

Citation: Fundamenta Informaticae, vol. 10, no. 1, pp. 93-114, 1987