Prof. RNDr. Alexander Meduna, CSc.

MEDUNA Alexander a TECHET Jiří. An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations. Theoretical Computer Science. Paris: Elsevier Science, 2009, roč. 410, č. 21, s. 1961-1969. ISSN 0304-3975.
Jazyk publikace:angličtina
Název publikace:An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations
Název (cs):Nekonečná hierarchie jazykových rodin generovaná gramatikami s rozptýleným kontextem za použití n-limitovaných derivací
Strany:1961-1969
Rok:2009
Časopis:Theoretical Computer Science, roč. 410, č. 21, Paris, FR
ISSN:0304-3975
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
Anotace
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=8832}
}

Vaše IPv4 adresa: 34.237.75.18
Přepnout na https