Fundamenta Informaticae - Volume 55, issue 1

Authors: Bloom, Stephen L. | Ésik, Zoltán

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 55, no. 1, pp. 1-21, 2003

Authors: Champarnaud, Jean-Marc | Coulon, Fabien

Article Type: Research Article

Abstract: We can represent the canonical automaton of a language as the smallest automaton which contains any other automaton recognizing this language, providing equivalent states are merged. Indeed, the canonical automaton appears to be a good representative element in the equivalence class of non-deterministic automata recognizing a given language. Our aim is to provide a detailed description of the canonical automaton based on the notions of syntactical rectangle and characteristic event. In our approach, a state of …the canonical automaton of a language ℒ is associated with a rectangle (L,R)⊆Σ^*×Σ^*, which is maximal w.r.t. the property L.R⊆ℒ. We explicit the link with other characterizations, like considering a state as a residual intersection which was given by Arnold et al., and the fundamental automaton defined by Matz and Potthoff. In particular, we pretend that the construction of the canonical automaton has the same time complexity as the construction of the fundamental automaton. Our last section briefly discusses the problem of searching minimal NFAs using the canonical automaton. Show more

Keywords: Canonical/fundamental automaton, nondeterministic automata, NFA minimization, grid cover, characteristic event

Citation: Fundamenta Informaticae, vol. 55, no. 1, pp. 23-38, 2003

Authors: Dinu, Liviu P.

Article Type: Research Article

Abstract: In this paper we present an aggregation method which can be applied to classifications having different vocabularies. The method uses the rank distance (Dinu, 2003), a metric which measures the similarity between two hierarchies based on the ranks of objects. We define the aggregation of n hierarchies as the classification for which the sum of distances from it to each of the n hierarchies is minimal. We study some of his rationality properties and propose some …open problems. Show more

Keywords: rank distance, classification, aggregation, rationality conditions

Citation: Fundamenta Informaticae, vol. 55, no. 1, pp. 39-50, 2003

Authors: Moshkov, Mikhail Ju.

Article Type: Research Article

Abstract: We investigate infinite information systems. Such systems are widely used in pattern recognition, data mining, discrete optimization, computational geometry. An information system is called compressible relatively to a given weight function if for each problem over the information system with sufficiently large weight (i.e., total weight of attributes in the problem description) there exists a decision tree (i) solving this problem and (ii) having the weighted depth less than the problem weight. In the paper all …pairs (information system, weight function) such that the information system is compressible relatively to the weight function are described. For each such pair the behavior of Shannon type function is investigated characterizing the growth in the worst case of the minimal weighted depth of decision trees with the growth of problem weight. Show more

Keywords: information system, decision tree, weighted depth

Citation: Fundamenta Informaticae, vol. 55, no. 1, pp. 51-61, 2003

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: We propose a modal logic programming language called MProlog, which is as expressive as the general modal Horn fragment. We give a fixpoint semantics and an SLD-resolution calculus for MProlog in all of the basic serial modal logics KD, T, KDB, B, KD4, S4, KD5, KD45, and S5. For an MProlog program P and for L being one of the mentioned logics, we define an operator T_{L,P}, which has the least fixpoint I_{L,P}. This fixpoint is a set of …formulae, which may contain labeled forms of the modal operator ⋄, and is called the least L-model generator of P. The standard model of I_{L,P} is shown to be a least L-model of P. The SLD-resolution calculus for MProlog is designed with a similar style as for classical logic programming. It is sound and complete. We also extend the calculus for MProlog in the almost serial modal logics KB, K5, K45, and KB5. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 55, no. 1, pp. 63-100, 2003