Descriptive Set Theory and $\omega$-Powers of Finitary Languages
| Autor: | Finkel, Olivier, Lecomte, Dominique |
|---|---|
| Přispěvatelé: | Equipe de Logique Mathématique (ELM), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Adrian Rezus |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
[MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
Languages of finite or infinite words ω-power [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) topological complexity context-free one-counter automaton Borel class Computer Science::Formal Languages and Automata Theory complete set |
| Zdroj: | Contemporary Logic and Computing Adrian Rezus. Contemporary Logic and Computing, 1, College Publications, pp.518-541, 2020, Landscapes in Logic |
| Popis: | International audience; The ω-power of a finitary language L over a finite alphabet Σ is the language of infinite words over Σ defined by L ∞ := {w 0 w 1. .. ∈ Σ ω | ∀i ∈ ω w i ∈ L}. The ω-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like Büchi automata or Büchi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and ω-powers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|