Detail výsledku

Context-Free Grammars over Free Groups

BIDLO, R. Context-Free Grammars over Free Groups. Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling. Ostrava: Marq software s.r.o., 2005. p. 95-100. ISBN: 80-86840-09-3.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Bidlo Radek, Ing., Ph.D., UIFS (FIT)
Abstrakt

This document introduces the notion of context-free grammar over a freegroup and examines the generative capacity of this structure. Thealgorithm of transformation of any type-0 grammar to an equivalentcontext-free grammar over a free group is demonstrated. As the mainresult, the equivalence of the family of recursively enumerablelanguages and the family of languages generated by context-freegrammars over free groups is proved.

Klíčová slova

Context-Free Grammars, Penttonen Normal Forms, Free Groups, Recursively Enumerable Languages

Rok
2005
Strany
95–100
Sborník
Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling
Konference
8th International Conference on Information Systems Implementation and Modelling
ISBN
80-86840-09-3
Vydavatel
Marq software s.r.o.
Místo
Ostrava
BibTeX 
@inproceedings{BUT21454,
  author="Radek {Bidlo}",
  title="Context-Free Grammars over Free Groups",
  booktitle="Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling",
  year="2005",
  pages="95--100",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}
Projekty
Optimally Integrated Models of Modern Information Technologies, GAČR, Standardní projekty, GA201/04/0441, zahájení: 2004-01-01, ukončení: 2006-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru