k-universality of regular languages

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Downloads (Pure)

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 in Σk appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O(log n). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, nondeterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton.

Original languageEnglish
Title of host publication34th International Symposium on Algorithms and Computation, ISAAC 2023
EditorsSatoru Iwata, Naonori Kakimura
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772891
DOIs
Publication statusPublished - Dec 2023
Event34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan
Duration: 3 Dec 20236 Dec 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume283
ISSN (Print)1868-8969

Conference

Conference34th International Symposium on Algorithms and Computation, ISAAC 2023
Country/TerritoryJapan
CityKyoto
Period3/12/236/12/23

Keywords

  • Finite Automata
  • Regular Languages
  • String Algorithms
  • Subsequences

Fingerprint

Dive into the research topics of 'k-universality of regular languages'. Together they form a unique fingerprint.

Cite this