Fundamenta Informaticae - Volume 145, issue 1

Authors: Martins, Claudio L.M. | de Oliveira, Pedro P.B.

Article Type: Research Article

Abstract: The understanding of how predefined computations can be attained by means of individual cellular automata rules, their spatial arrangements or their temporal sequences, is a key conceptual underpinning in the general notion of emergent computation. In this context, here we construct a solution to the MODn problem, which is the determination of whether the number of 1-bits in a cyclic binary string is perfectly divisible by the integer n > 1. Our solution is given for any lattice size N that is co-prime to n , and relies upon a set of one-dimensional rules, with maximum radius …of n − 1, organised in a temporal sequence. Although the simpler cases of the problem for n = 2 and n = 3 have been addressed in the literature, this is the first account on the general case, for arbitrary n . Show more

Keywords: Cellular automata, emergent computation, rule composition, modulo-n problem, MODn, active state transitions, parity, classification, decision problem

DOI: 10.3233/FI-2016-1344

Citation: Fundamenta Informaticae, vol. 145, no. 1, pp. 1-17, 2016

Authors: Simson, Daniel

Article Type: Research Article

Abstract: We continue the Coxeter spectral study of the category 𝒰ℬigr m of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ 𝒰ℬigr n + r of corank r ≥ 0, up to a pair of the Gram ℤ-congruences ∼ℤ and ≈ℤ , by means of the non-symmetric Gram matrix G ˇ Δ ∈ 𝕄 n + r …( ℤ ) of Δ, the symmetric Gram matrix G Δ : = 1 2 [ G ˇ Δ + G ˇ Δ t r ] ∈ 𝕄 n + r ( ℤ ) , the Coxeter matrix Cox Δ : = − G ˇ Δ ⋅ G ˇ Δ − t r ∈ 𝕄 n + r ( ℤ ) and its spectrum specc Δ ⊂ ℂ, called the Coxeter spectrum of Δ. One of the aims in the study of the category 𝒰ℬigr n + r is to classify the equivalence classes of the non-negative edge-bipartite graphs in 𝒰ℬigr n + r with respect to each of the Gram congruences ∼ℤ and ≈ℤ . In particular, the Coxeter spectral analysis question, when the strong congruence Δ ≈ ℤ Δ ′ holds (hence also Δ ∼ ℤ Δ ′ holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ 𝒰ℬigr n + r such that specc Δ = specc Δ′ , is studied in the paper. One of our main aims is an algorithmic description of a matrix B defining the Gram ℤ-congruences Δ ≈ ℤ Δ ′ and Δ ∼ ℤ Δ ′ , that is, a ℤ-invertible matrix B ∈ 𝕄 n + r ( ℤ ) such that G ˇ Δ ′ = B t r ⋅ G ˇ Δ ⋅ B and G Δ ′ = B t r ⋅ G Δ ⋅ B , respectively. We show that, given a connected non-negative edge-bipartite graph Δ in 𝒰ℬigr n + r of corank r ≥ 0 there exists a simply laced Dynkin diagram D , with n vertices, and a connected canonical r -vertex extension D ^ : = D ^ ( r ) of D of corank r (constructed in Section 2) such that Δ ~ ℤ D ^ . We also show that every matrix B defining the strong Gram ℤ-congruence Δ ≈ ℤ Δ ′ in 𝒰ℬigr n + r has the form B = C Δ ⋅ B ¯ ⋅ C Δ ′ − 1 , where C Δ , C Δ ′ ∈ M n + r ( ℤ ) are fixed ℤ-invertible matrices defining the weak Gram congruences Δ ~ ℤ D ^ and Δ ′ ~ ℤ D ^ with an r -vertex extended graph D ^ , respectively, and B ¯ ∈ 𝕄 n + r ( ℤ ) is ℤ-invertible matrix lying in the isotropy group G1( n + r , ℤ ) D ^ of D ^ . Moreover, each of the columns k ∈ ℤ n + r of B is a root of ℤ, i.e., k ⋅ G ˇ Δ ⋅ k t r = 1 . Algorithms constructing the set of all such matrices B are presented in case when r = 0. We essentially use our construction of a morsification reduction map ϕ D ^ : U B i g r D ^ → Mor D ^ that reduces (up to ≈ℤ ) the study of the set 𝒰ℬigr D ^ of all connected non-negative edge-bipartite graphs Δ in 𝒰ℬigr n + r such that Δ ~ ℤ D ^ to the study of G1( n + r , ℤ ) D ^ -orbits in the set Mor D ^ ⊆ G1( n + r , ℤ ) of all matrix morsifications of the graph D ^ . Show more

Keywords: signed graph, Gram congruence, Coxeter spectrum, symbolic algorithms, Coxeter-Dynkin type, isotropy group

DOI: 10.3233/FI-2016-1345

Citation: Fundamenta Informaticae, vol. 145, no. 1, pp. 19-48, 2016

Authors: Simson, Daniel

Article Type: Research Article

Abstract: In this two parts article with the same title we continue the Coxeter spectral study of the category 𝒰ℬigr m of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ 𝒰ℬigr n + r of corank r ≥ 0, up to a pair of the Gram ℤ-congruences ∼ℤ and ≈ℤ , by means of the non-symmetric Gram matrix Ğ …Δ ∈ M n + r ( ℤ ) of Δ, the symmetric Gram matrix G Δ : = 1 2 [ Ğ Δ + Ğ Δ t r ] ∈ M n + r ( ℤ ) , the Coxeter matrix Cox Δ : = − Ğ Δ ⋅ Ğ Δ - t r ∈ M n + r ( ℤ ) , its spectrum specc Δ ⊂ ℂ , called the Coxeter spectrum of Δ, and the Dynkin type Dyn Δ ∈ { A n , D n , E 6 , E 7 , E 8 } associated in Part 1 of this paper. One of the aims in the study of the category 𝒰ℬigr n + r is to classify the equivalence classes of the non-negative edge-bipartite graphs in 𝒰ℬigr n + r with respect to each of the Gram congruences ∼ℤ and ≈ℤ . In particular, the Coxeter spectral analysis question, when the congruence Δ ≈ ℤ Δ ′ holds (hence also Δ ~ ℤ Δ ′ holds), for a pair of connected non-negative graphs Δ , Δ ′ ∈ u B i g r n + r such that specc Δ = specc Δ ′ and Dyn Δ = Dyn Δ ′ , is studied in the paper. One of our main aims in this Part 2 of the paper is to get an algorithmic description of a matrix B defining the strong Gram ℤ-congruence Δ ≈ ℤ Δ ′ , that is, a ℤ-invertible matrix B ∈ M n + r ( ℤ ) such that Ğ Δ ′ = B t r ⋅ Ğ Δ ⋅ B . We obtain such a description for a class of non-negative connected edge-bipartite graphs Δ ∈ u B i g r n + r of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group Ğ l ( n + r , ℤ ) Δ : = { B ∈ M n + r ( ℤ ) ;   det   B = ± 1   and   B tr ⋅ Ğ Δ ⋅ B = Ğ Δ } , for a class of edge-bipartite graphs Δ ∈ u B i g r n + r . Using the algorithms, we calculate the isotropy mini-group Ğ l ( n , ℤ ) D and Ğ l ( n + 1 , ℤ ) D ˜ , where D is any of the Dynkin bigraphs A n , ℬ n , 𝒞 n , D n , E 6 , E 7 , E 8 , ℱ 4 , 𝒢 2 and D ˜ is any of the Euclidean graphs A ˜ n , D ˜ n , E ˜ 6 , E ˜ 7 , E ˜ 8 . Show more

Keywords: signed graph, Gram congruence, Coxeter spectrum, symbolic algorithms, Cartan matrix, Coxeter-Dynkin type, isotropy mini-group

DOI: 10.3233/FI-2016-1346

Citation: Fundamenta Informaticae, vol. 145, no. 1, pp. 49-80, 2016

Authors: Shalu, M.A. | Devi Yamini, S.

Article Type: Research Article

Abstract: We consider a new graph operation c 2 -join which generalizes join and co-join. We show that odd hole-free graphs (odd antihole-free graphs) are closed under c 2 -join and describe a polynomial time algorithm to recognize graphs that admit a c 2 -join. The time complexity of the (a ) recognition problem, (b ) maximum weight independent set (MWIS) problem, and (c ) minimum coloring (MC) problem for odd hole-free graphs are still unknown. Let H be an odd hole-free graph that contains an odd antihole as an induced subgraph and 𝒢H be the class of …all graphs generated from the induced subgraphs of H by using c 2 -join recursively. Then 𝒢H is odd hole-free, contains all P 4 -free graphs, complement of all bipartite graphs, and some imperfect graphs. We show that the MWIS problem, maximum weight clique (MWC) problem, MC problem, and minimum clique cover (MCC) problem can be solved efficiently for 𝒢H . Show more

Keywords: c2-join, odd hole-free graphs, modular decomposition, maximum weight independent set problem, maximum weight clique problem, minimum coloring problem, minimum clique cover problem

DOI: 10.3233/FI-2016-1347

Citation: Fundamenta Informaticae, vol. 145, no. 1, pp. 81-91, 2016

Authors: Xu, Jiuping | Qiu, Rui | Tao, Zhimiao

Article Type: Research Article

Abstract: This paper focuses on rough approximation operators in group mapping. The relationships between rough set theory and group theory are considered from a novel perspective. The necessary and sufficient conditions for the upper approximation and lower approximation of a group to be groups are analyzed. In addition, the homomorphism and isomorphism between two groups which have related upper or lower approximations are investigated. Finally, the applications of rough approximation operators in group mapping to coding theory are developed.

Keywords: rough set, lower approximation, upper approximation, group mapping, coding theory

DOI: 10.3233/FI-2016-1348

Citation: Fundamenta Informaticae, vol. 145, no. 1, pp. 93-109, 2016