Detail publikace

An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations

MEDUNA Alexander a TECHET Jiří. An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations. Theoretical Computer Science, roč. 410, č. 21, 2009, s. 1961-1969. ISSN 0304-3975.
Název česky
Nekonečná hierarchie jazykových rodin generovaná gramatikami s rozptýleným kontextem za použití n-limitovaných derivací
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
Klíčová slova

gramatiky s rozptýleným kontextem, neuspořádané gramatiky s rozptýleným kontextem, nejlevější derivace, vyjadřovací síla gramatik, nekonečná hierarchie jazykových rodin

Abstrakt

V tomto článku jsou zavedeny gramatiky s rozptýleným kontextem bez vymazávacích pravidel, ve kterých je pravidlo aplikováno vždy v rámci prvních n nonterminálů větné formy. Je dokázáno, že na základě tohoto omezení vznikne nekonečná hierarchie jazykových rodin, z nichž každá je vlastní podmnožinou rodiny kontextových jazyků. Podobný výsledek je dokázán i pro neuspořádané gramatiky s rozptýleným kontextem. Článek dále diskutuje důsledky těchto výsledků a uvádí některé otevřené problémy.

Rok
2009
Strany
1961-1969
Časopis
Theoretical Computer Science, roč. 410, č. 21, ISSN 0304-3975
Vydavatel
Elsevier Science
BibTeX 
@ARTICLE{FITPUB8832,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations",
   pages = "1961--1969",
   journal = "Theoretical Computer Science",
   volume = 410,
   number = 21,
   year = 2009,
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8832"
}
Nahoru