Fundamenta Informaticae - Volume 152, issue 2

Authors: Polat, Nazan Çakmak | Yaylalı, Gözde | Tanay, Bekir

Article Type: Research Article

Abstract: In this paper the tolerance soft set relation on a soft set is defined and some examples are given with their matrix representations. Also, pre-class and tolerance class concepts for a given tolerance soft set relation are introduced and some examples related to these definitions are illustrated. Some theoretical results are proved such as every pre-class contained by a tolerance class and intersection of two pre-classes is a pre-class as well. Moreover, a method to find out the tolerance classes and pre-classes by using matrix representation of a tolerance soft set relation is explained with examples.

Keywords: Soft set, Soft set relation, Tolerance soft set relation, Matrix representation

DOI: 10.3233/FI-2017-1514

Citation: Fundamenta Informaticae, vol. 152, no. 2, pp. 107-122, 2017

Authors: Koroth, Sajin | Sarma, Jayalal

Article Type: Research Article

Abstract: We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function f is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit (circuits where negations appear only at the leaves) computing f . We prove trade-off results between the depth and the weight/structure of the orientation vectors in any circuit C computing the CLIQUE function on an n vertex graph. We prove that if C is of depth d and each gate computes a Boolean function with orientation …of weight at most w (in terms of the inputs to C ), then d × w must be Ω(n ). In particular, if the weights are o ( n log k n ) , then C must be of depth ω(logk n ). We prove a barrier for our general technique. However, using specific properties of the CLIQUE function (used in Amano Maruoka (2005)) and the Karchmer–Wigderson framework (Karchmer Wigderson (1988)), we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. Asymptotic improvements to our results (in the restricted setting) separates NP from NC. As our main tool, we generalize Karchmer–Wigderson games (Karchmer Wigderson (1988)) for monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function. Show more

DOI: 10.3233/FI-2017-1515

Citation: Fundamenta Informaticae, vol. 152, no. 2, pp. 123-144, 2017

Authors: Mirhosseini, Mina | Nezamabadi-pour, Hossein

Article Type: Research Article

Abstract: The - similarity problem, finding a group of objects which have the most similarity to each other, has become an important issue in information retrieval and data mining. The theory of this concept is mathematically proven, but it practically has high time complexity. Binary Genetic Algorithm (BGA) has been applied to improve solutions quality of this problem, but a more efficient algorithm is required. Therefore, we aim to study and compare the performance of four metaheuristic algorithms called Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA), Imperialist Competitive Algorithm (ICA) and Fuzzy Imperialist Competitive Algorithm (FICA) to tackle this problem. …The experiments are conducted on two applications; the former is on four UCI datasets as a general application and the latter is on the text resemblance application to detect multiple similar text documents from Reuters datasets as a case study. The results of experiments give a ranking of the algorithms in solving the -similarity problem in both applications based on the exploration and exploitation abilities, that the FICA achieves the first rank in both applications as well as based on the both criteria. Show more

Keywords: n- Similarity, text document similarity, particle swarm optimization, gravitational search algorithm, imperialist competition algorithm, fuzzy imperialist competition algorithm

DOI: 10.3233/FI-2017-1516

Citation: Fundamenta Informaticae, vol. 152, no. 2, pp. 145-166, 2017

Authors: Umadevi, Dwaraganathan

Article Type: Research Article

Abstract: In this paper, a characterization for the class of all rough algebras from the class of all Q-rough algebras is obtained.

Keywords: Rough sets, pre-rough algebra, pre Q-rough algebra, rough algebra, Q-rough algebra

DOI: 10.3233/FI-2017-1517

Citation: Fundamenta Informaticae, vol. 152, no. 2, pp. 167-183, 2017

Authors: Zając, Katarzyna

Article Type: Research Article

Abstract: Following a Coxeter spectral analysis problems for positive edge-bipartite graphs (signed multigraphs with a separation property) introduced in [SIAM J. Discr. Math. 27(2013), 827-854] and [Fund. Inform. 123(2013), 447-490], we study analogous problems for loop-free corank two edge-bipartite graphs Δ = (Δ0 ,Δ1 ). i.e. for edge-bipartite graphs Δ, with at least n = 3 vertices such that their rational symmetric Gram matrix G Δ ∈ 𝕄n (ℚ) is positive semi-definite of rank n – 2. We study such connected edge-bipartite graphs by means of the non-symmetric Gram matrix Ğ Δ ∈ 𝕄n (ℤ), …the Coxeter matrix CoxΔ := –Ğ Δ · Ğ Δ –tr , its complex spectrum specc Δ ⊆ ℂ, and an associated simply laced Dynkin diagram DynΔ , with n – 2 vertices. Here ℤ means the ring of integers. It is well-known that if Δ ≈ℤ Δ′ (i.e., there exists B ∈ 𝕄n (ℤ) such that det B = ±1 and Ğ Δ ′ = Btr · Ğ Δ · B ) then specc Δ = specc Δ ′ and DynΔ = DynΔ ′. A complete classification of connected non-negative loop-free edge-bipartite graphs Δ with at most six vertices of corank two, up to the ℤ-congruence Δ ≈ℤ Δ′, is also given. A complete list of representatives of the ℤ-congruence classes of all connected non-negative edge-bipartite graphs of corank two with with at most 6 vertices is constructed; it consists of 1, 2, 2 and 8 edge-bipartite graphs of corank two with 3, 4, 5 and 6 vertices, respectively. Show more

Keywords: edge-bipartite graph, mesh geometry of roots, Dynkin diagram, Coxeter-Dynkin type

DOI: 10.3233/FI-2017-1518

Citation: Fundamenta Informaticae, vol. 152, no. 2, pp. 185-222, 2017