Repositorio de producción científica de la Universidad de Sevilla

An infinite hierarchy of languages defined by dP systems

 

Advanced Search
 
Opened Access An infinite hierarchy of languages defined by dP systems
Cites

Show item statistics
Icon
Export to
Author: Paun, Gheorghe
Pérez Jiménez, Mario de Jesús
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2012
Published in: Theoretical Computer Science, 431 (mayo 2012), 4-12.
Document type: Article
Abstract: Here, we continue the study of the recently introduced dP automata. They are symport/antiport P systems consisting of a number of components, each one accepting a string, and working together in recognizing the concatenation of these separate strings; the overall string is distributed to the dP automaton components in a balanced way, i.e., in equal parts up to one symbol, like in the communication complexity area. The question whether or not the number of components induces an infinite hierarchy of the recognized languages was formulated as an open problem in the literature.Wesolve here affirmatively this question (by connecting P automata with right linear simple matrix grammars), then we also briefly discuss the relation between the balanced and the non-balanced way of splitting the input string among components; settling this latter problem remains as a research topic. Some other open problems are also formulated.
Cite: Paun, G. y Pérez Jiménez, M.d.J. (2012). An infinite hierarchy of languages defined by dP systems. Theoretical Computer Science, 431 (mayo 2012), 4-12.
Size: 320.9Kb
Format: PDF

URI: https://hdl.handle.net/11441/79704

DOI: 10.1016/j.tcs.2011.12.053

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)