Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437293 | Theoretical Computer Science | 2011 | 7 Pages |
Abstract
Brlek and Reutenauer conjectured that any infinite word with language closed under reversal satisfies the equality in which denotes the defect of and denotes , where and are the factor and palindromic complexity of , respectively. Brlek and Reutenauer verified their conjecture for periodic infinite words. Using their result, we prove the conjecture for uniformly recurrent words. Moreover, we summarize results and some open problems related to defects, which may be useful for the proof of the Brlek–Reutenauer conjecture in full generality.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics