On the computational power of context-free PC grammar systems

DOI10.1016/S0304-3975(98)00159-5zbMath0939.68058OpenAlexW2001356001MaRDI QIDQ1566712

Niculae Mandache

Publication date: 4 June 2000

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00159-5

zbMATH Keywords

synchronizationparallel grammar systemssystem of diophantic equations

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

PC grammar systems with five context-free components generate all recursively enumerable languages., Parallel communicating grammar systems with context-free components are Turing complete for any communication model, On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms, Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts, On the computational completeness of context-free parallel communicating grammar systems

Cites Work

• Nonreturning PC grammar systems can be simulated by returning systems
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item