Fundamenta Informaticae - Volume 99, issue 3

Authors: Georgescu, Irina

Article Type: Research Article

Abstract: The Arrow index of a fuzzy choice function C is a measure of the degree to which C satisfies the Fuzzy Arrow Axiom, a fuzzy version of the classical Arrow Axiom. The main result of this paper shows that A(C) characterizes the degree to which C is full rational. We also obtain a method for computing A(C). The Arrow index allows to rank the fuzzy choice functions with respect to their rationality. Thus, if for solving a decision problem …several fuzzy choice functions are proposed, by the Arrow index the most rational one will be chosen. Show more

Keywords: fuzzy choice function, revealed preference indicator, congruence indicator, similarity

DOI: 10.3233/FI-2010-248

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 245-261, 2010

Authors: Jen, Tao-Yuan | Laurent, Dominique | Spyratos, Nicolas

Article Type: Research Article

Abstract: The problem of mining all frequent queries on a relational table is a problem known to be intractable even for conjunctive queries. In this article, we restrict our attention to conjunctive projection-selection queries and we assume that the table to be mined satisfies a set of functional dependencies. Under these assumptions, we define and characterize two pre-orderings with respect to which the support measure is shown to be anti-monotonic. Each of these pre-orderings induces an equivalence …relation for which all queries of the same equivalence class have the same support. The goal of this article is not to provide algorithms for the computation of frequent queries, but rather to provide basic properties of pre-orderings and their associated equivalence relations showing that functional dependencies can be used for an optimized computation of supports of conjunctive queries. In particular, we show that one of the two pre-orderings characterizes anti-monotonicity of the support, while the other one refines the former, but allows to characterize anti-monotonicity with respect to a given table, only. Basic computational implications of these properties are discussed in the article. Show more

Keywords: Functional dependencies, data mining, level-wise algorithms, frequent queries, equivalent queries

DOI: 10.3233/FI-2010-249

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 263-292, 2010

Authors: Jiang, Feng | Sui, Yuefei | Cao, Cungen

Article Type: Research Article

Abstract: Formal concept analysis (FCA) is a mathematical description and theory of concepts implied in formal contexts. And the current formal contexts of FCA aim to model the binary relations between individuals (objects) and attributes in the real world. In the real world we usually describe each individual by some attributes, which induces the relations between individuals and attributes. But there also exist many relations between individuals, for instance, the parent-children relation in a family. In this …paper, to model the relations between individuals in the real world, we propose a new context – relational context for FCA, which contains a set U of objects and a binary relation r on U. Corresponding to the formal concepts in formal contexts, we present different kinds of relational concepts in relational contexts, which are the pairs of sets of objects. First we define the standard relational concepts in relational contexts. Moreover, we discuss the indirect relational concepts and negative relational concepts in relational contexts, which aim to concern the indirection and negativity of the relations in relational contexts, respectively. Finally, we define the hybrid relational concepts in relational contexts, which are the combinations of any two different kinds of relational concepts. In addition, we also discuss the application of relational contexts and relational concepts in the supply chain management field. Show more

Keywords: FCA, formal contexts, relational contexts, relational concepts, concept lattices, supply chain

DOI: 10.3233/FI-2010-250

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 293-314, 2010

Authors: Majumder, Subhashis | Nandy, Subhas C. | Bhattacharya, Bhargab B.

Article Type: Research Article

Abstract: In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the …partition. Show more

Keywords: Monochromatic partitioning, NP-hardness, Heuristic, Vertex Cover

DOI: 10.3233/FI-2010-251

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 315-324, 2010

Authors: Okhotin, Alexander

Article Type: Research Article

Abstract: It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2^{n/2-2} states (the known upper bound is 2^n ), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2^{sqrt{2n+30}-6} states. A similar state complexity function for scattered superstrings is determined to be exactly 2^{n-2} + 1 for an …alphabet of at least n − 2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least 1/5 4sqrt{n/2}n-3/4. Show more

Keywords: descriptional complexity, finite automata, state complexity, substring, subword, subsequence, Higman–Haines sets

DOI: 10.3233/FI-2010-252

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 325-338, 2010

Authors: Rytsar, Bohdan | Romanowski, Piotr | Shvay, Adrian

Article Type: Research Article

Abstract: In this paper a creation of new numerical set-theoretical constructions of Boolean functions with their properties has been presented. The parted conjuncterms and decomposition clones which can be used for realization of different optimization logic synthesis of digital devices and systems have been proposed. Set theoretical operations and procedures with these constructions have been considered. Examples which illustrate simplicity of their practical realization have been presented. Moreover, the paper includes the comparison …of new results obtained on the basis of the proposed approach with the results obtained by means of commercial software Quartus II of Altera. Show more

Keywords: Boolean function, set-theoretical constructions, decomposition, parted conjuncterm, decomposition clone

DOI: 10.3233/FI-2010-253

Citation: Fundamenta Informaticae, vol. 99, no. 3, pp. 339-354, 2010