Left Random Context ET0L Grammars

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F13%3APU106272" target="_blank" >RIV/00216305:26230/13:PU106272 - isvavai.cz</a>

Result on the web

<a href="http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2" target="_blank" >http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-2013-811" target="_blank" >10.3233/FI-2013-811</a>

Result language

angličtina

Original language name

Left Random Context ET0L Grammars

Original language description

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.

Czech name

—

Czech description

—

Type

J_ost - Miscellaneous article in a specialist periodical

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2013

Confidentiality

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

Name of the periodical

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

1875-8681

Volume of the periodical

123

Issue of the periodical within the volume

3

Country of publishing house

PL - POLAND

Number of pages

16

Pages from-to

289-304

UT code for WoS article

—

EID of the result in the Scopus database

—