Parallel communicating grammar systems with context-free components are Turing complete for any communication model
type: Item
instance of: scholarly article
title: Parallel communicating grammar systems with context-free components are Turing complete for any communication model
zbMATH Open document ID: 1404.68064
author: Mary Sarah Ruth Wilkin
author: Stefan D. Bruda
published in: Acta Universitatis Sapientiae. Informatica
publication date: 2017-02-07T00:00:00Z
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6681558
zbMATH Keywords: formal languages
zbMATH Keywords: theory of computation
zbMATH Keywords: formal grammar
zbMATH Keywords: parallel communicating grammar system
zbMATH Keywords: Turing completeness
MaRDI profile type: Publication
full work available at URL: ausi-2016-0007
OpenAlex ID: W2576274719
cites work: PC grammar systems with five context-free components generate all recursively enumerable languages.
cites work: Q4782094
cites work: On the computational completeness of context-free parallel communicating grammar systems
cites work: Q5146519
cites work: Q4763798
cites work: Nonreturning PC grammar systems can be simulated by returning systems
cites work: Turing machines with restricted memory access
cites work: Q4198056
cites work: Q3798273
cites work: Reformulating Global Grammar Constraints
cites work: On the computational power of context-free PC grammar systems
DOI: 10.1515/AUSI-2016-0007
description: scientific article; zbMATH DE number 6681558