Detail publikace
Two-way PC Grammar Systems Based on Regular Grammars
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
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 třemi 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ů. Na závěr článku jsou diskutovány některé varianty těchto systémů.
@inproceedings{BUT16915,
author="Petr {Kaláb}",
title="Two-way PC Grammar Systems Based on Regular Grammars",
booktitle="Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modeling",
year="2004",
series="1st edition",
pages="111--118",
address="Ostrava",
isbn="80-85988-99-2"
}