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