Membrane Systems Languages Are Polynomial-Time Parsable
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
291 3
Ultima descărcare din IBN:
2017-04-28 11:24
Căutarea după subiecte
similare conform CZU
512.54+512.62 (1)
Algebră (236)
SM ISO690:2012
ALHAZOV, Artiom; CIUBOTARU, Constantin; IVANOV, Sergiu; ROGOZHIN, Yurii. Membrane Systems Languages Are Polynomial-Time Parsable. In: Computer Science Journal of Moldova. 2010, nr. 2(53), pp. 139-148. ISSN 1561-4042.
EXPORT metadate:
Google Scholar
Dublin Core
Computer Science Journal of Moldova
Numărul 2(53) / 2010 / ISSN 1561-4042

Membrane Systems Languages Are Polynomial-Time Parsable

CZU: 512.54+512.62
Pag. 139-148

Alhazov Artiom12, Ciubotaru Constantin1, Ivanov Sergiu13, Rogozhin Yurii3
1 Institute of Mathematics and Computer Science ASM,
2 Hiroshima University,
3 Technical University of Moldova
Disponibil în IBN: 26 aprilie 2016


The focus of this paper is the family of languages generated by transitional non-cooperative P systems without further ingredients. This family can also be defined by so-called time yields of derivation trees of context-free grammars. In this paper we prove that such languages can be parsed in polynomial time, where the degree of polynomial may depend on the number of rules and on the size of the alphabet