Zobrazeno 1 - 10
of 2 273
pro vyhledávání: '"Recursively enumerable language"'
Autor:
György Vaszil, Erzsébet Csuhaj-Varjú
Publikováno v:
Information Processing Letters. 110:902-907
By showing that two nonterminals are sufficient, we present the optimal lower bound on the number of nonterminals of scattered context grammars being able to generate any recursively enumerable language.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Vaszil, György
We show how to generate any recursively enumerable language with a non-returning PC grammar system having eight context-free components. This is an improvement of descriptional complexity compared to the previously known construction where the number
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f9d33df2c4db7efdc4ada113fe451279
Conference
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Journal of Membrane Computing. 4:68-86
A Szilard language is a well-known tool in formal language theory to express the derivation process in a grammar system or grammar. Matrix InsDel (insertion–deletion) system is a well-known variant of InsDel system, where the idea of matrix control
Autor:
Kumar S. Ray, Prithwineel Paul
Publikováno v:
Theoretical Computer Science. 816:19-36
In this paper, we associate the idea of derivation languages with a restricted variant of flat splicing systems where at each step splicing is done with an element from the initial set of words present in the system. We call these flat splicing syste
Autor:
Henning Fernau, Martin Vu
Publikováno v:
Beyond the Horizon of Computability
In this paper, we discuss the addition of substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems, i.e., in addition to insertions and deletions we allow single letter replacements to occur. We invest
Publikováno v:
Theoretical Computer Science. 893:60-71
Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems),
Publikováno v:
Communications of the ACM. 64:131-138
Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated eno
Publikováno v:
Natural Computing. 20:671-689
A matrix insertion-deletion system (or matrix ins-del system) is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model ver