| Creator |
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
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.show more
|
Export Mendeley
doi-tr-125