Simple Matrix Grammars and Their Leftmost Variants
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F16%3APU121559" target="_blank" >RIV/00216305:26230/16:PU121559 - isvavai.cz</a>
Result on the web
<a href="http://www.worldscientific.com/doi/10.1142/S0129054116400141" target="_blank" >http://www.worldscientific.com/doi/10.1142/S0129054116400141</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0129054116400141" target="_blank" >10.1142/S0129054116400141</a>
Alternative languages
Result language
angličtina
Original language name
Simple Matrix Grammars and Their Leftmost Variants
Original language description
In essence, simple matrix grammars can be seen as sequences of context-free grammars, referred to as their components, which work in parallel. The present paper demonstrates that two-component simple matrix grammars are as powerful as ordinary matrix grammars. Then, it places three leftmost derivation restrictions upon these grammars and demonstrates that under two of these restrictions, simple matrix grammars are computational complete--that is, they are equivalent with Turing machines. From a historical perspective, concerning simple matrix grammars, the paper also makes several remarks that correct false statements published about them in the past.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
1793-6373
Volume of the periodical
27
Issue of the periodical within the volume
3
Country of publishing house
SG - SINGAPORE
Number of pages
15
Pages from-to
359-373
UT code for WoS article
000378637600005
EID of the result in the Scopus database
2-s2.0-84973547707