Fundamenta Informaticae - Volume 139, issue 2

Authors: Alatabbi, Ali | Daykin, Jacqueline W. | Rahman, M. Sohel | Smyth, William F.

Article Type: Research Article

Abstract: In this paper we focus on a total (but non-lexicographic) ordering of strings called V -order. We devise a new linear-time algorithm for computing the V -comparison of two finite strings. In comparison with the previous algorithm in the literature, our algorithm is both conceptually simpler, based on recording letter positions in increasing order, and more straightforward to implement, requiring only linked lists.

Keywords: algorithm, array, comparison, complexity, data structure, lexicographic order, linear, linked-list, V-order, Lyndon word, string, total order, word

DOI: 10.3233/FI-2015-1228

Citation: Fundamenta Informaticae, vol. 139, no. 2, pp. 115-126, 2015

Authors: Desai, Santosh S. | Chaudhari, Shrikant R.

Article Type: Research Article

Abstract: Many researchers have studied the rationality of fuzzy choice functions with transitive rationalization. However, not much is known when transitivity is weakened to quasi-transitivity or any other weaker property of the preference relation. In the present paper we study the rationality of fuzzy choice functions with quasi-transitive rationalization for the domains that contain characteristic functions of all single and two element subsets of the universal set.

Keywords: Fuzzy choice function, Base domain, Fuzzy Q- and D-congruence axiom, Sen’s quasi condition, Q-rational fuzzy choice functions

DOI: 10.3233/FI-2015-1229

Citation: Fundamenta Informaticae, vol. 139, no. 2, pp. 127-151, 2015

Authors: Kasjan, Stanisław | Simson, Daniel

Article Type: Research Article

Abstract: This is the first part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category 𝒰 ℬ i g r n of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category ℛ ℬ i g r n of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~Z and ≈Z . The positive graphs Δ in ℛ ℬ i g …r n , with dotted loops, are studied by means of the complex Coxeter spectrum s p e c c Δ   ⊂ ℂ , the irreducible mesh root systems of Dynkin types 𝔹 n ,   n ≥ 2 , ℂ n ,   n ≥ 3 ,   𝔽 4 ,   𝔾 2 , the isotropy group Gl(n , ℤ)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of the paper is to study the Coxeter spectral analysis question: “Does the congruence Δ ≈ℤ Δ′ hold, for any pair of connected positive graphs Δ ,   Δ ′ ∈ ℛ ℬ i g r n such that spec c Δ = spec c Δ ′ and the numbers of loops in Δ and Δ′ coincide? ” We do it by a reduction to the Coxeter spectral study of the G1 ( n ,   ℤ ) D -orbits in the set M o r D   ⊂   𝕄 n ( ℤ ) of matrix morsifications of a Dynkin diagram D = D Δ ∈ 𝒰 B i g r n associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in ℛ ℬ i g r n , for a fixed n ≥ 2, mesh algorithms for computing the set of all ℤ-invertible matrices B ∈ G1 ( n ,   ℤ ) definining the ℤ-congruence Δ ≈ ℤ Δ ' , for positive graphs Δ ,   Δ ′ ∈ ℛ ℬ i g r n , with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems Γ ( R Δ • , Φ Δ ) . In the first part of the paper we present an introduction to the study of Cox-regular edge-bipartite graphs Δ with dotted loops in relation with the irreducible reduced root systems and the Dynkin diagrams ℬ n ,   n ≥ 2 ,   ℂ n ,   n ≥ 3 ,   𝔽 4 , 𝔾 2 . Moreover, we construct a unique ΦD -mesh root system Γ ( R D • ,   Φ D ) for each of the Cox-regular edge-bipartite graphs ℬ n ,   n ≥ 2 ,   C n ,   n ≥ 3 ,   ℱ 4 ,   c a l 𝒢 2 of the type ℬ n ,   n ≥ 2 ,   ℂ n ,   n ≥ 3 ,   𝔽 4 , 𝔾 2 , respectively. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. Show more

Keywords: Edge-bipartite graph, Dynkin diagram, morsification, Coxeter spectrum, Coxeter-Gram polynomial, mesh root system, mesh algorithm

DOI: 10.3233/FI-2015-1230

Citation: Fundamenta Informaticae, vol. 139, no. 2, pp. 153-184, 2015

Authors: Kasjan, Stanisław | Simson, Daniel

Article Type: Research Article

Abstract: This is the second part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category 𝒰 ℬ i g r n of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category ℛ ℬ i g r n of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~Z and ≈Z . The positive graphs Δ in ℛ ℬ i g …r n , with dotted loops, are studied by means of the complex Coxeter spectrum s p e c c Δ   ⊂ ℂ , the irreducible mesh root systems of Dynkin types 𝔹 n ,   n ≥ 2 , ℂ n ,   n ≥ 3 ,   𝔽 4 ,   𝔾 2 , the isotropy group Gl(n , ℤ)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of our two part paper is to study the Coxeter spectral analysis question: “Does the congruence Δ ≈ℤ Δ′ hold, for any pair of connected positive graphs Δ ,   Δ ′ ∈ ℛ ℬ i g r n such that spec c Δ = spec c Δ ′ and the numbers of loops in Δ and Δ′ coincide? ” We do it by a reduction to the Coxeter spectral study of the G1 ( n ,   ℤ ) D -orbits in the set M o r D   ⊂   𝕄 n ( ℤ ) of matrix morsifications of a Dynkin diagram D = D Δ ∈ 𝒰 B i g r n associated with Δ. In this second part, we construct numeric algorithms for computing the connected positive edge-bipartite graphs Δ in ℛ ℬ i g r n , for a fixed n ≥ 2, mesh algorithms for computing the set of all ℤ-invertible matrices B ∈ G1 ( n ,   ℤ ) definining the ℤ-congruence Δ ≈ ℤ Δ ' , for positive graphs Δ ,   Δ ′ ∈ ℛ ℬ i g r n , with ngeq 2 fixed, and mesh-type algorithms for the mesh root systems Γ ( R Δ • , Φ Δ ) . We also present a classification and a structure type results for positive Cox-regular edge-bipartite graphs Δ with dotted loops. Show more

Keywords: edge-bipartite graph, Dynkin diagram, morsification, Coxeter spectrum, Coxeter-Gram polynomial, mesh root system, mesh algorithm

DOI: 10.3233/FI-2015-1231

Citation: Fundamenta Informaticae, vol. 139, no. 2, pp. 185-209, 2015

Authors: Macías-Ramos, Luis F. | Valencia-Cabrera, Luis | Song, Bosheng | Song, Tao | Pan, Linqiang | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Inspired by mitosis process and membrane fission processes, cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules have been introduced, respectively. These computation systems have two key features: the ability to have infinite copies of some objects (within an active environment) and to generate an exponential workspace in polynomial time. In this work, we extend the P-Lingua framework for simulating that kind of P systems taking into account these two features. Consequently, a new simulator has been developed and included in pLinguaCore library. The functioning of the simulator has been checked by simulating efficient solutions …to SAT problem using a family of cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules. The corresponding MeCoSim based application is also provided. Show more

Keywords: Bio-inspired Computing, Membrane Computing, P System, P-Lingua, MeCoSim

DOI: 10.3233/FI-2015-1232

Citation: Fundamenta Informaticae, vol. 139, no. 2, pp. 211-227, 2015