Detail publikace

The Leftmost Derivation of Type Two in Matrix Grammars

ŠKRKAL, O. The Leftmost Derivation of Type Two in Matrix Grammars. Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling. Ostrava: 2003. p. 195-199. ISBN: 80-85988-84-4.
Název česky
Levá derivace typu dvě v maticových gramatikách
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Škrkal Oto, Ing.
Klíčová slova

Formal language theory, regulated rewriting, matrix grammars, canonical derivations, complexity reduction.

Abstrakt

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.

Rok
2003
Strany
195–199
Sborník
Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling
ISBN
80-85988-84-4
Místo
Ostrava
BibTeX 
@inproceedings{BUT13993,
  author="Oto {Škrkal}",
  title="The Leftmost Derivation of Type Two in Matrix Grammars",
  booktitle="Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling",
  year="2003",
  pages="195--199",
  address="Ostrava",
  isbn="80-85988-84-4"
}
Nahoru