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íchlevou derivaci typu dvě s ohledem na počet neterminálů a maticobsahujících více než jedno přepisovací pravidlo. Dokazuje, že tytomaticové gramatiky potřebují pouze devět neterminálů a šest matic délkyaspoň 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
Konference
MOSIS 2003 - Modelling and Simulation of Systems, Brno, CZ
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