A translational theorem for the class of EOL languages

Joost Engelfriet; Grzegorz Rozenberg

doi:10.1016/S0019-9958(81)90198-4

A translational theorem for the class of EOL languages

Joost Engelfriet, Grzegorz Rozenberg

Research output: Contribution to journal › Article › Academic

3 Citations (Scopus)

31 Downloads (Pure)

Abstract

If K is not a context-free language, then sh(K, a*) is not an EOL language (where sh(K1, K2) denotes the shuffle of the languages K1 and K2, and a is a symbol not in the alphabet of K). Hence the class of context-free languages is the largest full AFL inside the class of EOL languages.

Original language	English
Pages (from-to)	175-183
Journal	Information and Control
Volume	50
Issue number	2
DOIs	https://doi.org/10.1016/S0019-9958(81)90198-4
Publication status	Published - 1981
Externally published	Yes

Access to Document

10.1016/S0019-9958(81)90198-4

Engelfriet81translationalFinal published version, 437 KB

Cite this

@article{061899b5db134306ae45b1c947143453,

title = "A translational theorem for the class of EOL languages",

abstract = "If K is not a context-free language, then sh(K, a*) is not an EOL language (where sh(K1, K2) denotes the shuffle of the languages K1 and K2, and a is a symbol not in the alphabet of K). Hence the class of context-free languages is the largest full AFL inside the class of EOL languages.",

author = "Joost Engelfriet and Grzegorz Rozenberg",

year = "1981",

doi = "10.1016/S0019-9958(81)90198-4",

language = "English",

volume = "50",

pages = "175--183",

journal = "Information and Control",

issn = "0019-9958",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - A translational theorem for the class of EOL languages

AU - Engelfriet, Joost

AU - Rozenberg, Grzegorz

PY - 1981

Y1 - 1981

N2 - If K is not a context-free language, then sh(K, a*) is not an EOL language (where sh(K1, K2) denotes the shuffle of the languages K1 and K2, and a is a symbol not in the alphabet of K). Hence the class of context-free languages is the largest full AFL inside the class of EOL languages.

AB - If K is not a context-free language, then sh(K, a*) is not an EOL language (where sh(K1, K2) denotes the shuffle of the languages K1 and K2, and a is a symbol not in the alphabet of K). Hence the class of context-free languages is the largest full AFL inside the class of EOL languages.

U2 - 10.1016/S0019-9958(81)90198-4

DO - 10.1016/S0019-9958(81)90198-4

M3 - Article

SN - 0019-9958

VL - 50

SP - 175

EP - 183

JO - Information and Control

JF - Information and Control

IS - 2

ER -

A translational theorem for the class of EOL languages

Abstract

Access to Document

Fingerprint

Cite this