Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Fibonacci morphisms and Sturmian words
Séébold P. Theoretical Computer Science88 (2):365-384,1991.Type:Article
Date Reviewed: Oct 1 1992

The author proves five conjectures made by Kosa [1] and shows their usefulness in the automatic generation of  Sturmian  words. For a two-letter alphabet B, if p ( n ) denotes the number of factors of length n in an infinite word U, then U is Sturmian if p ( n ) = n + 1 for any n ∈ N. The best example of a Sturmian word is a Fibonacci word. Given a binary alphabet of the form A = { 0 , 1 }, the Sturmian words are generated by left and right endomorphisms of the form 1 → 01 and 1 → 10 respectively. The conjectures of Kosa deal with the completeness of such generating relationships.

The paper is highly theoretical and makes no mention of any application. The content of the paper does not appear to have immediate interest for many people. Among 16 references cited, only one other than the author’s directly addresses the problem.

The proofs are nicely stated and easy to follow. Instead of introducing all notation in the same place, however, the author sometimes introduces notation in the middle. This makes it difficult for the reader to find the meaning of certain symbols. I would have appreciated some more worked-out examples.

The formatting of the paper is nice, except for a few bad line breaks in the middle of equations. Overall, the paper is a nice exercise for a theoretician.

Reviewer:  M. Mukherjee Review #: CR116143
1) Kosa, M. Problems and solutions. EATCS Bull. 32 (1987), 331–333.
Bookmark and Share
 
Formal Languages (F.4.3 )
 
 
Number-Theoretic Computations (F.2.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Formal Languages": Date
The three subfamilies of rational &ohgr;-languages closed under &ohgr;-transduction
Timmerman E. Theoretical Computer Science 76(2-3): 243-250, 2001. Type: Article
Jul 1 1992
Introduction to formal languages
Révész G., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486666976)
Jan 1 1993
Algorithms for determining relative inclusion star height and inclusion
Hashiguchi K. Theoretical Computer Science 91(1): 85-100, 1991. Type: Article
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy