Fundamenta Informaticae - Volume 136, issue 4

Authors: Creignou, Nadia | Vollmer, Heribert

Article Type: Research Article

Abstract: We consider the weighted satisfiability problem for Boolean circuits and propositional formulæ, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formulæ to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each …such B, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formulæ) or efficiently solvable. We also consider the related enumeration and counting problems. Show more

Keywords: Parameterized complexity, weighted satisfiability, parameterized counting complexity, polynomial-delay enumeration, Post’s lattice

DOI: 10.3233/FI-2015-1159

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 297-316, 2015

Authors: Figallo, Aldo V. | Pelaitay, Gustavo

Article Type: Research Article

Abstract: In 2007, tense Łukasiewicz–Moisil algebras were introduced by Diaconescu and Georgescu as an algebraic counterpart of tense n–valued Moisil logic. These algebras constitute a generalization of tense algebras. In this paper we describe a discrete duality for tense Łukasiewicz–Moisil algebras bearing in mind the results indicated by Dzik, Orłowska and van Alten in 2006, for De Morgan algebras.

Keywords: n–valued Łukasiewicz–Moisil algebras, tense Łukasiewicz–Moisil algebras, tense operators, discrete duality

DOI: 10.3233/FI-2015-1160

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 317-329, 2015

Authors: Grześkowiak, Maciej

Article Type: Research Article

Abstract: Given a square-free integer Δ < 0, we present an algorithm constructing a pair of primes p and q such that q|p + 1 − t and 4p − t2 = Δf2 , where |t| ≤ 2√p for some integers f, t. Together with a CM method presented in the paper, such primes p and q are used for a construction of an elliptic curve E over a finite field $\mathbb{F}_p$ such that the order of E is divisible by a large prime. It is shown that our algorithm works in polynomial time.

Keywords: Elliptic curves over finite field, public key cryptography

DOI: 10.3233/FI-2015-1161

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 331-343, 2015

Authors: Kaniecki, Mariusz | Kosakowska, Justyna | Malicki, Piotr | Marczak, Grzegorz

Article Type: Research Article

Abstract: We construct a horizontal mesh algorithm for a study of a special type of mesh root systems of connected positive loop-free edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense of [SIAM J. Discrete Math. 27 (2013), 827–854] and [Fund. Inform. 124 (2013), 309-338]. Given such a loop-free edge-bipartite graph Δ, with the non-symmetric Gram matrix $\Gcaron_ \Delta \isin \mathbb{M}_n(\mathbb{Z})$ and the Coxeter transformation $\Phi_A : \mathbb{Z}^n \rarr \mathbb{Z}^n$ defined by a quasi-triangular matrix morsification $A \isin \mathbb{M}_n(\mathbb{Z})$ of Δ satisfying a non-cycle condition, our combinatorial algorithm constructs a ΦA -mesh root …system structure $\Gamma(\Rscr_\Delta, \Phi_A)$ on the finite set of all ΦA -orbits of the irreducible root system $\Rscr_\Delta := {v \isin \mathbb{Z}^n; v \cdot \Gcaron_\Delta \cdot v^{tr} = 1}$ . We apply the algorithm to a graphical construction of a ΦI - mesh root system structure $\Gamma(\Rscr_I, \Phi_I)$ on the finite set of ΦI -orbits of roots of any poset I with positive definite Tits quadratic form $\qIcirc : \mathbb{Z}_I \rarr \mathbb{Z}$ . Show more

Keywords: combinatorial algorithm, edge-bipartite graph, Dynkin diagram, root system, mesh translation quiver, quadratic form, Coxeter polynomial

DOI: 10.3233/FI-2015-1162

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 345-379, 2015

Authors: Korpusik, Michał | Łukaszewicz, Witold | Madalińska-Bugaj, Ewa

Article Type: Research Article

Abstract: In this paper we extend a consistency-based approach (originally introduced by Delgrande and Schaub) to belief revision for structured belief bases. We explicitly distinguish between observations, i.e., facts that an epistemic agent observes or is being told, and rules representing general knowledge about the considered world. When new information becomes available respective sets are being altered in a different way to preserve parts of knowledge during the revision process. Such an approach allows us to deal with difficult and complex scenarios, involving defeasible information and derivation filtering, with common-sense results.

DOI: 10.3233/FI-2015-1163

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 381-404, 2015

Authors: Maji, Pradipta | Garai, Partha

Article Type: Research Article

Abstract: Dimensionality reduction of a data set by selecting or extracting relevant and nonredundant features is an essential preprocessing step used for pattern recognition, data mining, machine learning, and multimedia indexing. Among the large amount of features present in real life data sets, only a small fraction of them is effective to represent the data set accurately. Prior to analysis of the data set, preprocessing the data to obtain a smaller set of representative features and retaining the optimal salient characteristics of the data not only decrease the processing time but also lead to more compactness of the models learned and …better generalization. In this regard, a novel dimensionality reduction method is presented here that simultaneously selects and extracts features using the concept of feature significance. The method is based on maximizing both relevance and significance of the reduced feature set, whereby redundancy therein is removed. The method is generic in nature in the sense that both supervised and unsupervised feature evaluation indices can be used for simultaneously feature selection and extraction. The effectiveness of the proposed method, along with a comparison with existing feature selection and extraction methods, is demonstrated on a set of real life data sets. Show more

Keywords: Pattern recognition, data mining, feature selection, feature extraction, classification

DOI: 10.3233/FI-2015-1164

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 405-431, 2015

Authors: Mazzanti, Stefano

Article Type: Research Article

Abstract: Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Consequently, the set of AC0 functions and other canonical complexity classes are defined as the substitution closure of a finite function set.

Keywords: concatenation recursion on notation, substitution basis

DOI: 10.3233/FI-2015-1165

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 433-460, 2015

Authors: Wichert, Andreas | Moreira, Catarina

Article Type: Research Article

Abstract: We investigate exact indexing for high dimensional lp norms based on the 1-Lipschitz property and projection operators. The orthogonal projection that satisfies the 1-Lipschitz property for the lp norm is described. The adaptive projection defined by the first principal component is introduced.

Keywords: 1-Lipschitz property, curse of dimensionality, nearest neighbour, high dimensional indexing, $l_p$ norm

DOI: 10.3233/FI-2015-1166

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 461-474, 2015

Article Type: Other

Citation: Fundamenta Informaticae, vol. 136, no. 4, pp. 475-476, 2015