| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
doi-tr-125