Result Details

Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

KŘIVKA, Z.; MEDUNA, A. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. FUNDAMENTA INFORMATICAE, 2021, vol. 179, no. 4, p. 361-384. ISSN: 0169-2968.
Type
journal article
Language
English
Authors
Křivka Zbyněk, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Abstract

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions.  It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Keywords

Scattered context grammars, size reduction, the number of non-context-free productions, parallel productions, computational completeness, descriptional complexity

Published
2021
Pages
361–384
Journal
FUNDAMENTA INFORMATICAE, vol. 179, no. 4, ISSN 0169-2968
DOI
10.3233/FI-2021-2028
UT WoS
000651794800003
EID Scopus
2-s2.0-85106764278
BibTeX 
@article{BUT162265,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete",
  journal="FUNDAMENTA INFORMATICAE",
  year="2021",
  volume="179",
  number="4",
  pages="361--384",
  doi="10.3233/FI-2021-2028",
  issn="0169-2968",
  url="https://www.fit.vut.cz/research/publication/11559/"
}
Files
Projects
Efficient Finite Automata for Automated Reasoning, MŠMT, ERC CZ, LL1908, start: 2020-01-01, end: 2024-12-31, completed
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, start: 2016-01-01, end: 2020-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top