Results 211 to 220 of about 770 (231)
Some of the next articles are maybe not open access.
Pattern Languages Versus Parallel Communicating Grammar Systems
International Journal of Foundations of Computer Science, 1997We compare the power of two (fairly different) recently investigated language identifying devices: patterns and parallel communicating (PC) grammar systems. The simulation of multi-patterns by context-free PC grammar systems is rather obvious, but, unexpectedly, this can be realized also by (non-centralized) PC grammar systems with right-linear ...
Sorina Dumitrescu +2 more
openaire +2 more sources
Bounded communication in parallel communicating grammar systems
J. Inf. Process. Cybern., 1994Summary: We consider parallel grammar systems with a bounded number of communications in any derivation (bounded PCGS) and we study their computational power. Thus, a pumping lemma for such systems is established and infinite hierarchies are obtained. Finally, the languages generated by \(k\)-bounded centralized PCGS of degree 2 are shown to be \((k+ 1)
Cecilia Magdalena Ionescu +1 more
openaire +1 more source
Parallel communicating grammar systems with terminal transmission
Acta Informatica, 2001zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
On the Regularity of Languages Generated by Parallel Communicating Grammar Systems
J. Autom. Lang. Comb., 1996Journal of Automata, Languages and Combinatorics, Volume 1, Number 3, 1996, 181 ...
openaire +2 more sources
A coverability structure for parallel communicating grammar systems
J. Inf. Process. Cybern., 1993Summary: We prove that certain questions (including the circular query problem) about nonreturning context-free parallel communicating grammar systems are recursively solvable, and for this purpose we use some techniques of vector addition systems.
Ferucio Laurentiu Tiplea, Cristian Ene
openaire +1 more source
Further Remarks on Parallel Communicating Grammar Systems without a Master
J. Autom. Lang. Comb., 2000Journal of Automata, Languages and Combinatorics, Volume 5, Number 1, 2000, 59 ...
openaire +2 more sources
Parallel Processing Letters, 2016
Coverability trees offer a finite characterization of all the derivations of a context-free parallel grammar system (CF-PCGS). Their finite nature implies that they necessarily omit some information about these derivations. We demonstrate that the omitted information is most if not all of the time too much, and so coverability trees are not useful as ...
Stefan D. Bruda, Mary Sarah Ruth Wilkin
openaire +1 more source
Coverability trees offer a finite characterization of all the derivations of a context-free parallel grammar system (CF-PCGS). Their finite nature implies that they necessarily omit some information about these derivations. We demonstrate that the omitted information is most if not all of the time too much, and so coverability trees are not useful as ...
Stefan D. Bruda, Mary Sarah Ruth Wilkin
openaire +1 more source
ON CENTRALIZED PARALLEL COMMUNICATING GRAMMAR SYSTEMS WITH CONTEXT-SENSITIVE COMPONENTS
International Journal of Foundations of Computer Science, 2013Centralized parallel communicating grammar systems with context-sensitive components that work in returning mode can only generate context-sensitive languages. Here we show that, when working in nonreturning mode, these grammar systems generate all languages from the nondeterministic time complexity class NEXT = ∪c ≥ 1 NTIME (2c·n).
openaire +1 more source
On the Number of Components and Clusters of Non-returning Parallel Communicating Grammar Systems
2011In this paper, we study the size complexity of nonreturning parallel communicating grammar systems. First we consider the problem of determining the minimal number of components necessary to generate all recursively enumerable languages. We present a construction which improves the currently known best bounds of seven (with three predefined clusters ...
Erzsébet Csuhaj-Varjú, György Vaszil
openaire +1 more source
2013
The paper brings new insights into the complexity of Szilard languages (SZLs) of Parallel Communicating Grammar Systems (PCGSs). We investigate the structure of Szilard words for several classes of PCGSs with context-free rules. We prove that the classes of SZLs of returning centralized and non-returning non-centralized PCGSs are included in circuit ...
Liliana Cojocaru, Erkki Mäkinen
openaire +1 more source
The paper brings new insights into the complexity of Szilard languages (SZLs) of Parallel Communicating Grammar Systems (PCGSs). We investigate the structure of Szilard words for several classes of PCGSs with context-free rules. We prove that the classes of SZLs of returning centralized and non-returning non-centralized PCGSs are included in circuit ...
Liliana Cojocaru, Erkki Mäkinen
openaire +1 more source