A speed-up for the commute between subword trees and DAWGs.
type: Item
instance of: scholarly article
title: A speed-up for the commute between subword trees and DAWGs.
zbMATH Open document ID: 1043.68078
DOI: 10.1016/S0020-0190(01)00327-1
author: Alberto Apostolico
author: Stefano Lonardi
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: A popular way to describe and build the DAWG or Directed Acyclic Word Graph of a string is by transformation of the corresponding subword tree. This transformation, which is not difficult to reverse, is easy to grasp and almost trivial to implement except for the assumed implication of a standard tree isomorphism algorithm. Here we point out a simple property of subword trees that makes checking tree isomorphism in this context a straightforward process, thereby simplifying the transformation significantly. Subword trees and DAWGs arise rather ubiquitously in applications of string processing, where they often play complementary roles. Efficient conversions are thus especially desirable.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68U15
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856402
zbMATH Keywords: Design and analysis of algorithms
zbMATH Keywords: Subword tree
zbMATH Keywords: DAWG
zbMATH Keywords: Tree isomorphism test
MaRDI profile type: Publication
cites work: On the computational power of pushdown automata
cites work: Q4347080
cites work: Complete inverted files for efficient text retrieval and analysis
cites work: The smallest automaton recognizing the subwords of a text
cites work: Q4849531
cites work: A V log V algorithm for isomorphism of triconnected planar graphs
cites work: A Space-Economical Suffix Tree Construction Algorithm
cites work: On-line construction of suffix trees
Recommended article: Q3690247
Recommended article: Q3690245
Recommended article: Faster Subtree Isomorphism
Recommended article: An improvement of subword complexity
Recommended article: Suffix trees, DAWGs and CDAWGs for forward and backward tries
Recommended article: Q3312210
Recommended article: A Faster Parameterized Algorithm for Treedepth
Recommended article: Slowing Down Top Trees for Better Worst-Case Compression
Recommended article: Parameterized DAWGs: efficient constructions and bidirectional pattern searches
description: scientific article; zbMATH DE number 1856402