Detail publikace

Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths

KOUTNÝ, J.; MEDUNA, A. Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika, 2012, vol. 48, no. 1, p. 165-175. ISSN: 0023-5954.
Název česky
Stomem řízené gramatiky s omezeními na řezy a cesty
Typ
článek v časopise
Jazyk
anglicky
Autoři
Koutný Jiří, Ing., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

context-free grammars, tree-controlled grammars, restricted derivation trees, paths, cuts, language families 

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
2-s2.0-84858040799
BibTeX 
@article{BUT91444,
  author="Jiří {Koutný} and Alexandr {Meduna}",
  title="Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths",
  journal="Kybernetika",
  year="2012",
  volume="48",
  number="1",
  pages="165--175",
  issn="0023-5954",
  url="http://www.kybernetika.cz/content/2012/1/165"
}
Nahoru