帰納的に可算な言語の線形言語の小さいクラスによる特性化

スポンサーリンク

概要

論文の詳細を見る
言語理論の大きな課題の1つである言語の族の特性化について、小さな言語の族で準同型写像を用いることによって大きな言語の族を特性化する研究がなされている。帰納的に可算な言語の族の特性化について2つの決定性言語の共通部分の準同型写像による像、2つの線形言語の共通部分の準同型写像による像、あるいは、Dyck言語と極小線形言語との共通部分の準同型写像による像で表わすもの、線形言語の部分族である右長、同長、左長言語の族を用いた特性化などが知られている。本稿においては、文献の特性化の結果の証明に用いられている文法について検討し、さらに小さい言語の族による特性化が可能であることを示す。すなわち、任意の帰納的に可算な言語は、(1,2)線形言語と(1,1)極小線形言語との共通部分の準同型写像で表わすことができることを示す。
1990-09-04

著者

関連論文

スポンサーリンク