Publication detail

CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages

MEDUNA, A. MARTIŠKO, J.

Original Title

CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages

Type

conference paper

Language

English

Original Abstract

The paper deals with the modified version of L(CS) = L(PSCG) problem. The modified version of the problem compares the generative power of context sensitive grammars with the generative power of CD grammar systems with propagating scattered context components. The paper gives a proof that these two models have the same generative power.

Keywords

CD Grammar Systems, Context Sensitive Grammars, Propagating Scattered context Grammars,

Authors

MEDUNA, A.; MARTIŠKO, J.

Released

4. 9. 2017

Publisher

Open Publishing Association

Location

Debrecen

ISBN

2075-2180

Periodical

Electronic Proceedings in Theoretical Computer Science, EPTCS

Year of study

2017

Number

252

State

unknown

Pages from

170

Pages to

179

Pages count

10

URL

https://arxiv.org/abs/1708.06467v1

BibTex

@inproceedings{BUT144440,
  author="Alexandr {Meduna} and Jakub {Martiško}",
  title="CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages",
  booktitle="15th International Conference on Automata and Formal Languages",
  year="2017",
  journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
  volume="2017",
  number="252",
  pages="170--179",
  publisher="Open Publishing Association",
  address="Debrecen",
  doi="10.4204/EPTCS.252.17",
  issn="2075-2180",
  url="https://arxiv.org/abs/1708.06467v1"
}