On the Unavoidability of Primitive Words and other Languages
| Autor: | Leupold, Peter |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| DOI: | 10.25596/jalc-2021-091 |
| Popis: | Most of the well-known language classes contain very different languages that often have no words at all in common. Therefore it might seem improbable at first sight, that there could be a language non-trivially sharing infinitely many words with each of the individual languages. Non-trivially here means, that the language itself has infinite complement so that there do exist infinite languages that have empty intersection with it. We formalize this idea of being unavoidable. Then we fill the concept with life by providing examples of languages that are unavoidable for classes of regular, context-free and context-sensitive languages. Primitive words play a central role in many of these examples. Journal of Automata, Languages and Combinatorics, Volume 26, Numbers 1-2, 2021, 91-107 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|