An inverse homomorphic characterization of full principal AFL
type: Item
instance of: scholarly article
title: An inverse homomorphic characterization of full principal AFL
zbMATH Open document ID: 0565.68073
DOI: 10.1016/0020-0255(84)90029-X
author: Takashi Yokomori
author: D. Wood
published in: Information Sciences
publication date: 1984-01-01T00:00:00Z
review text: In spite of the quite laborious proof, the main result of this paper acquires a concise and elegant form: Let \({\mathcal L}\) be a full principal AFL closed under context-free substitution. Then there is a fixed language \(L_ 0\) in \({\mathcal L}\) such that for each L in \({\mathcal L}\) there exist a weak coding h and a homomorphism g such that \(L=hg^{-1}(L_ 0).\) An immediate corollary shows that there is a fixed ETOL language \(L_ 0\) such that for each ETOL language L there exist h and g as above such that \(L=hg^{-1}(L_ 0)\).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3902066
zbMATH Keywords: full principal AFL
zbMATH Keywords: ETOL language
Wikidata QID: Q123199862
reviewed by: R. Andonie
MaRDI profile type: Publication
cites work: On some families of languages related to developmental systems
cites work: Q3870326
cites work: Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
cites work: Q4089754
cites work: The Hardest Context-Free Language
cites work: Q4140407
cites work: Q5678435
full work available at URL: 0020-0255(84)90029-x
OpenAlex ID: W2006459891
description: scientific article; zbMATH DE number 3902066