<テクニカルレポート>
Elementary Formal Systems with the subword property characterize the class P

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 An EFS is a kind of a grammar and generates a language. During an Em's with the subword property generating an output, once a word appears, the word is a subword of the output. The property is not onl...y natural and simple but ample to describe a computation of a polynomial time-bounded deterministic Turing machine. Our main result is that the class of elementary formal systems (EFSs for short) with the subword property is equal to the class P. We also give a membership problem for EFSs with the subword property and show that the class of languages generated by EFSs with the property is closed under some operations.続きを見る

本文情報を非表示

doi-tr-125 pdf 636 KB 62  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20