$k$-Universality of Regular Languages Revisited
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916660763426816 |
|---|---|
| author | Adamson, Duncan Fleischmann, Pamela Huch, Annika Koß, Tore Manea, Florin |
| author_facet | Adamson, Duncan Fleischmann, Pamela Huch, Annika Koß, Tore Manea, Florin |
| contents | A subsequence of a word $w$ is a word $u$ such that $u = w[i_1] w[i_2] \cdots w[i_k]$, for some set of indices $1 \leq i_1 < i_2 < \dots < i_k \leq \vert w \vert$. A word $w$ is \emph{$k$-subsequence universal} over an alphabet $Σ$ if every word over $Σ$ up to length $k$ appears in $w$ as a subsequence. In this paper, we revisit the problem $k$-ESU of deciding, for a given integer $k$, whether a regular language, given either as nondeterministic finite automaton or as a regular expression, contains a $k$-universal word. [Adamson et al., ISAAC 2023] showed that this problem is NP-hard, even in the case when $k=1$, and an FPT algorithm w.r.t. the size of the input alphabet was given. In this paper, we improve the aforementioned algorithmic result and complete the analysis of this problem w.r.t. other parameters. That is, we propose a more efficient FPT algorithm for $k$-ESU, with respect to the size of the input alphabet, and propose new FPT algorithms for this problem w.r.t.~the number of states of the input automaton and the length of the input regular expression. We also discuss corresponding lower bounds. Our results significantly improve the understanding of this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $k$-Universality of Regular Languages Revisited Adamson, Duncan Fleischmann, Pamela Huch, Annika Koß, Tore Manea, Florin Formal Languages and Automata Theory Data Structures and Algorithms A subsequence of a word $w$ is a word $u$ such that $u = w[i_1] w[i_2] \cdots w[i_k]$, for some set of indices $1 \leq i_1 < i_2 < \dots < i_k \leq \vert w \vert$. A word $w$ is \emph{$k$-subsequence universal} over an alphabet $Σ$ if every word over $Σ$ up to length $k$ appears in $w$ as a subsequence. In this paper, we revisit the problem $k$-ESU of deciding, for a given integer $k$, whether a regular language, given either as nondeterministic finite automaton or as a regular expression, contains a $k$-universal word. [Adamson et al., ISAAC 2023] showed that this problem is NP-hard, even in the case when $k=1$, and an FPT algorithm w.r.t. the size of the input alphabet was given. In this paper, we improve the aforementioned algorithmic result and complete the analysis of this problem w.r.t. other parameters. That is, we propose a more efficient FPT algorithm for $k$-ESU, with respect to the size of the input alphabet, and propose new FPT algorithms for this problem w.r.t.~the number of states of the input automaton and the length of the input regular expression. We also discuss corresponding lower bounds. Our results significantly improve the understanding of this problem. |
| title | $k$-Universality of Regular Languages Revisited |
| topic | Formal Languages and Automata Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.18611 |