The Open UniversitySkip to content
 

Improved bounds on the number of ternary square-free words

Grimm, Uwe (2001). Improved bounds on the number of ternary square-free words. Journal of Integer Sequences, 4(2)

Full text available as:
[img]
Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (133Kb)
URL: http://www.cs.uwaterloo.ca/journals/JIS/VOL4/GRIMM...
Google Scholar: Look up in Google Scholar

Abstract

Improved upper and lower bounds on the number of square-free ternary words are obtained. The upper bound is based on the enumeration of square-free ternary words up to length 110. The lower bound is derived by constructing generalised Brinkhuis triples. The problem of finding such triples can essentially be reduced to a combinatorial problem, which can efficiently be treated by computer. In particular, it is shown that the number of square-free ternary words of length n grows at least as 65^(n/40), replacing the previous best lower bound of 2^(n/17).

Item Type: Journal Article
ISSN: 1530-7638
Extra Information: The Journal of Integer Sequences is an open access journal without consecutive page numbers. The article number is 01.2.7.
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 6744
Depositing User: Uwe Grimm
Date Deposited: 13 Feb 2007
Last Modified: 06 Dec 2010 17:40
URI: http://oro.open.ac.uk/id/eprint/6744
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk