Detail publikace

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

MEDUNA, A. TECHET, J.

Originální název

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

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

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.

Klíčová slova

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

Autoři

MEDUNA, A.; TECHET, J.

Rok RIV

2009

Vydáno

2. 1. 2009

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Ročník

410

Číslo

21

Stát

Nizozemsko

Strany od

1961

Strany do

1969

Strany počet

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