Spiking neural P systems with extended rules: universality and languages
| Autor: | Mihai Ionescu, Andrei Păun, Haiming Chen, Tseren-Onolt Ishdorj, Gheorghe Paun, Mario J. Pérez-Jiménez |
|---|---|
| Přispěvatelé: | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, Ministerio de Educación y Ciencia (MEC). España, Junta de Andalucía |
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
Theoretical computer science Chomsky hierarchy Complex system Spiking Neural P systems Membrane Computing Turing computability Computer Science Applications Universality (dynamical systems) Recursively enumerable language Regular language Theory of computation Membrane computing Mathematics |
| Zdroj: | idUS. Depósito de Investigación de la Universidad de Sevilla instname |
| ISSN: | 1572-9796 1567-7818 |
| DOI: | 10.1007/s11047-006-9024-6 |
| Popis: | We consider spiking neural P systems with rules allowed to introduce zero, one, or more spikes at the same time. The motivation comes both from constructing small universal systems and from generating strings; previous results from these areas are briefly recalled. Then, the computing power of the obtained systems is investigated, when considering them as number generating and as language generating devices. In the first case, a simpler proof of universality is obtained, while in the latter case we find characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of standard rules). The relationships with regular languages are also investigated. Ministerio de Educación y Ciencia TIN2005-09345-C03-01 Junta de Andalucía TIC-581 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink