A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
Original language description
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>
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multi-information technologies: Theory, models, and methods</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
LATA 2009 proceedings
ISBN
978-3-642-00981-5
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer Verlag
Place of publication
Springer-Verlag Berlin Heidelberg
Event location
Tarragona
Event date
Apr 2, 2009
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—