DYCK REDUCTIONS OF MINIMAL LINEAR LANGUAGES YIELD THE FULL CLASS OF RECURSIVELY-ENUMERABLE LANGUAGES

Authors
HIROSE S OKAWA S
Citation
S. Hirose et S. Okawa, DYCK REDUCTIONS OF MINIMAL LINEAR LANGUAGES YIELD THE FULL CLASS OF RECURSIVELY-ENUMERABLE LANGUAGES, IEICE transactions on information and systems, E79D(2), 1996, pp. 161-164
Citations number
20
Categorie Soggetti
Computer Science Information Systems
Journal title
IEICE transactions on information and systems → ACNP
ISSN journal
09168532
Volume
E79D
Issue
2
Year of publication
1996
Pages
161 - 164
Database
ISI
SICI code
0916-8532(1996)E79D:2<161:DROMLL>2.0.ZU;2-Q
Abstract
In this paper, we give a direct proof of the result of Latteux and Tur akainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reduc tions (which reduce pairs of parentheses to the empty word).