Some hierarchies for the communication complexity measures of cooperating grammar systems

DOI10.1016/0304-3975(94)90103-1zbMath0805.68043OpenAlexW1979814982WikidataQ62045986 ScholiaQ62045986MaRDI QIDQ1325838

Lila Kari, Jarkko Kari, Juraj Hromkovič

Publication date: 15 May 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90103-1

zbMATH Keywords

computational complexitycommunication complexitypumping lemmasdescriptional complexity measurelower-bound proof techniquesparallel communicating grammar systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Grammar systems: A grammatical approach to distribution and cooperation

Cites Work

• The impact of the number of cooperating grammars on the generative power
• Further remarks on parallel communicating grammar systems
• Systolic trellis automatata †
• Communicating sequential processes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item