Publication Details

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

MEDUNA, A.; MARTIŠKO, J. CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages. In 15th International Conference on Automata and Formal Languages. Electronic Proceedings in Theoretical Computer Science, EPTCS. Debrecen: Open Publishing Association, 2017. p. 170-179. ISSN: 2075-2180.

Czech title

CD gramatické systémy se dvěma komponentami s rozptýleným kontextem bez epsilon pravidel popisují třídu kontextových jazyků

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Martiško Jakub, Ing.

URL

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

Keywords

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

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.

Published

2017

Pages

170–179

Journal

Electronic Proceedings in Theoretical Computer Science, EPTCS, vol. 2017, no. 252, ISSN 2075-2180

Proceedings

15th International Conference on Automata and Formal Languages

Publisher

Open Publishing Association

Place

Debrecen

DOI

10.4204/EPTCS.252.17

UT WoS

000439346000018

EID Scopus

2-s2.0-85030163581

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