Detail publikace

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

KALÁB, P. Two-Way Linear PC Grammar Systems and Their Descriptional Complexity. In Proceedings of the 11th Conference Student EEICT 2005. Volume 3. Brno: Publishing house of Brno University of Technology VUTIUM, 2005. p. 546-550. ISBN: 80-214-2890-2.
Název česky
Dvousměrné lineární PC gramatické systémy a jejich popisná složitost
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Kaláb Petr, Ing.
Klíčová slova

Bezkontextová gramatika, levě-rozšířená frontová gramatika, pravě-lineární gramatika, gramatické systémy, komunikační krok, dvousměrné PC gramatické systémy, derivace, pravidlo, větná forma, nonterminál, terminál

Abstrakt

Kromě derivačních a komunikačních kroků dvousměrný PC gramatický systém vykonává také krok redukční, během kterého se nahrazuje pravá strana bezkontextového pravidla stranou levou. Článek dokazuje, že každý neunární rekurzivně spočetný jazyk může být popsán úsporným způsobem centralizovaným dvousměrným PC gramatickým systémem, Γ, s pěti komponentami. Přičemž hlavní komponenta obsahuje pouze tři nontermilány a jediné pravidlo obsahující komunikační symbol. Dále Γ během každého výpočtu provede jediný komunikační krok a všechny větné formy obsahují maximálně dva výskyty nonterminálních symbolů.

Rok
2005
Strany
546–550
Sborník
Proceedings of the 11th Conference Student EEICT 2005
Řada
Volume 3
Konference
STUDENT EEICT 2005, Brno, CZ
ISBN
80-214-2890-2
Vydavatel
Publishing house of Brno University of Technology VUTIUM
Místo
Brno
BibTeX 
@inproceedings{BUT21492,
  author="Petr {Kaláb}",
  title="Two-Way Linear PC Grammar Systems and Their Descriptional Complexity",
  booktitle="Proceedings of the 11th Conference Student EEICT 2005",
  year="2005",
  series="Volume 3",
  pages="546--550",
  publisher="Publishing house of Brno University of Technology VUTIUM",
  address="Brno",
  isbn="80-214-2890-2"
}
Nahoru