Computational power of dynamic threshold neural P systems for generating string languages
| Autor: | Wenmei Yi, Xiaohui Luo, Hong Peng, Yue Huang, Jun Wang, Qian Yang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Algebra
Recursively enumerable language General Computer Science Regular language Computer science Completeness (order theory) String (computer science) Universality (philosophy) Computer Science::Programming Languages Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Function (mathematics) Theoretical Computer Science Power (physics) |
| Zdroj: | Theoretical Computer Science. 851:77-91 |
| ISSN: | 0304-3975 |
| Popis: | Inspired from spiking and dynamic mechanisms of neurons, dynamic threshold neural P systems (DTNP systems) have been developed and their computational completeness as number-generating/accepting devices and function computing devices has been investigated. However, a universality result of DTNP systems as language generators has not been established so far. This paper discusses computational power of DTNP systems as language generators. We first discuss the relationship between the languages generated by DTNP systems and finite languages, and then prove that regular languages can be generated by finite DTNP systems. Moreover, we prove that recursively enumerable languages can be characterized by projections of inverse-morphic images of the languages generated by DTNP systems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect