Ternary directed acyclic word graphs

DOI10.1016/j.tcs.2004.07.008zbMath1071.68048OpenAlexW2154517803MaRDI QIDQ703500

Shunsuke Inenaga, Satoru Miyamoto, Masayuki Takeda, Ayumi Shinohara

Publication date: 11 January 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.008

zbMATH Keywords

AVL treesDeterministic finite state automataDirected acyclic word graphsPattern matching on stringsTernary search trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

On the Structure of Consistent Partitions of Substring Set of a Word ⋮ WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate string matching with suffix automata
• The smallest automaton recognizing the subwords of a text
• Minimisation of acyclic deterministic automata in linear time
• Transducers and repetitions
• On-line construction of suffix trees
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Complete inverted files for efficient text retrieval and analysis

This page was built for publication: Ternary directed acyclic word graphs