Words with simple Burrows-Wheeler transforms

MaRDI QIDQ1010806zbMATH OpenFDO

Authors Simon J. Puglisi, Jamie Simpson

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/117257, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r83.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Combinatorics on words (68R15) Nonnumerical algorithms (68W05)

Review text

Summary: Mantaci et al have shown that if a word \(x\) on the alphabet \(\{a,b\}\) has a Burrows-Wheeler Transform of the form \(b^ia^j\) then \(x\) is a conjugate or a power of a conjugate of a standard word. We give an alternative proof of this result and describe words on the alphabet \(\{a,b,c\}\) whose transforms have the form \(c^ib^ja^k\). These words have some common properties with standard words. We also present some results about words on larger alphabets having similar properties.

Recommendations

• Balanced Words Having Simple Burrows-Wheeler Transform
• scientific article; zbMATH DE number 2051173
• Burrows-Wheeler transform and palindromic richness
• Burrows-Wheeler transformations and de Bruijn words
• Two combinatorial criteria for BWT images

Cited in

(25)

• Measuring the clustering effect of BWT via RLE
• Perfectly clustering words are primitive positive elements of the free group
• Logarithmic equal-letter runs for BWT of purely morphic words
• When a dollar makes a BWT
• Burrows-Wheeler transform and palindromic richness
• The alternating BWT: an algorithmic perspective
• Two combinatorial criteria for BWT images
• Arithmetics on suffix arrays of Fibonacci words
• Balanced Words Having Simple Burrows-Wheeler Transform
• The simplest binary word with only three squares
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Perfect balance and circularly rich words
• Balancing and clustering of words in the Burrows-Wheeler transform
• Order Conditions for Languages
• Clustering and Arnoux-Rauzy words
• On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms
• Christoffel matrices and Sturmian determinants
• Clustering of return words in languages of interval exchanges
• Characterizations of perfectly clustering words
• Perfectly clustering words and iterated palindromes over a ternary alphabet
• A generalization of perfectly clustering words and band bricks for certain gentle algebras
• Burrows-Wheeler transformations and de Bruijn words
• On the conjugates of Christoffel words
• On palindromic periodicities
• Characterisation of band bricks over certain string algebras and a variant of perfectly clustering words

This page was built for publication: Words with simple Burrows-Wheeler transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010806)