Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages
Summary :
In this paper, we give a direct proof of the result of Latteux and Turakainen 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 reductions (which reduce pairs of parentheses to the empty word).
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.2 pp.161-164
- Publication Date
- 1996/02/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Automata,Languages and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Sadaki HIROSE, Satoshi OKAWA, "Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 2, pp. 161-164, February 1996, doi: .
Abstract: In this paper, we give a direct proof of the result of Latteux and Turakainen 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 reductions (which reduce pairs of parentheses to the empty word).
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_2_161/_p
Copy
@ARTICLE{e79-d_2_161,
author={Sadaki HIROSE, Satoshi OKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages},
year={1996},
volume={E79-D},
number={2},
pages={161-164},
abstract={In this paper, we give a direct proof of the result of Latteux and Turakainen 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 reductions (which reduce pairs of parentheses to the empty word).},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages
T2 - IEICE TRANSACTIONS on Information
SP - 161
EP - 164
AU - Sadaki HIROSE
AU - Satoshi OKAWA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 1996
AB - In this paper, we give a direct proof of the result of Latteux and Turakainen 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 reductions (which reduce pairs of parentheses to the empty word).
ER -
English
