Computer Science – Formal Languages and Automata Theory
Scientific paper
2010-09-29
Electronic Journal of Combinatorics 2010 Vol. 17(1) #R140
Computer Science
Formal Languages and Automata Theory
11 pages, 1 figure, 1 table. Presented at NORCOM'2010, submitted to EJC
Scientific paper
Circular words are cyclically ordered finite sequences of letters. We give a computer-free proof of the following result by Currie: square-free circular words over the ternary alphabet exist for all lengths $l$ except for 5, 7, 9, 10, 14, and 17. Our proof reveals an interesting connection between ternary square-free circular words and closed walks in the $K_{3{,}3}$ graph. In addition, our proof implies an exponential lower bound on the number of such circular words of length $l$ and allows one to list all lengths $l$ for which such a circular word is unique up to isomorphism.
No associations
LandOfFree
On ternary square-free circular words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On ternary square-free circular words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On ternary square-free circular words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-522364