Optimal insertion in deterministic DAWGs

DOI10.1016/S0304-3975(02)00571-6MaRDI QIDQ1399983zbMATH OpenOpenAlexWikidataFDO

Authors Kyriakos N. Sgarbas, N. Fakotakis, G. 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

minimizationDFAincremental algorithmsDAWGspelling checker

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3974159
• scientific article; zbMATH DE number 4039135
• Optimal Interactive Coding for Insertions, Deletions, and Substitutions
• Optimal deterministic algorithm generation
• Stochastic Algorithms: Foundations and Applications
• Tight bounds for graph problems in insertion streams
• Optimum Algorithms for a Model of Direct Chaining
• OPTIMAL DELAUNAY POINT INSERTION
• scientific article; zbMATH DE number 1962793

Cites work

• scientific article; zbMATH DE number 3883638 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 839553 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• An algorithm for dynamic processing of dawg's
• Average sizes of suffix trees and DAWGs
• Direct construction of minimal acyclic finite states automata
• How to squeeze a lexicon
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Minimisation of acyclic deterministic automata in linear time
• On the computational power of pushdown automata

Cited in

(5)

• Incremental construction of minimal deterministic finite cover automata
• Minimisation of automata
• Building efficient and compact data structures for simplicial complexes
• An algorithm for dynamic processing of dawg's
• scientific article; zbMATH DE number 3570344 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399983)