pith. sign in

arxiv: 0801.1783 · v1 · submitted 2008-01-11 · 💻 cs.CC · cs.GT· cs.LO· math.LO

An omega-power of a context-free language which is Borel above Delta⁰_omega

classification 💻 cs.CC cs.GTcs.LOmath.LO
keywords borellanguageomegaabovedeltaomega-powerwordsaccepted
0
0 comments X
read the original abstract

We use erasers-like basic operations on words to construct a set that is both Borel and above Delta^0_omega, built as a set V^\omega where V is a language of finite words accepted by a pushdown automaton. In particular, this gives a first example of an omega-power of a context free language which is a Borel set of infinite rank.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.