The Communication Hierarchy of Time and Space Bounded Parallel Machines

DOI10.1051/ITA:2003012MaRDI QIDQ4825478zbMATH OpenOpenAlexFDO

Authors Norbert Popély

Publication date 28 October 2004

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2003__37_2_159_0, http://www.numdam.org/item?id=ITA_2003__37_2_159_0/, https://eudml.org/doc/92720

zbMATH Keywords

synchronized alternating machinescommunicating alternating machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hierarchies of computability and definability (03D55) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• A communication hierarchy of parallel computations
• scientific article; zbMATH DE number 4060723
• On the power of synchronization in parallel computations
• Tradeoffs for language recognition on alternating machines
• On communication-bounded synchronized alternating finite automata

Cites work

• scientific article; zbMATH DE number 4130026 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• A communication hierarchy of parallel computations
• Alternation
• Communication for alternating machines
• On the power of synchronization in parallel computations
• Some properties of space-bounded synchronized alternating Turing machines with universal states only

Cited in

(2)

• Parallel communicating limited and uniformly limited 0L systems
• scientific article; zbMATH DE number 3938553 (Why is no real title available?)

This page was built for publication: The Communication Hierarchy of Time and Space Bounded Parallel Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4825478)