Detail publikačního výsledku

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

Anglický název

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

Druh

Článek recenzovaný mimo WoS a Scopus

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.

Klíčová slova

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

Klíčová slova v angličtině

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

2010

Vydáno

02.01.2009

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Svazek

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