A homomorphic characterization of recursively enumerable languages (Q1061494)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A homomorphic characterization of recursively enumerable languages |
scientific article |
Statements
A homomorphic characterization of recursively enumerable languages (English)
0 references
1985
0 references
We give a homomorphic characterization of the class of recursively enumerable languages: it is shown that any recursively enumerable language is the homomorphic image of the intersection of a Dyck language and a 'minimal linear' language.
0 references
linear language
0 references
Dyck language
0 references
0 references
