Detail výsledku

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

MEDUNA, A.; TECHET, J. An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations. Theoretical Computer Science, 2009, vol. 410, no. 21, p. 1961-1969. ISSN: 0304-3975.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Techet Jiří, Ing., Ph.D.
Abstrakt

This paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. It demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. In addition, it proves analogous results for unordered scattered context grammars. Some consequences of these results are derived and open problems formulated.

Klíčová slova

scattered context grammars, unordered scattered context grammars, left derivation restriction, generative power, infinite hierarchy of language families

Rok
2009
Strany
1961–1969
Časopis
Theoretical Computer Science, roč. 410, č. 21, ISSN 0304-3975
BibTeX 
@article{BUT49308,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations",
  journal="Theoretical Computer Science",
  year="2009",
  volume="410",
  number="21",
  pages="1961--1969",
  issn="0304-3975"
}
Projekty
Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů, GAČR, Doktorské granty, GD102/05/H050, zahájení: 2005-01-01, ukončení: 2008-12-31, ukončen
Multiinformační technologie, GAČR, Standardní projekty, GA201/07/0005, zahájení: 2007-01-01, ukončení: 2009-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