A faster algorithm for the construction of optimal factoring automata
<|reference_start|>A faster algorithm for the construction of optimal factoring automata: The problem of constructing optimal factoring automata arises in the context of unification factoring for the efficient execution of logic programs. Given an ordered set of $n$ strings of length $m$, the problem is to construct a trie-like tree structure of minimum size in which the leaves in left-to-right order represent the input strings in the given order. Contrary to standard tries, the order in which the characters of a string are encountered can be different on different root-to-leaf paths. Dawson et al. [ACM Trans. Program. Lang. Syst. 18(5):528--563, 1996] gave an algorithm that solves the problem in time $O(n^2 m (n+m))$. In this paper, we present an improved algorithm with running-time $O(n^2m)$.<|reference_end|>
@article{erlebach2024a,
    title={A faster algorithm for the construction of optimal factoring automata},
    author={Thomas Erlebach and Kleitos Papadopoulos},
    journal={arXiv preprint arXiv:2404.02354},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02354},
    primaryClass={cs.DS}
}