The suffix tree of a tree and minimizing sequential transducers

DOI10.1016/S0304-3975(96)00319-2zbMath0896.68058MaRDI QIDQ1127317

Dany Breslauer

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

suffix tree of a treesequential transducers

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Efficiently computing runs on a trie, Longest common extensions in trees, Longest Common Extensions in Trees, On updating suffix tree labels, Computing the prefix of an automaton, Computing runs on a trie, A proof of Choffrut's theorem on subsequential functions, Minimization algorithms for sequential transducers, Solving string problems on graphs using the labeled direct product, Determinization of transducers over finite and infinite words., Minimizing subsequential transducers: a survey., Constructing LZ78 tries and position heaps in linear time for large alphabets

Uses Software

• Algorithm 360

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding level-ancestors in trees
• Minimization algorithms for sequential transducers
• On the computational power of pushdown automata
• Fast Algorithms for Finding Nearest Common Ancestors
• Faster algorithms for the shortest path problem
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A Space-Economical Suffix Tree Construction Algorithm
• Fast incremental planarity testing