Parallel communicating grammar systems with bounded resources [PDF]
Theoretical Computer Science, 2002 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
György Vaszil
exaly +4 more sources
On the computational completeness of context-free parallel communicating grammar systems [PDF]
Theoretical Computer Science, 1999 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
György Vaszil
exaly +3 more sources
On the number of components for some parallel communicating grammar systems [PDF]
Theoretical Computer Science, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Jürgen Dassow, Bianca Truthe
exaly +4 more sources
Some decision problems for parallel communicating grammar systems [PDF]
Theoretical Computer Science, 1994 AbstractIn this paper we investigate several decision problems for parallel communicating grammar systems: the enabling, circularity, centralizing, conflict-freeness, boundedness, membership, equivalence, inclusion, emptiness and finiteness problems.
Ferucio Laurentiu Țiplea
exaly +3 more sources
On context-free parallel communicating grammar systems: synchronization, communication, and normal forms [PDF]
Theoretical Computer Science, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
György Vaszil
exaly +3 more sources
Parallel communicating grammar systems with regular control and skeleton preserving FRR automata [PDF]
Theoretical Computer Science, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Martin Platek, Friedrich Otto
exaly +4 more sources
On the power of parallel communicating grammar systems with right-linear components [PDF]
RAIRO - Theoretical Informatics and Applications, 1997 Summary: We settle here two problems concerning the generative power of parallel communicating grammar systems with right-linear components: (1) each linear language can be generated by a non-centralized returning system, (2) the family of languages generated by centralized returning systems is incomparable with the family of languages generated by non-
Sorina Dumitrescu, Gheorghe Paun
openaire +2 more sources
On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata [PDF]
, 2009 This paper contributes to the study of Freely Rewriting Re-starting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS) as formalizations of the linguistic method of analysis by reduction . For PCGS we study two complexity measures called generation complexity and distribution complexity , and we prove that a PCGS *** , for which ...
Dana Pardubská +2 more
openaire +1 more source
Parallel communicating grammar systems with context-free components are Turing complete for any communication model [PDF]
Acta Universitatis Sapientiae, Informatica, 2016 Abstract Parallel Communicating Grammar Systems (PCGS) were introduced as a language-theoretic treatment of concurrent systems. A PCGS extends the concept of a grammar to a structure that consists of several grammars working in parallel, communicating with each other, and so contributing to the generation of strings.
Wilkin Mary Sarah Ruth, Bruda Stefan D.
openaire +2 more sources
Splicing Context-Free Matrix Grammars using Parallel Communicating Grammar Systems
International Journal of Innovative Technology and Exploring Engineering, 2019 Extensive research on splicing of strings in DNA computing has established important theoretical results in computational theory. Further, splicing on strings has been extended to arrays in[2]. In this context, we propose, a grammar system, using queries to splice context-free matrix grammars and show that the language generated by this grammar system ...
M. Iffath Mubeen*, J.D. Emerald
openaire +1 more source