Generalized One-Sided Forbidding Grammars

Result code in IS VaVaI

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

Result on the web

<a href="http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703" target="_blank" >http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1080/00207160.2012.723703" target="_blank" >10.1080/00207160.2012.723703</a>

Result language

angličtina

Original language name

Generalized One-Sided Forbidding Grammars

Original language description

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.

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

International Journal of Computer Mathematics

ISSN

0020-7160

e-ISSN

1029-0265

Volume of the periodical

90

Issue of the periodical within the volume

2

Country of publishing house

GB - UNITED KINGDOM

Number of pages

11

Pages from-to

172-182

UT code for WoS article

—

EID of the result in the Scopus database

—