Homomorphic Characterizations Are More Powerful Than Dyck Reductions

スポンサーリンク

概要

• 論文の詳細を見る

• Let L be any class of languages, L' be a class of languages which is closed under λ-free homomorphisms, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses X_k, Dyck reduction Red over X_k, and a language L_1 in L' over Σ⋃X_k such that L=Red(L_1)⋂Σ^*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ^*→Σ^*, a Dyck language D over Γ, and a language L_2 in L' over Γ such that L=h(D⋂L_2). We also give an application of this result.

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

著者

• Kimura H

  Kanazawa Univ. Kanazawa‐shi Jpn

• Kimura Haruhiko

  Department Of Electrical & Computer Engineering Faculty Of Engineering Kanazawa University

• Hirose S

  Toyama Univ. Toyama‐shi Jpn

• HIROSE Sadaki

  Department of Engineering, Toyama University

• OKAWA Satoshi

  Department of Computer Software, The University of Aizu

• Okawa Satoshi

  Division Of Applied Life Sciences Graduate School Of Agriculture Kyoto University

• Okawa S

  Department Of Computer Software The University Of Aizu

• Okawa Satoshi

  Department Of Computer Software Of The University Of Aizu

関連論文

• Estimation of Gas Generation Point using Delay of Gas Sensor Responses
• Dyck Reductions are More Powerful Than Homomorphic Characterizations
• Homomorphic Characterizations Are More Powerful Than Dyck Reductions
• Subcellular Localization and Possible Functions of γ-Glutamyltransferase in the Radish (Raphanus sativus L.) Plant
• Purification and Properties of Soluble and Bound γ-Glutamyltransferases from Radish Cotyledon
• Occurrence of Two Forms of γ-Glutamyltransferases in Radish Plant
• Efficient Algorithms for Node Disjoint Path Problems
• Set-To-Set Fault Tolerant Routing in Hypercubes (Special Section on Discrete Mathematics and Its Applications)
• Upper Bounds of the Correlation Functions of a Class of Binary Zero-Correlation-Zone Sequences(Coding Theory)
• 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
• A Ternary Zero-Correlation Zone Sequence Set Having Wide Inter-Subset Zero-Correlation Zone
• Tolosa-Hunt Syndrome Associated with Cytomegalovirus Infection

もっと見る 閉じる

スポンサーリンク