An Inverse Homomorphic Characterization of Full Principal AFL

Takashi Yokomori; Derick Wood

doi:10.1016/0020-0255(84)90029-X

An Inverse Homomorphic Characterization of Full Principal AFL

Takashi Yokomori^*, Derick Wood

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

The main result of this paper is: Let L be a full principal AFL closed under context-free substitution. Then there is a fixed language l₀ in L such that for each L in L there exist a weak coding h and a homomorphism g such that L = hg^-1(L₀). As a corollary, it immediately follows that there is a fixed ETOL language L₀ such that for each ETOL language L there exist a weak coding h and a homomorphism g such that L = hg^-1(L₀).

Original language	English
Pages (from-to)	209-215
Number of pages	7
Journal	Information Sciences
Volume	33
Issue number	3
DOIs	https://doi.org/10.1016/0020-0255(84)90029-X
Publication status	Published - 1984 Sept
Externally published	Yes

ASJC Scopus subject areas

Software
Information Systems and Management
Artificial Intelligence
Theoretical Computer Science
Control and Systems Engineering
Computer Science Applications

Access to Document

10.1016/0020-0255(84)90029-X

Cite this

@article{f9f799f316df4425b6fd9ba5736d244d,

title = "An Inverse Homomorphic Characterization of Full Principal AFL",

abstract = "The main result of this paper is: Let L be a full principal AFL closed under context-free substitution. Then there is a fixed language l0 in L such that for each L in L there exist a weak coding h and a homomorphism g such that L = hg-1(L0). As a corollary, it immediately follows that there is a fixed ETOL language L0 such that for each ETOL language L there exist a weak coding h and a homomorphism g such that L = hg-1(L0).",

author = "Takashi Yokomori and Derick Wood",

note = "Funding Information: *The work was supported by a Natural Sciences and Engineering Research Council of Canada Grant NO. A-5692, and was carried out during the first author{\textquoteright}s visit to the Unit for Computer Science, MeMaster University.",

year = "1984",

month = sep,

doi = "10.1016/0020-0255(84)90029-X",

language = "English",

volume = "33",

pages = "209--215",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

number = "3",

}

TY - JOUR

T1 - An Inverse Homomorphic Characterization of Full Principal AFL

AU - Yokomori, Takashi

AU - Wood, Derick

N1 - Funding Information: *The work was supported by a Natural Sciences and Engineering Research Council of Canada Grant NO. A-5692, and was carried out during the first author’s visit to the Unit for Computer Science, MeMaster University.

PY - 1984/9

Y1 - 1984/9

N2 - The main result of this paper is: Let L be a full principal AFL closed under context-free substitution. Then there is a fixed language l0 in L such that for each L in L there exist a weak coding h and a homomorphism g such that L = hg-1(L0). As a corollary, it immediately follows that there is a fixed ETOL language L0 such that for each ETOL language L there exist a weak coding h and a homomorphism g such that L = hg-1(L0).

AB - The main result of this paper is: Let L be a full principal AFL closed under context-free substitution. Then there is a fixed language l0 in L such that for each L in L there exist a weak coding h and a homomorphism g such that L = hg-1(L0). As a corollary, it immediately follows that there is a fixed ETOL language L0 such that for each ETOL language L there exist a weak coding h and a homomorphism g such that L = hg-1(L0).

UR - http://www.scopus.com/inward/record.url?scp=0021488612&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021488612&partnerID=8YFLogxK

U2 - 10.1016/0020-0255(84)90029-X

DO - 10.1016/0020-0255(84)90029-X

M3 - Article

AN - SCOPUS:0021488612

SN - 0020-0255

VL - 33

SP - 209

EP - 215

JO - Information Sciences

JF - Information Sciences

IS - 3

ER -

An Inverse Homomorphic Characterization of Full Principal AFL

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this