Detail publikačního výsledku

Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete

HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.

Originální název

Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete

Anglický název

Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

The present paper explains how to reduce the size of scattered context grammars with respect to the number of both non-contextfree productions and nonterminals. It proves that every recursively enumerable language is generated by a six-nonterminal scattered context grammar with a single non-context-free production. Open problems are proposed.

Anglický abstrakt

The present paper explains how to reduce the size of scattered context grammars with respect to the number of both non-contextfree productions and nonterminals. It proves that every recursively enumerable language is generated by a six-nonterminal scattered context grammar with a single non-context-free production. Open problems are proposed.

Klíčová slova

Scattered context grammars, Size reduction, The number of non-context-free productions, The number of nonterminal symbols, Computational completeness, Descriptional complexity

Klíčová slova v angličtině

Scattered context grammars, Size reduction, The number of non-context-free productions, The number of nonterminal symbols, Computational completeness, Descriptional complexity

Autoři

HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.

Vydáno

22.07.2025

Nakladatel

Springer Verlag

Místo

Loughborough

ISBN

978-3-031-97099-3

Kniha

Descriptional Complexity of Formal Systems

Edice

Lecture Notes in Computer Science

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Svazek

15759

Číslo

7

Stát

Spolková republika Německo

Strany od

123

Strany do

136

Strany počet

13

URL

https://link.springer.com/book/10.1007/978-3-031-97100-6

BibTex

@inproceedings{BUT198282,
  author="Martin {Havel} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete",
  booktitle="Descriptional Complexity of Formal Systems",
  year="2025",
  series="Lecture Notes in Computer Science",
  journal="Lecture Notes in Computer Science",
  volume="15759",
  number="7",
  pages="123--136",
  publisher="Springer Verlag",
  address="Loughborough",
  doi="10.1007/978-3-031-97100-6\{_}9",
  isbn="978-3-031-97099-3",
  issn="0302-9743",
  url="https://link.springer.com/book/10.1007/978-3-031-97100-6"
}

Dokumenty

krivka_havel_meduna_dcfs2025_camera_ready