Init language of a recursively enumerable language
- From: Slavko Rede <slavko.rede@xxxxxx>
- Date: Thu, 05 Oct 2006 10:28:22 EDT
The language Init(L) of a recursively enumerable
language L is the set of all such words x that there
exists a word y for which holds xy is in L.
Omega languages are sets of infinite words accepted by
Turing machines. (The definition of acceptance is here
slightly different than by the ordinary Turing
machines.)
Now, if L is an omega language then Init(L) is a
language of finite strings. Each such string is a prefix
of an infinite word. In the article "Omega-computations
on Turing machines" written by R.S.Cohen and A.Y.Gold
one can read the so called Init Lemma:
If L is an omega language recognizable by a:
1) Finite state automata
2) Pushdown automata
3) Deterministic pushdown automata
4) 1-way non-deterministic automata
5) Deterministic stack automata
then the language Init(L) is recognizable by the
same type of automata.
However, the Init Lemma does not hold for context
sensitive omega languages accepted by linear bounded
automata. Namely, every omega language is context
sensitive but there exists an omega language whose init
language is even not recursively enumerable.
Of course, if L is a an ordinary recursively enumerable
language of finite words then Init(L) is also a
recursively enumerable language. Is perhaps Init(L) then
a context sensitive language as well? Are there any
articles or books which handle this question?
.
- Prev by Date: Re: Penny Smith solution to Navier Stokes Millenium Problem
- Next by Date: Re: Penny Smith solution to Navier Stokes Millenium Problem
- Previous by thread: Seven papers published by Geometry & Topology Publications
- Next by thread: a triangle inequality
- Index(es):
Relevant Pages
|