|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Decidability of plane edge coloring with three colors | | Hung-Hsun Chen
; Wen-Guei Hu
; De-Jan Lai
; Song-Sun Lin
; | | Date: |
25 Oct 2012 | | Abstract: | This investigation studies the decidability problem of plane edge coloring
with three symbols. 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 decision problem is to find an
algorithm to determine whether or not $Sigma(B)
eqemptyset$, where
$Sigma(B)$ is the set of all global patterns on $mathbb{Z}^{2}$ that can be
constructed from the Wang tiles in $B$.
When $pgeq 5$, the problem is known to be undecidable. When $p=2$, the
problem is decidable. This study proves that when $p=3$, the problem is also
decidable. $mathcal{P}(B)$ is the set of all periodic patterns on
$mathbb{Z}^{2}$ that can be generated by the tiles in $B$. If
$mathcal{P}(B)
eqemptyset$, then $B$ has a subset $B’$ of minimal cycle
generators such that $mathcal{P}(B’)
eqemptyset$ and
$mathcal{P}(B")=emptyset$ for $B"subsetneqq B’$. This study demonstrates
that the set $mathcal{C}(3)$ of all minimal cycle generators contains
$787,605$ members that can be classified into $2,906$ equivalence classes.
$mathcal{N}(3)$ is the set of all maximal non-cycle generators: if $Bin
mathcal{N}(3)$, then $mathcal{P}(B)=emptyset$ and
$mathcal{P}( ilde{B})
eqemptyset$ for $ ilde{B}supsetneqq B$. The problem
is shown to be decidable by proving that $Bin mathcal{N}(3)$ implies
$Sigma(B)=emptyset$. Consequently, $Sigma(B)
eqemptyset$ if and only if
$mathcal{P}(B)
eqemptyset$. | | Source: | arXiv, 1210.6712 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER