Detail publikačního výsledku

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

MASOPUST, T.

Originální název

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

Anglický název

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

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

MASOPUST, T.

Rok RIV

2010

Vydáno

03.01.2009

Nakladatel

Springer Verlag

Místo

Springer-Verlag Berlin Heidelberg

ISBN

978-3-642-00981-5

Kniha

LATA 2009 proceedings

Edice

Lecture notes in computer science

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Svazek

2009

Číslo

5457

Stát

Spolková republika Německo

Strany od

554

Strany do

565

Strany počet

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/"
}