A faster algorithm for the construction of optimal factoring automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929301739274240 |
|---|---|
| author | Erlebach, Thomas Papadopoulos, Kleitos |
| author_facet | Erlebach, Thomas Papadopoulos, Kleitos |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02354 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A faster algorithm for the construction of optimal factoring automata Erlebach, Thomas Papadopoulos, Kleitos Data Structures and Algorithms F.2.2 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)$. |
| title | A faster algorithm for the construction of optimal factoring automata |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2404.02354 |