Detail publikace

Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths

KOUTNÝ Jiří a MEDUNA Alexander. Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika, roč. 48, č. 1, 2012, s. 165-175. ISSN 0023-5954. Dostupné z: http://www.kybernetika.cz/content/2012/1/165
Název česky
Stomem řízené gramatiky s omezeními na řezy a cesty
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt

Nejprve diskutujeme stromem řízené gramatiky, v nichž jsou cesty jejich derivačních stromů omezeny řídicími jazyky. Článek dokazuje, že pokud je řídicí jazyk regulární, pak takové systémy generují třídu bezkontextových jazyků. Pak zavádíme řízení řezů derivačních stromů bezkontextových gramatik a ukazujeme, že pokud je jazyk řídicí řezy regulární, pak takové systémy generují třídu rekurzivně vyčíslitelných jazyků. Nakonec zavádíme relaci uspořádání řízených řezů a ukazujeme, že takové omezení nemá vliv na generativní sílu těchto systémů.

Rok
2012
Strany
165-175
Časopis
Kybernetika, roč. 48, č. 1, ISSN 0023-5954
EID Scopus
BibTeX
@ARTICLE{FITPUB9699,
   author = "Ji\v{r}\'{i} Koutn\'{y} and Alexander Meduna",
   title = "Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths",
   pages = "165--175",
   journal = "Kybernetika",
   volume = 48,
   number = 1,
   year = 2012,
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9699"
}
Nahoru