An infinite hierarchy of languages defined by dP systems

TitleAn infinite hierarchy of languages defined by dP systems
Publication TypeJournal Papers
Year of Publication2012
AuthorsPaun, G., & Pérez-Jiménez M. J.
Journal TitleTheoretical Computer Science
PublisherElsevier
Place PublishedAmsterdam (The Netherlands)
Volume431 (2012)
Pages4-12
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. We solve 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.

KeywordsMembrane computing; dP system; Infinite hierarchy; Simple matrix grammar
URLhttp://www.sciencedirect.com/science/article/pii/S030439751101019X
Impact Factor

0.489

Ranking

78/100 - Q4

ISSN Number0304-3975
DOI10.1016/j.tcs.2011.12.053