Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Membrane Systems Languages Are Polynomial-Time Parsable
Authors: Alhazov Artiom, Ciubotaru Constantin, Ivanov Sergiu, Rogojin Iurie
– 0.17 Mb
Abstract
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.A. Alhazov1,2, C. Ciubotaru1, S. Ivanov1,3, Yu. Rogozhin1
1 Institute of Mathematics and Computer Science
Academy of Sciences of Moldova
5 Academiei str., Chișinău, MD 2028, Moldova
E-mail: , , ,
2 FCS, Department of Information Engineering
Graduate School of Engineering
Hiroshima University,
Higashi-Hiroshima 739-8527 Japan
3 Faculty of Computers,
Informatics and Microelectronics,
Technical University of Moldova,
Ştefan cel Mare 168, Chișinău MD 2004 Moldova
1 Institute of Mathematics and Computer Science
Academy of Sciences of Moldova
5 Academiei str., Chișinău, MD 2028, Moldova
E-mail: , , ,
2 FCS, Department of Information Engineering
Graduate School of Engineering
Hiroshima University,
Higashi-Hiroshima 739-8527 Japan
3 Faculty of Computers,
Informatics and Microelectronics,
Technical University of Moldova,
Ştefan cel Mare 168, Chișinău MD 2004 Moldova
Fulltext
– 0.17 Mb
Contents
- Gheorghe Păun (A tribute in honour of his 60th birthday)
- Investigations on Natural Computing in the Institute of Mathematics and Computer Science
- Membrane Systems Languages Are Polynomial-Time Parsable
- Minimal Parallelism and Number of Membrane Polarizations
- On computational properties of gene assembly in ciliates
- Recent Developments on Insertion-Deletion Systems
- Simulator of P-Systems with String Replication Developed in Framework of P-Lingua 2.1
