PC grammar systems with five context-free components generate all recursively enumerable languages.

DOI10.1016/S0304-3975(02)00852-6zbMath1042.68057OpenAlexW2092508863MaRDI QIDQ1874424

Erzsébet Csuhaj-Varjú, György Vaszil, Gheorghe Păun

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00852-6

zbMATH Keywords

Descriptional complexityRecursively enumerable languagesParallel communicating grammar systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (6)

REMARKS ON CONTEXT-FREE PARALLEL COMMUNICATING GRAMMAR SYSTEMS GENERATING CROSSED AGREEMENTS ⋮ Parallel communicating grammar systems with context-free components are Turing complete for any communication model ⋮ Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts ⋮ On the Number of Components and Clusters of Non-returning Parallel Communicating Grammar Systems ⋮ PC GRAMMAR SYSTEMS WITH CLUSTERS OF COMPONENTS ⋮ Improved descriptional complexity results on generalized forbidding grammars

Cites Work

• On the computational completeness of context-free parallel communicating grammar systems
• On the computational power of context-free PC grammar systems
• Parallel communicating grammar systems with bounded resources
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: PC grammar systems with five context-free components generate all recursively enumerable languages.