Iterating iterated substitution

Joost Engelfriet

doi:10.1016/0304-3975(77)90043-3

Iterating iterated substitution

Joost Engelfriet

Research output: Contribution to journal › Article › Academic

1 Citation (Scopus)

123 Downloads (Pure)

Abstract

By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.

Original language	Undefined
Pages (from-to)	85-100
Journal	Theoretical computer science
Volume	5
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(77)90043-3
Publication status	Published - 1977

Keywords

IR-68024

Access to Document

10.1016/0304-3975(77)90043-3

Engelfriet77iterating

Cite this

@article{99ff8229cf1e4ff0a28697f47e267ea5,

title = "Iterating iterated substitution",

abstract = "By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.",

keywords = "IR-68024",

author = "Joost Engelfriet",

year = "1977",

doi = "10.1016/0304-3975(77)90043-3",

language = "Undefined",

volume = "5",

pages = "85--100",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Iterating iterated substitution

AU - Engelfriet, Joost

PY - 1977

Y1 - 1977

N2 - By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.

AB - By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.

KW - IR-68024

U2 - 10.1016/0304-3975(77)90043-3

DO - 10.1016/0304-3975(77)90043-3

M3 - Article

SN - 0304-3975

VL - 5

SP - 85

EP - 100

JO - Theoretical computer science

JF - Theoretical computer science

IS - 1

ER -