Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Koutný Jiří, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this adi- tional restriction does not affect the generative power of these grammars.

Klíčová slova

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

URL
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"
}
Projekty
Bezkontextové gramatiky a zásobníkové automaty, MŠMT, KONTAKT, MEB041003, zahájení: 2010-01-01, ukončení: 2011-12-31, ukončen
Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů, GAČR, Doktorské granty, GD102/09/H042, zahájení: 2009-01-30, ukončení: 2012-12-31, ukončen
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru