
handle: 10281/492759 , 10278/5069503 , 11390/1279005 , 11568/1272462
Deterministic Finite Wheeler Automata are a natural generalisation to regular languages of the theory of compressed data structures originated by the introduction of the Burrows-Wheeler transform. Indeed, if we can find a Wheeler automaton recognizing a given language L, such automaton can be used to design time and space efficient algorithms for representing and searching L. In this paper we introduce an alternative representation of Deterministic Wheeler Automata by showing that a natural map between strings and rational numbers in Qr0, 1q can be extended to represent the automaton’s states as intervals in Qr0, 1q. Using this representation it emerges a natural relationship between automata properties and some properties of real numbers. In addition, such representation enables us to formulate problems related to automata in a numerical setting. Although at the moment the numerical approach does not lead to time efficient algorithms, we believe this new perspective deserves further consideration. As a further demonstration of the convenience of this new representation, we use it to provide a simple proof of an unexpected result on regular languages. More precisely, we compare the size of the smallest Wheeler automaton recognizing a given language L with respect to the size of the smallest automaton, possibly non-Wheeler, recognizing the same language. We show settings in which there can be an exponential gap between the two sizes, and we discuss the implications of this result on the problem of representing regular languages.
Co-lexicographical Sorting; Deterministic Finite Automata; Graph Indexing; String Matching; Wheeler languages;, Co-lexicographical Sorting, Co-lexicographical Sorting; Deterministic Finite Automata; Graph Indexing; String Matching; Wheeler languages, Deterministic Finite Automata, Wheeler languages, Graph Indexing, String Matching, 004
Co-lexicographical Sorting; Deterministic Finite Automata; Graph Indexing; String Matching; Wheeler languages;, Co-lexicographical Sorting, Co-lexicographical Sorting; Deterministic Finite Automata; Graph Indexing; String Matching; Wheeler languages, Deterministic Finite Automata, Wheeler languages, Graph Indexing, String Matching, 004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
