Optimal insertion in deterministic DAWGs

DOI10.1016/S0304-3975(02)00571-6zbMath1022.68070OpenAlexW2107822224WikidataQ99428232 ScholiaQ99428232MaRDI QIDQ1399983

Kyriakos N. Sgarbas, Nikos D. Fakotakis, George Kokkinakis

Publication date: 30 July 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00571-6

zbMATH Keywords

DFAminimizationincremental algorithmsDAWGspelling checker

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Incremental construction of minimal deterministic finite cover automata ⋮ Building efficient and compact data structures for simplicial complexes ⋮ Minimisation of automata

Cites Work

• Minimisation of acyclic deterministic automata in linear time
• Average sizes of suffix trees and DAWGs
• On the computational power of pushdown automata
• How to squeeze a lexicon
• Incremental Construction of Minimal Acyclic Finite-State Automata
• An algorithm for dynamic processing of dawg's
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal insertion in deterministic DAWGs