Browsing by Author "Lin, Song-Sun"

Now showing 1 - 15 of 15

NONEMPTINESS PROBLEMS OF PLANE SQUARE TILING WITH TWO COLORS
(2011-03-01)
Hu, Wen-Guei
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
This investigation studies nonemptiness problems of plane square tiling. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges of p colors are arranged side by side such that adjacent tiles have the same colors. Given a set of Wang tiles B, the nonemptiness problem is to determine whether or not Sigma(B) not equal theta, where Sigma(B) is the set of all global patterns on Z(2) that can be constructed from the Wang tiles in B. When p >= 5, the problem is well known to be undecidable. This work proves that when p = 2, the problem is decidable. P(B) is the set of all periodic patterns on Z(2) that can be generated by B. If P(B) not equal empty set, then s has a subset B' of minimal cycle generator such that P(B') not equal empty set and P(B '') = empty set for B '' subset of B'. This study demonstrates that the set of all minimal cycle generators C(2) contains 38 elements. N(2) is the set of all maximal noncycle generators: if B is an element of N(2), then P(B) = empty set and (B) over tilde superset of B implies P (B) over tilde) not equal empty set. N(2) has eight elements. That Sigma (B) = theta for any B is an element of N(2) is proven, implying that if Sigma(B) not equal empty set, then P(B) not equal empty set. The problem is decidable for p = 2: Sigma(B) not equal empty set if and only if B has a subset of minimal cycle generators. The approach can be applied to corner coloring with a slight modification, and similar results hold.
Nonemptiness problems of Wang tiles with three colors
(2014-08-28)
Chen, Hung-Hsun
;
Hu, Wen-Guei
;
Lai, De-Jan
;
Lin, Song-Sun
;
應用數學系
This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not Sigma(B) not equal empty set , where Sigma(B) is the set of all global patterns on Z(2) that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B of Wang tiles, Sigma (B) not equal empty set if and only if P(B) not equal empty set, where P(B) is the set of all periodic patterns on Z(2) that can be generated by the tiles in B. When p >= 5, Wang's conjecture is known to be wrong. When p = 2, the conjecture is true. This study proves that when p = 3, the conjecture is also true. If P(B) not equal empty set, then B has a subset B' of minimal cycle generators such that P(B') not equal empty set and P(B '') not equal empty set for B '' B'. This study demonstrates that the set C(3) of all minimal cycle generators contains 787, 605 members that can be classified into 2, 906 equivalence classes. N(3) is the set of all maximal non-cycle generators: if B is an element of N(3), then P(B) not equal empty set and P((B) over tilde) not equal empty set for (B) over tilde B. Wang's conjecture is shown to be true by proving that B is an element of N(3) implies Sigma(B) = empty set. (C) 2014 Elsevier B.V. All rights reserved.
Nonemptiness problems of Wang tiles with three colors
(2014-08-28)
Chen, Hung-Hsun
;
Hu, Wen-Guei
;
Lai, De-Jan
;
Lin, Song-Sun
;
應用數學系
This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not Sigma(B) not equal empty set , where Sigma(B) is the set of all global patterns on Z(2) that can be constructed from the Wang tiles in B. Wang\'s conjecture is that for any B of Wang tiles, Sigma (B) not equal empty set if and only if P(B) not equal empty set, where P(B) is the set of all periodic patterns on Z(2) that can be generated by the tiles in B. When p >= 5, Wang\'s conjecture is known to be wrong. When p = 2, the conjecture is true. This study proves that when p = 3, the conjecture is also true. If P(B) not equal empty set, then B has a subset B\' of minimal cycle generators such that P(B\') not equal empty set and P(B \'\') not equal empty set for B \'\' B\'. This study demonstrates that the set C(3) of all minimal cycle generators contains 787, 605 members that can be classified into 2, 906 equivalence classes. N(3) is the set of all maximal non-cycle generators: if B is an element of N(3), then P(B) not equal empty set and P((B) over tilde) not equal empty set for (B) over tilde B. Wang\'s conjecture is shown to be true by proving that B is an element of N(3) implies Sigma(B) = empty set. (C) 2014 Elsevier B.V. All rights reserved.
ON SPATIAL ENTROPY OF MULTI-DIMENSIONAL SYMBOLIC DYNAMICAL SYSTEMS
(2016-07)
Hu, Wen-Guei
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
The commonly used topological entropy h(top) (U) of the multidimensional shift space U is the rectangular spatial entropy h(r) (U) which is the limit of growth rate of admissible local patterns on finite rectangular sub-lattices which expands to whole space Z(d), d >= 2. This work studies spatial entropy h(Omega)(U) of shift space U on general expanding system Omega = {Omega(n)}(n=1)(infinity) where Omega(n) is increasing fi nite sublattices and expands to Z(d). Omega is called genuinely d-dimensional if Omega(n) contains no lower-dimensional part whose size is comparable to that of its d-dimensional part. We show that h(r)(U) is the supremum of h(Omega)(U) for all genuinely d-dimensional Omega. Furthermore, when Omega is genuinely d-dimensional and satis fi es certain conditions, then h(Omega) (U) = h(r)(U). On the contrary, when Omega(n) contains a lower-dimensional part which is comparable to its d-dimensional part, then h r (U) < h(Omega)(U) for some U. Therefore, h(r)(U) is appropriate to be the d-dimensional spatial entropy.
On the structure of multi-layer cellular neural networks
(2012-04-15)
Ban, Jung-Chao
;
Chang, Chih-Hung
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
Let Y subset of {-1, 1}(Z infinity xn) be the mosaic solution space of an n-layer cellular neural network. We decouple Y into n subspaces, say Y-(1), Y-(2), ... , Y-(n), and give a necessary and sufficient condition for the existence of factor maps between them. In such a case, Y-(i) is a sofic shift for 1 <= i <= n. This investigation is equivalent to study the existence of factor maps between, two sofic shifts. Moreover, we investigate whether Y-(i) and Y-(j) are topological conjugate, strongly shift equivalent, shift equivalent, or finitely equivalent via the well-developed theory in symbolic dynamical systems. This clarifies, in a multi-layer cellular neural network, each layer's structure. As an extension, we can decouple Y into arbitrary k-subspaces. where 2 <= k <= n, and demonstrates each subspace's structure. (C) 2012 Elsevier Inc. All rights reserved.
On the Structure of Two-Layer Cellular Neural Networks
(2013)
Ban, Jung-Chao
;
Chang, Chih-Hung
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
Let Y subset of{-1,1}(Z infinity x2) be the mosaic solution space of a two-layer cellular neural network (TCNN). We decouple Y into two subspaces, say Y-(1) and Y-(2), and give a necessary and sufficient condition for the existence of factor maps between them. In such a case, Y-(i) is a sofic shift for i = 1,2. This investigation is equivalent to study the existence of factor maps between two sofic shifts. Moreover, we investigate whether Y-(1) and Y-(2) are topological conjugate, strongly shift equivalent, shift equivalent, or finitely equivalent via the well-developed theory in symbolic dynamical systems. This clarifies, in a TCNN, each layer\'s structure.
Pattern generation problems arising in multiplicative integer systems
(2019-05-01)
Ban, Jung-Chao
;
Hu, Wen-Guei
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
This study investigates a multiplicative integer system, an invariant subset of the full shift under the action of the semigroup of multiplicative integers, by using a method that was developed for studying pattern generation problems. The spatial entropy and the Minkowski dimensions of general multiplicative systems can thus be computed. A coupled system is the intersection of a multiplicative integer system and the golden mean shift, which can be decoupled by removing the multiplicative relation set and then performing procedures similar to those applied to a decoupled system. The spatial entropy can be obtained after the remaining error term is shown to approach zero.
Patterns generation and spatial entropy in two-dimensional lattice models
(2007-09-01)
Ban, Jung-Chao
;
Lin, Song-Sun
;
Lin, Yin-Heng
;
應用數學系
;
Department of Applied Mathematics
Patterns generation problems in two-dimensional lattice models are studied. Let S be the set of p symbols and Z(2lx2l), l >= 1, be a fixed finite square sublattice of Z(2). Function U : Z(2lx2l) -> S is called local pattern. Given a basic set B of local patterns, a unique transition matrix A(2) which is a q(2)xq(2) matrix, q = p(l2), can be defined. The recursive formulae of higher transition matrix A(n) on Z(2lxnl) have already been derived [4]. Now A(n)(m), m >= 1, contains all admissible patterns on Z((m+1)lxnl) which can be generated by B. In this paper, the connecting operator C-m, which comprises all admissible patterns on Z((m+1)lx2l), is carefully arranged. C-m can be used to extend A(n)(m) to A(n+1)(m) recursively for n >= 2. Furthermore, the lower bound of spatial entropy h(A(2)) can be derived through the diagonal part of C-m. This yields a powerful method for verifying the positivity of spatial entropy which is important in examining the complexity of the set of admissible global patterns. The trace operator T-m of C-m can also be introduced. In the case of symmetric A(2), T-2m gives a good estimate of the upper bound on spatial entropy. Combining C-m with T-m helps to understand the patterns generation problems more systematically.
Smooth solutions of the one-dimensional compressible Euler equation with gravity
(2016-01-05)
Hsu, Cheng-Hsiung
;
Lin, Song-Sun
;
Yang, Chi-Ru
;
應用數學系
;
Department of Applied Mathematics
We study one-dimensional motions of polytropic gas governed by the compressible Euler equations. The problem on the half space under a constant gravity gives an equilibrium which has free boundary touching the vacuum and the linearized approximation at this equilibrium gives time periodic solutions. But it is difficult to justify the existence of long-time true solutions for which this time periodic solution is the first approximation. The situation is in contrast to the problem of free motions without gravity. The reason is that the usual iteration method for quasilinear hyperbolic problem cannot be used because of the loss of regularities which causes from the touch with the vacuum. Due to this reason, we try to find a family of solutions expanded by a small parameter and apply the Nash-Moser Theorem to justify this expansion. Note that the application of Nash-Moser Theorem is necessary for the sake of conquest of the trouble with loss of regularities, and the justification of the applicability requires a very delicate analysis of the problem. (C) 2015 Elsevier Inc. All rights reserved.
Spatial chaos of Wang tiles with two symbols
(2016-02)
Chen, Jin-Yu
;
Chen, Yu-Jie
;
Hu, Wen-Guei
;
Lin, Song-Sun
;
應用數學系
This investigation completely classifies the spatial chaos problem in plane edge coloring (Wang tiles) with two symbols. For a set of Wang tiles B, spatial chaos occurs when the spatial entropy h(B) is positive. B is called a minimal cycle generator if P(B) not equal empty set and P(B\') = empty set whenever B\' not subset of B, where P(B) is the set of all periodic patterns on Z(2) generated by B. Given a set of Wang tiles B, write B = C-1 boolean OR C-2 boolean OR ... boolean OR C-k boolean OR N, where C-j, 1 <= j <= k, are minimal cycle generators and B contains no minimal cycle generator except those contained in C-1 boolean OR C-2 boolean OR ... boolean OR C-k. Then, the positivity of spatial entropy h(B) is completely determined by C-1 boolean OR C-2 boolean OR ... boolean OR C-k. Furthermore, there are 39 equivalence classes of marginal positive-entropy sets of Wang tiles and 18 equivalence classes of saturated zero-entropy sets of Wang tiles. For a set of Wang tiles B, h(B) is positive if and only if B contains a MPE set, and h(B) is zero if and only if B is a subset of a SZE set. (C) 2016 AIP Publishing LLC.
Spatial complexity in multi-layer cellular neural networks
(2009-01-15)
Ban, Jung-Chao
;
Chang, Chih-Hung
;
Lin, Song-Sun
;
Lin, Yin-Heng
;
應用數學系
This study investigates the complexity of the global set of output patterns for one-dimensional multi-layer cellular neural networks with input. Applying labeling to the output space produces a sofic shift space. Two invariants, namely spatial entropy and dynamical zeta function, can be exactly computed by studying the induced sofic shift space. This study gives sofic shift a realization through a realistic model. Furthermore, a new phenomenon, the broken of symmetry of entropy, is discovered in multi-layer cellular neural networks with input. (C) 2008 Elsevier Inc. All rights reserved.
Spatial complexity in multi-layer cellular neural networks
(2009-01-15)
Ban, Jung-Chao
;
Chang, Chih-Hung
;
Lin, Song-Sun
;
Lin, Yin-Heng
;
應用數學系
This study investigates the complexity of the global set of output patterns for one-dimensional multi-layer cellular neural networks with input. Applying labeling to the output space produces a sofic shift space. Two invariants, namely spatial entropy and dynamical zeta function, can be exactly computed by studying the induced sofic shift space. This study gives sofic shift a realization through a realistic model. Furthermore, a new phenomenon, the broken of symmetry of entropy, is discovered in multi-layer cellular neural networks with input. (C) 2008 Elsevier Inc. All rights reserved.
Three-dimensional Cellular Neural Networks and pattern generation problems
(2008-04-01)
Ban, Jung-Chao
;
Lin, Song-Sun
;
Lin, Yin-Heng
;
應用數學系
;
Department of Applied Mathematics
This work investigates three-dimensional pattern generation problems and their applications to three-dimensional Cellular Neural Networks (3DCNN). An ordering matrix for the set of all local patterns is established to derive a recursive formula for the ordering matrix of a larger finite lattice. For a given admissible set of local patterns, the transition matrix is defined and the recursive formula of high order transition matrix is presented. Then, the spatial entropy is obtained by computing the maximum eigenvalues of a sequence of transition matrices. The connecting operators are used to verify the positivity of the spatial entropy, which is important in determining the complexity of the set of admissible global patterns. The results are useful in studying a set of global stationary solutions in various Lattice Dynamical Systems and Cellular Neural Networks.
ZETA FUNCTIONS FOR HIGHER-DIMENSIONAL SHIFTS OF FINITE TYPE
(2009-11-01)
Hu, Wen-Guei
;
Lin, Song-Sun
;
應用數學系
;
Department of Applied Mathematics
This work investigates zeta functions for d-dimensional shifts of finite type, d >= 3. First, the three-dimensional case is studied. The trace operator T(a1,a2;b12) and rotational matrices R(x;a1,a2;b12) and R(y;a1,a2;b12) are introduced to study [GRAPHICS] -periodic patterns. The rotational symmetry of T(a1,a2;b12) induces the reduced trace operator tau(a1,a2;b12) and then the associated zeta function zeta(a1,a2;b12) = (det(I - s(a1a2)tau(a1,a2;b12)))(-1). The zeta function zeta is then expressed as zeta = Pi(infinity)(a1=1) Pi(infinity)(a2=1) Pi(a1-1)(b12=0) zeta(a1,a2;b12), a reciprocal of an infinite product of polynomials. The results hold for any inclined coordinates, determined by unimodular transformation in GL(3)(Z). Hence, a family of zeta functions exists with the same integer coefficients in their Taylor series expansions at the origin, and yields a family of identities in number theory. The methods used herein are also valid for d-dimensional cases, d >= 4, and can be applied to thermodynamic zeta functions for the three-dimensional Ising model with finite range interactions.
林松山教授學術論文集
(s.n.], 2003)
Lin, Song-Sun