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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU82559" target="_blank" >RIV/00216305:26230/09:PU82559 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.<br>

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BD - Information theory

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2009

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Volume of the periodical

410

Issue of the periodical within the volume

21

Country of publishing house

FR - FRANCE

Number of pages

9

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—