Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages

スポンサーリンク

概要

• 論文の詳細を見る

• 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).

• 社団法人電子情報通信学会の論文
• 1996-02-25

著者

• Hirose S

  Toyama Univ. Toyama‐shi Jpn

• HIROSE Sadaki

  Department of Engineering, Toyama University

• Okawa Satoshi

  Department Of Computer Software Of The University Of Aizu

関連論文

• Dyck Reductions are More Powerful Than Homomorphic Characterizations
• Homomorphic Characterizations Are More Powerful Than Dyck Reductions
• Efficient Algorithms for Node Disjoint Path Problems
• Set-To-Set Fault Tolerant Routing in Hypercubes (Special Section on Discrete Mathematics and Its Applications)
• Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages
• A Generalized Construction of Zero-Correlation Zone Sequence Set with Sequence Subsets
• Tolosa-Hunt Syndrome Associated with Cytomegalovirus Infection

スポンサーリンク