Classifying Rotationally-Closed Languages Having Greedy Universal Cycles
| Autor: | Joseph DiMuro |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Applied Mathematics
String (computer science) Append Sigma Substring Theoretical Computer Science Set (abstract data type) Combinatorics Computational Theory and Mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology Alphabet Greedy algorithm Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 26 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/7932 |
| Popis: | Let $\textbf{T}(n,k)$ be the set of strings of length $n$ over the alphabet $\Sigma=\{1,2,\ldots,k\}$. A universal cycle for $\textbf{T}(n,k)$ can be constructed using a greedy algorithm: start with the string $k^n$, and continually append the least symbol possible without repeating a substring of length $n$. This construction also creates universal cycles for some subsets $\textbf{S}\subseteq\textbf{T}(n,k)$; we will classify all such subsets that are closed under rotations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|