Publication result 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

English Title

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

Type

Paper in proceedings (conference paper)

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.

English 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,

Key words in English

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

Authors

MEDUNA, A.; MARTIŠKO, J.

RIV year

2018

Released

04.09.2017

Publisher

Open Publishing Association

Location

Debrecen

Book

15th International Conference on Automata and Formal Languages

ISBN

2075-2180

Periodical

Electronic Proceedings in Theoretical Computer Science, EPTCS

Volume

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

Documents

example
published_version