Space-time Trade-offs for the LCP Array of Wheeler DFAs

Area of Science:

• Theoretical Computer Science
• Data Structures and Algorithms
• Stringology and Automata Theory

Background:

• The Longest Common Prefix (LCP) array, crucial for string processing, has been generalized to Wheeler Deterministic Finite Automata (DFAs).
• Existing LCP array storage for Wheeler DFAs requires O(n) bits, which can be space-inefficient compared to compact DFA representations like BOSS.
• Efficient computation of matching statistics on Wheeler DFAs is hindered by the space requirements of the LCP array.

Purpose of the Study:

• To develop a space-efficient method for accessing LCP array entries in Wheeler DFAs.
• To establish a space-time tradeoff for computing matching statistics on Wheeler DFAs.
• To improve the time complexity for navigating variable-order de Bruijn graphs using augmented BOSS representations.

Main Methods:

• A novel sampling technique is proposed to enable logarithmic time access to LCP array entries.
• This technique requires only a linear number of bits for storage, significantly reducing space complexity.
• The BOSS representation of de Bruijn graphs is augmented to achieve faster navigation of variable-order de Bruijn graphs.

Main Results:

• The proposed sampling technique allows LCP array access in O(log n) time while using only O(n) bits of space.
• A new space-time tradeoff is achieved for computing matching statistics on Wheeler DFAs.
• Navigation of variable-order de Bruijn graphs is improved to logarithmic time complexity in n, outperforming previous linear bounds.

Conclusions:

• The developed sampling technique offers a practical solution for space-efficient LCP array management in Wheeler DFAs.
• This research provides significant improvements in computing matching statistics and navigating de Bruijn graphs.
• The findings contribute to the development of more compact and faster data structures for automata and graph representations.