Publication detail

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

MEDUNA, A. TECHET, J.

Original Title

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

English Title

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

Type

journal article - other

Language

en

Original Abstract

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.

English abstract

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.

Keywords

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

RIV year

2009

Released

02.01.2009

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

0304-3975

Periodical

Theoretical Computer Science

Year of study

410

Number

21

State

NL

Pages from

1961

Pages to

1969

Pages count

9

Documents

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"
}