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

communicating alternating machinessynchronized alternating machines

Mathematics Subject Classification ID

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

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

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

Cited in

(3)

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

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)