Detail výsledku
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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Abstrakt
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.
Klíčová slova
Scattered context grammars, size reduction, the number of non-context-free productions, parallel productions, computational completeness, descriptional complexity
Rok
2021
Strany
361–384
Časopis
FUNDAMENTA INFORMATICAE, roč. 179, č. 4, ISSN 0169-2968
DOI
UT WoS
000651794800003
EID Scopus
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/"
}
Soubory
Projekty
Efektivní konečné automaty pro automatické usuzování, MŠMT, ERC CZ, LL1908, zahájení: 2020-01-01, ukončení: 2024-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
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
Výzkumné skupiny
Pracoviště
Ústav informačních systémů
(UIFS)