A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

Popis výsledku v původním jazyce

This paper answers three open questions concerning the generative power of some simple variants of context-free grammars regulated by context conditions. Specifically, it discusses the generative power of so-called context-free semi-conditional grammars(which are random context grammars where permitting and forbidding sets are replaced with permitting and forbidding strings) where permitting and forbidding strings of each production are of length no more than one, and of simple semi-conditional grammars where, in addition, no production has attached both a permitting and a forbidding string. Finally, this paper also presents some normal form results, an overview of known results, and unsolved problems.<br>

Název v anglickém jazyce

A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

Popis výsledku anglicky

This paper answers three open questions concerning the generative power of some simple variants of context-free grammars regulated by context conditions. Specifically, it discusses the generative power of so-called context-free semi-conditional grammars(which are random context grammars where permitting and forbidding sets are replaced with permitting and forbidding strings) where permitting and forbidding strings of each production are of length no more than one, and of simple semi-conditional grammars where, in addition, no production has attached both a permitting and a forbidding string. Finally, this paper also presents some normal form results, an overview of known results, and unsolved problems.<br>

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multiinformační technologie: Teorie, modely a metody</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

Kód důvěrnosti údajů

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

Název statě ve sborníku

LATA 2009 proceedings

ISBN

978-3-642-00981-5

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer Verlag

Místo vydání

Springer-Verlag Berlin Heidelberg

Místo konání akce

Tarragona

Datum konání akce

2. 4. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—