Ponencia
Further Results on the Power of Generating APCol Systems
Autor/es | Ciencialová, Lucie
Cienciala, Ludek Csuhaj-Varjú, Erzsébet |
Coordinador/Director | Research Group on Natural Computing |
Fecha de publicación | 2019 |
Fecha de depósito | 2019-11-21 |
Publicado en |
|
Resumen | In this paper we continue our investigations in APCol systems (Automatonlike
P colonies), variants of P colonies where the environment of the agents is given by a
string and the functioning of the system resembles to the ... In this paper we continue our investigations in APCol systems (Automatonlike P colonies), variants of P colonies where the environment of the agents is given by a string and the functioning of the system resembles to the functioning of standard nite automaton. We rst deal with the concept of determinism in these systems and compare deterministic APCol systems with deterministic register machines. Then we focus on generating non-deterministic APCol systems with only one agent. We show that these systems are as powerful as 0-type grammars, i.e., generate any recursively enumerable language. If the APCol system is non-erasing, then any context-sensitive language can be generated by a non-deterministic APCol systems with only one agent. |
Cita | Ciencialová, L., Cienciala, L. y Csuhaj-Varjú, E. (2019). Further Results on the Power of Generating APCol Systems. En BWMC 2019: Seventeenth Brainstorming Week on Membrane Computing (79-90), Sevilla, España: Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
079_APCol.pdf | 212.6Kb | [PDF] | Ver/ | |