k-universality of regular languages revisited

Duncan Adamson; Pamela Fleischmann; Annika Huch; Tore Koß; Florin Manea

doi:10.1007/978-981-96-8312-3_2

k-universality of regular languages revisited

Duncan Adamson^*, Pamela Fleischmann^*, Annika Huch^*, Tore Koß^*, Florin Manea^*

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A subsequence of a word w is a word u such that u = w[i₁]w[i₂] ··· w[i_k], for some set of indices 1 ≤ i₁ < i₂ < ··· < i_k ≤ |w|. A word w is 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.

Original language	English
Title of host publication	Frontiers of algorithmics
Subtitle of host publication	19th international joint conference, IJTCS-FAW 2025, proceedings
Editors	Vincent Chau, Christoph Dürr, Minming Li, Pinyan Lu
Place of Publication	Singapore
Publisher	Springer Nature Singapore
Pages	16-32
Number of pages	17
ISBN (Electronic)	9789819683123
ISBN (Print)	9789819683116
DOIs	https://doi.org/10.1007/978-981-96-8312-3_2
Publication status	Published - 30 Jun 2025
Event	19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom - Sorbonne University, Paris, France Duration: 30 Jun 2025 → 2 Jul 2025 https://ijtcs-faw.github.io/2025/

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	15828
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom
Abbreviated title	IJTCS-FAW 2025
Country/Territory	France
City	Paris
Period	30/06/25 → 2/07/25
Internet address	https://ijtcs-faw.github.io/2025/

Keywords

String algorithms
Regular languages
Subregular languages
Regular expressions
Finite automata
Subsequences
Universality

Access to Document

10.1007/978-981-96-8312-3_2

https://arxiv.org/abs/2503.18611

Cite this

Adamson, D., Fleischmann, P., Huch, A., Koß, T., & Manea, F. (2025). k-universality of regular languages revisited. In V. Chau, C. Dürr, M. Li, & P. Lu (Eds.), Frontiers of algorithmics: 19th international joint conference, IJTCS-FAW 2025, proceedings (pp. 16-32). (Lecture notes in computer science; Vol. 15828). Springer Nature Singapore. https://doi.org/10.1007/978-981-96-8312-3_2

@inproceedings{b00d3c9e64ea4cdd9d6d164fd8789859,

title = "k-universality of regular languages revisited",

abstract = "A subsequence of a word w is a word u such that u = w[i1]w[i2] ··· w[ik], for some set of indices 1 ≤ i1 < i2 < ··· < ik ≤ |w|. A word w is 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.",

keywords = "String algorithms, Regular languages, Subregular languages, Regular expressions, Finite automata, Subsequences, Universality",

author = "Duncan Adamson and Pamela Fleischmann and Annika Huch and Tore Ko{\ss} and Florin Manea",

note = "Funding: Florin Manea is supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) in the framework of the Heisenberg Programme – project number 466789228.; 19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom, IJTCS-FAW 2025 ; Conference date: 30-06-2025 Through 02-07-2025",

year = "2025",

month = jun,

day = "30",

doi = "10.1007/978-981-96-8312-3\_2",

language = "English",

isbn = "9789819683116",

series = "Lecture notes in computer science",

publisher = "Springer Nature Singapore",

pages = "16--32",

editor = "Vincent Chau and Christoph D{\"u}rr and Minming Li and Pinyan Lu",

booktitle = "Frontiers of algorithmics",

url = "https://ijtcs-faw.github.io/2025/",

}

Adamson, D, Fleischmann, P, Huch, A, Koß, T & Manea, F 2025, k-universality of regular languages revisited. in V Chau, C Dürr, M Li & P Lu (eds), Frontiers of algorithmics: 19th international joint conference, IJTCS-FAW 2025, proceedings. Lecture notes in computer science, vol. 15828, Springer Nature Singapore, Singapore, pp. 16-32, 19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom, Paris, France, 30/06/25. https://doi.org/10.1007/978-981-96-8312-3_2

k-universality of regular languages revisited. / Adamson, Duncan; Fleischmann, Pamela; Huch, Annika et al.
Frontiers of algorithmics: 19th international joint conference, IJTCS-FAW 2025, proceedings. ed. / Vincent Chau; Christoph Dürr; Minming Li; Pinyan Lu. Singapore: Springer Nature Singapore, 2025. p. 16-32 (Lecture notes in computer science; Vol. 15828).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - k-universality of regular languages revisited

AU - Adamson, Duncan

AU - Fleischmann, Pamela

AU - Huch, Annika

AU - Koß, Tore

AU - Manea, Florin

N1 - Funding: Florin Manea is supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) in the framework of the Heisenberg Programme – project number 466789228.

PY - 2025/6/30

Y1 - 2025/6/30

N2 - A subsequence of a word w is a word u such that u = w[i1]w[i2] ··· w[ik], for some set of indices 1 ≤ i1 < i2 < ··· < ik ≤ |w|. A word w is 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.

AB - A subsequence of a word w is a word u such that u = w[i1]w[i2] ··· w[ik], for some set of indices 1 ≤ i1 < i2 < ··· < ik ≤ |w|. A word w is 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.

KW - String algorithms

KW - Regular languages

KW - Subregular languages

KW - Regular expressions

KW - Finite automata

KW - Subsequences

KW - Universality

UR - https://www.scopus.com/pages/publications/105010821482

U2 - 10.1007/978-981-96-8312-3_2

DO - 10.1007/978-981-96-8312-3_2

M3 - Conference contribution

AN - SCOPUS:105010821482

SN - 9789819683116

T3 - Lecture notes in computer science

SP - 16

EP - 32

BT - Frontiers of algorithmics

A2 - Chau, Vincent

A2 - Dürr, Christoph

A2 - Li, Minming

A2 - Lu, Pinyan

PB - Springer Nature Singapore

CY - Singapore

T2 - 19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom

Y2 - 30 June 2025 through 2 July 2025

ER -