Contextual array grammars with matrix control, regular control languages, and tissue P systems control
Закрыть
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
721 0
SM ISO690:2012
ALHAZOV, Artiom, FERNAU, Henning, FREUND, Rudolf, IVANOV, Sergiu, SIROMONEY, Rani S., SUBRAMANIAN, K.G.. Contextual array grammars with matrix control, regular control languages, and tissue P systems control. In: Theoretical Computer Science, 2017, nr. 682, pp. 5-21. ISSN 0304-3975. DOI: https://doi.org/10.1016/j.tcs.2017.03.012
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Theoretical Computer Science
Numărul 682 / 2017 / ISSN 0304-3975 /ISSNe 1879-2294

Contextual array grammars with matrix control, regular control languages, and tissue P systems control

DOI:https://doi.org/10.1016/j.tcs.2017.03.012

Pag. 5-21

Alhazov Artiom1, Fernau Henning2, Freund Rudolf3, Ivanov Sergiu4, Siromoney Rani S.5, Subramanian K.G.6
 
1 Institute of Mathematics and Computer Science ASM,
2 Universit¨at Trier,
3 Technische Universität Wien, Institut für Computersprachen,
4 Universitatea Paris-Est Marne-La-Vallee, Franţa,
5 Chennai Mathematical Institute,
6 Liverpool Hope University
 
 
Disponibil în IBN: 19 februarie 2018


Rezumat

We consider d-dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d≥2, d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

Cuvinte-cheie
Array grammar, Matrix control, Regular control,

Tissue P system