Detail publikace

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

KALÁB Petr. Two-Way Linear PC Grammar Systems and Their Descriptional Complexity. In: Proceedings of the 11th Conference Student EEICT 2005. Volume 3. Brno: Nakladatelství Vysokého učení technického v Brně VUTIUM, 2005, s. 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
angličtina
Autoři
Kaláb Petr, Ing. (UIFS FIT VUT)
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
Nakladatelství Vysokého učení technického v Brně VUTIUM
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7773,
   author = "Petr Kal\'{a}b",
   title = "Two-Way Linear PC Grammar Systems and Their Descriptional Complexity",
   pages = "546--550",
   booktitle = "Proceedings of the 11th Conference Student EEICT 2005",
   series = "Volume 3",
   year = 2005,
   location = "Brno, CZ",
   publisher = "Publishing house of Brno University of Technology VUTIUM",
   ISBN = "80-214-2890-2",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7773"
}
Nahoru