Detail výsledku

General CD Grammar Systems and Their Simplification

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A. General CD Grammar Systems and Their Simplification. Journal of Automata, Languages and Combinatorics, 2020, vol. 25, no. 1, p. 37-54. ISSN: 1430-189X.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Kocman Radim, Ing., Ph.D., UIFS (FIT)
Křivka Zbyněk, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

Rok
2020
Strany
37–54
Časopis
Journal of Automata, Languages and Combinatorics, roč. 25, č. 1, ISSN 1430-189X
DOI
10.25596/jalc-2020-037
EID Scopus
2-s2.0-85085293890
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/"
}
Soubory
Projekty
Centrum kompetence ve zpracování vizuálních informací (V3C - Visual Computing Competence Center), TAČR, Centra kompetence, TE01020415, zahájení: 2012-05-01, ukončení: 2019-12-31, ukončen
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, zahájení: 2016-01-01, ukončení: 2020-12-31, ukončen
Nástroje, metody a technologie ICT pro podporu konceptu smart cities, VUT, Vnitřní projekty VUT, FIT-S-17-3964, zahájení: 2017-03-01, ukončení: 2020-02-29, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru