Fundamenta Informaticae - Volume 39, issue 4

Authors: Chikalov, Igor

Article Type: Research Article

Abstract: This paper contains some results concerning the properties of decision trees with minimal average depth. The sufficient conditions, which allows for performing a decomposition of problem are given. The class of all information systems, which have linear upper bounds on minimal average weighted depth depending only on entropy, is described. The exponential lower bounds on the number of vertices in branching programs with minimal average weighted depth for some problems are obtained.

Keywords: decision tree, branching program, average time complexity

DOI: 10.3233/FI-1999-39401

Citation: Fundamenta Informaticae, vol. 39, no. 4, pp. 337-357, 1999

Authors: Ejdys, Piotr | Góra, Grzegorz

Article Type: Research Article

Abstract: We consider the average error rate of classification as a function of the number of training examples. We investigate the upper and the lower bounds of this error in a class of commonly used algorithms based on inductive learning from examples. As a result, we arrive at the astonishing conclusion that, contrary to what one could expect, the error rate of some algorithms does not decrease monotonically with number of training examples; rather, it initially increases up to a certain point and only then it starts to decrease. Furthermore, the classification quality of some algorithms is as poor as that …of the naive algorithm. We show that for simple monomials, even if we take an exponentially large training data set, the classification quality of some methods will not be better than if we have taken just one or several training examples. Show more

DOI: 10.3233/FI-1999-39402

Citation: Fundamenta Informaticae, vol. 39, no. 4, pp. 359-374, 1999

Authors: Hage, Jurriaan

Article Type: Research Article

Abstract: Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching classes are equivalence classes of gain graphs under the switching operation. The membership (or equivalence) problem is important to the theory of switching classes. The problem is to …decide for two given skew gain graphs, on the same underlying graph and having gains from the same group, whether or not they belong to the same switching class. We give efficient algorithms. If a certain skew gain graph in the switching class has only abelian gains, then we can reduce the membership problem to an elegant problem on anti-involutions. Finally we show that the word problem can be reduced to the general membership problem, thereby establishing undecidability of the latter for some groups. Show more

Keywords: Switching of graphs, centralizer, bipartite graphs, complexity, groups, graphs

DOI: 10.3233/FI-1999-39403

Citation: Fundamenta Informaticae, vol. 39, no. 4, pp. 375-387, 1999

Authors: Marek, V. Wiktor | Truszczyński, Mirosław

Article Type: Research Article

Abstract: We study properties of rough sets, that is, approximations to sets of records in a database or, more formally, to subsets of the universe of an information system. A rough set is a pair 〈L, U〉 such that L, U are definable in the information system and L ⊆ U. In the paper, we introduce a language, called the language of inclusion-exclusion, to describe incomplete specifications of (unknown) sets. We use rough sets in order to define a semantics for theories in the inclusion-exclusion language. We argue that our concept of a rough set is closely related to that introduced …by Pawlak. We show that rough sets can be ordered by the knowledge ordering (denoted $\preceq$ kn )- We prove that Pawlak's rough sets are characterized as $\preceq$ kn -greatest approximations. We show that for any consistent (that is, satisfiable) theory T in the language of inclusion-exclusion there exists a $\preceq$ kn -greatest rough set approximating all sets X that satisfy T. For some classes of theories in the language of inclusion-exclusion, we provide algorithmic ways to find this best approximation. We also state a number of miscellaneous results and discuss some open problems. Show more

DOI: 10.3233/FI-1999-39404

Citation: Fundamenta Informaticae, vol. 39, no. 4, pp. 389-409, 1999

Authors: Woltert, Prank | Zakharyaschev, Michael

Article Type: Research Article

Abstract: We construct a new concept description language intended for representing dynamic and intensional knowledge. The most important feature distinguishing this language from its predecessors in the literature is that it allows applications of modal operators to all kinds of syntactic terms: concepts, roles and formulas. Moreover, the language may contain both local (i.e., state-dependent) and global (i.e., state-independent) concepts, roles and objects. All this provides us with the most complete and natural means for reflecting the dynamic and intensional behaviour of application domains. We construct a satisfiability checking (mosaic-type) algorithm for this language (based on 𝒜ℒ𝒞) in (i) arbitrary multimodal …frames, (ii) frames with universal accessibility relations (for knowledge) and (iii) frames with transitive, symmetric and euclidean relations (for beliefs). On the other hand, it is shown that the satisfaction problem becomes undecidable if the underlying frames are arbitrary strict linear orders, 〈$\mathbb{N}$ , <〉, or the language contains the common knowledge operator for n ≥ 2 agents. Show more

Keywords: Description logic, modal logic, temporal logic, epistemic logic, decidability

DOI: 10.3233/FI-1999-39405

Citation: Fundamenta Informaticae, vol. 39, no. 4, pp. 411-438, 1999