Hacker News new | past | comments | ask | show | jobs | submit login
How to Squeeze a Lexicon (2002) [pdf] (aei.polsl.pl)
9 points by tjalfi 17 days ago | hide | past | favorite | 1 comment


Here's the abstract of this paper.

Minimal acyclic deterministic finite automata (ADFAs) can be used as a compact representation of finite string sets with fast access time. Creating them with traditional algorithms of DFA minimization is a resource hog when a large collection of strings is involved. This paper aims to popularize an efficient but little known algorithm for creating minimal ADFAs recognizing a finite language, invented independently by several authors. The algorithm is presented for three variants of ADFAs, its minor improvements are discussed, and minimal ADFAs are compared to competitive data structures.

Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact