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

DOI10.3233/FI-2021-2028OpenAlexW3163941704MaRDI QIDQ5164863

Alexander Meduna, Zbyněk Křivka

Publication date: 15 November 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2028

zbMATH Keywords

computational completenessdescriptional complexityscattered context grammarssize reductionparallel productionsthe number of non-context-free productions

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• On the generative power of regular pattern grammars
• On the descriptional complexity of scattered context grammars
• Generative power of three-nonterminal scattered context grammars
• Scattered context grammars
• Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
• Regulated Grammars and Automata

This page was built for publication: Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete