Publication detail

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

MASOPUST, T.

Original Title

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

Type

conference paper

Language

English

Original Abstract

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.

Keywords

Formal languages; context condition; context-free grammar; random context grammar; semi-conditional grammar; simple semi-conditional grammar; erasing production; generative power.

Authors

MASOPUST, T.

RIV year

2009

Released

3. 1. 2009

Publisher

Springer Verlag

Location

Springer-Verlag Berlin Heidelberg

ISBN

978-3-642-00981-5

Book

LATA 2009 proceedings

Edition

Lecture notes in computer science

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Year of study

2009

Number

5457

State

Federal Republic of Germany

Pages from

554

Pages to

565

Pages count

12

URL

http://grammars.grlmc.com/LATA2009/

BibTex

@inproceedings{BUT33771,
  author="Tomáš {Masopust}",
  title="A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions",
  booktitle="LATA 2009 proceedings",
  year="2009",
  series="Lecture notes in computer science",
  journal="Lecture Notes in Computer Science",
  volume="2009",
  number="5457",
  pages="554--565",
  publisher="Springer Verlag",
  address="Springer-Verlag Berlin Heidelberg",
  isbn="978-3-642-00981-5",
  issn="0302-9743",
  url="http://grammars.grlmc.com/LATA2009/"
}