A regular language is said to be Wheeler if it is accepted by some finite automaton whose states admit a total Wheeler order, which reflects the co-lexicographic order of the prefixes of the strings accepted by the automaton. As Wheeler automata provide useful properties for many applications related to pattern matching and indexing, it is important to check if a given regular language is Wheeler to know if we can benefit from them. In this paper, we present an algorithm to decide whether a regular language represented as a deterministic finite automaton is Wheeler in quadratic time, which also matches the lower bound unless the strong exponential time hypothesis fails. Our method can also be extended to decide if there exists a p-width DFA that accepts the language of the input DFA.

Testing Wheelerness of Regular Languages

Ruben Becker;Davide Cenzato;Sung-Hwan Kim;Bojana Kodric;Alberto Policriti;Nicola Prezza
2023-01-01

Abstract

A regular language is said to be Wheeler if it is accepted by some finite automaton whose states admit a total Wheeler order, which reflects the co-lexicographic order of the prefixes of the strings accepted by the automaton. As Wheeler automata provide useful properties for many applications related to pattern matching and indexing, it is important to check if a given regular language is Wheeler to know if we can benefit from them. In this paper, we present an algorithm to decide whether a regular language represented as a deterministic finite automaton is Wheeler in quadratic time, which also matches the lower bound unless the strong exponential time hypothesis fails. Our method can also be extended to decide if there exists a p-width DFA that accepts the language of the input DFA.
2023
Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5048994
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact