Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

Originální 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.

Anglický 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.

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",
  annote="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.",
  address="NEUVEDEN",
  chapter="49308",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Theoretical Computer Science",
  number="21",
  volume="410",
  year="2009",
  month="january",
  pages="1961--1969",
  publisher="NEUVEDEN",
  type="journal article - other"
}