Parallel communicating grammar systems with bounded resources
Theoretical Computer Science, 2002 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Erzsébet Csuhaj-Varjú, György Vaszil
openaire +4 more sources
On the number of components for some parallel communicating grammar systems
Theoretical Computer Science, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Jürgen Dassow, Bianca Truthe
openaire +4 more sources
On the computational completeness of context-free parallel communicating grammar systems
Theoretical Computer Science, 1999 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Erzsébet Csuhaj-Varjú, György Vaszil
openaire +3 more sources
Parallel communicating grammar systems with regular control and skeleton preserving FRR automata
Theoretical Computer Science, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dana Pardubská +2 more
openaire +4 more sources
On the Size Complexity of Non-Returning Context-Free PC Grammar Systems [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Improving the previously known best bound, we show that any recursively enumerable language can be generated with a non-returning parallel communicating (PC) grammar system having six context-free components.
Erzsébet Csuhaj-Varjú, György Vaszil
doaj +1 more source
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
Poetic Judgement in Everyday Speech
PhilosophiesSpeaking is a highly conventional enterprise. But unusual usages are, nonetheless, frequently encountered. Some of these novelties fall flat, while others find favour, to the extent of entering common usage.
Paul Magee
doaj +1 more source
Some decision problems for parallel communicating grammar systems
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 Tiplea +3 more
openaire +1 more source
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