A speed-up for the commute between subword trees and DAWGs.

DOI10.1016/S0020-0190(01)00327-1zbMath1043.68078MaRDI QIDQ1853059

Stefano Lonardi, Alberto Apostolico

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

DAWGDesign and analysis of algorithmsSubword treeTree isomorphism test

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for text processing; mathematical typography (68U15)

Related Items (1)

On-line construction of compact directed acyclic word graphs

Cites Work

• The smallest automaton recognizing the subwords of a text
• On-line construction of suffix trees
• A V log V algorithm for isomorphism of triconnected planar graphs
• On the computational power of pushdown automata
• A Space-Economical Suffix Tree Construction Algorithm
• Complete inverted files for efficient text retrieval and analysis
• Unnamed Item
• Unnamed Item

This page was built for publication: A speed-up for the commute between subword trees and DAWGs.