Recognition of Deterministic ET0L Languages in Polynomial Time

Forfattere

  • Neil D. Jones
  • Sven Skyum

DOI:

https://doi.org/10.7146/dpb.v5i63.6482

Resumé

It is shown that if G is a deterministic ETOL system, there is a nondeterministic log space algorithm to determine membership in L(G). Consequently every deterministic ETOL language is recognizable in polynomial time. As a corollary, all context-free languages of finite index, and all indian parallel languages are recognizable within the same bounds.

Forfatterbiografier

Neil D. Jones

Sven Skyum

Downloads

Publiceret

1976-10-01

Citation/Eksport

Jones, N. D., & Skyum, S. (1976). Recognition of Deterministic ET0L Languages in Polynomial Time. DAIMI Report Series, 5(63). https://doi.org/10.7146/dpb.v5i63.6482

Nummer

Nr. 63 (1976): PB-63 Recognition of Deterministic ET0L Languages in Polynomial Time

Sektion

Articles

Licens

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.