The Leftmost Derivation of Type Two in Matrix Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F03%3APU42552" target="_blank" >RIV/00216305:26230/03:PU42552 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
The Leftmost Derivation of Type Two in Matrix Grammars
Original language description
This contribution discusses the descriptional complexity of matrix grammars using left-most derivation of type two with respect to the number of nonterminals and matrices with two or more productions. It proves that these matrix grammars need only nine nonterminals and six matrices of length two or more to generate recursively enumerable languages.
Czech name
Levá derivace typu dvě v maticových gramatikách
Czech description
Tento příspěvěk se zabývá složitostí maticových gramatik používajících levou derivaci typu dvě s ohledem na počet neterminálů a matic obsahujících více než jedno přepisovací pravidlo. Dokazuje, že tyto maticové gramatiky potřebují pouze devět neterminálůa šest matic délky aspoň dvě, aby byly schopny generovat všechny rekurzivně spočetné jazyky.<br>
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2003
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
Article name in the collection
Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling
ISBN
80-85988-84-4
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
195-199
Publisher name
NEUVEDEN
Place of publication
Ostrava
Event location
Brno
Event date
Apr 28, 2003
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—