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

Type

journal article - other

Language

English

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.

Keywords

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

Authors

MEDUNA, A.; TECHET, J.

RIV year

2009

Released

2. 1. 2009

ISBN

0304-3975

Periodical

Theoretical Computer Science

Year of study

410

Number

21

State

Kingdom of the Netherlands

Pages from

1961

Pages to

1969

Pages count

9

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