Publication result detail

General CD Grammar Systems and Their Simplification

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A.

Original Title

General CD Grammar Systems and Their Simplification

English Title

General CD Grammar Systems and Their Simplification

Type

Scopus Article

Original Abstract

The present paper studies general CD grammar systems, whose components are general grammars, so they are computationally complete, and it investigates them working under the * mode and t mode. Most importantly, the paper presents two types of transformations that turn arbitrary general grammars into equivalent two-component general CD grammar systems with a context-free component and a non-context-free component. From the first type of transformations, the non-context-free component results with two rules of the form 11->00 and 0000->epsilon, while the other type of transformations produces the non-context-free component with two rules of the form 11->00 and 0000->2222. Apart from this significant reduction and simplification, the paper describes several other useful properties concerning these systems and the way they work. A formulation of several remarks and open problems closes this paper.

English abstract

The present paper studies general CD grammar systems, whose components are general grammars, so they are computationally complete, and it investigates them working under the * mode and t mode. Most importantly, the paper presents two types of transformations that turn arbitrary general grammars into equivalent two-component general CD grammar systems with a context-free component and a non-context-free component. From the first type of transformations, the non-context-free component results with two rules of the form 11->00 and 0000->epsilon, while the other type of transformations produces the non-context-free component with two rules of the form 11->00 and 0000->2222. Apart from this significant reduction and simplification, the paper describes several other useful properties concerning these systems and the way they work. A formulation of several remarks and open problems closes this paper.

Keywords

general grammars, CD grammar systems, simulated non-context-free rules, homogeneous rules, evenly homogeneous rules

Key words in English

general grammars, CD grammar systems, simulated non-context-free rules, homogeneous rules, evenly homogeneous rules

Authors

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A.

RIV year

2021

Released

19.02.2020

ISBN

1430-189X

Periodical

Journal of Automata, Languages and Combinatorics

Volume

25

Number

1

State

Federal Republic of Germany

Pages from

37

Pages to

54

Pages count

18

URL

https://www.fit.vut.cz/research/publication/11509/

BibTex

@article{BUT162079,
  author="Radim {Kocman} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="General CD Grammar Systems and Their Simplification",
  journal="Journal of Automata, Languages and Combinatorics",
  year="2020",
  volume="25",
  number="1",
  pages="37--54",
  doi="10.25596/jalc-2020-037",
  issn="1430-189X",
  url="https://www.fit.vut.cz/research/publication/11509/"
}

Documents

Submission version
Printed version