Some complete $$\omega $$-powers of a one-counter language, for any Borel class of finite rank

&
Archive for Mathematical Logic 60 (1-2):161-187 (2020)
  Copy   BIBTEX

Abstract

We prove that, for any natural number \, we can find a finite alphabet \ and a finitary language L over \ accepted by a one-counter automaton, such that the \-power $$\begin{aligned} L^\infty :=\{ w_0w_1\ldots \in \Sigma ^\omega \mid \forall i\in \omega ~~w_i\in L\} \end{aligned}$$is \-complete. We prove a similar result for the class \.

Categories

Add categories

Keywords

Reprint years

2021

DOI

10.1007/s00153-020-00737-4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,774

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Some complete ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document}-powers of a one-counter language, for any Borel class of finite rank. [REVIEW]Dominique Lecomte & Olivier Finkel - 2021 - Archive for Mathematical Logic 60 (1-2):161-187.
Classical and effective descriptive complexities of ω-powers.Olivier Finkel & Dominique Lecomte - 2009 - Annals of Pure and Applied Logic 160 (2):163-191.
The Beth-Closure of $mathscr{L}(Q_alpha)$ is Not Finitely Generated.Lauri Hella & Kerkko Luosto - 1992 - Journal of Symbolic Logic 57 (2):442-448.
Finite Model Theory and Finite Variable Logics.Eric Barry Rosen - 1995 - Dissertation, University of Pennsylvania
Infinitary Logic has No Expressive Efficiency Over Finitary Logic.Matthew Harrison-Trainor & Miles Kretschmer - forthcoming - Journal of Symbolic Logic:1-18.
A partition relation for pairs on $$omega ^{omega ^omega }$$.Claribet Piña - 2018 - Archive for Mathematical Logic 57 (7-8):727-753.
Some remarks on category of the real line.Kyriakos Keremedis - 1999 - Archive for Mathematical Logic 38 (3):153-162.
On some sets of dictionaries whose ω ‐powers have a given.Olivier Finkel - 2010 - Mathematical Logic Quarterly 56 (5):452-460.
On Cohesive Powers of Linear Orders.Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer, Alexandra A. Soskova & Stefan V. Vatev - 2023 - Journal of Symbolic Logic 88 (3):947-1004.
Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.

Analytics

Added to PP
2020-07-03

Downloads
11 (#351,772)

6 months
5 (#1,552,255)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Descriptive Set Theory.Yiannis Nicholas Moschovakis - 1982 - Studia Logica 41 (4):429-430.
Classical and effective descriptive complexities of ω-powers.Olivier Finkel & Dominique Lecomte - 2009 - Annals of Pure and Applied Logic 160 (2):163-191.
Ω-powers and descriptive set theory.Dominique Lecomte - 2005 - Journal of Symbolic Logic 70 (4):1210-1232.

Add more references