On the power of synchronization in parallel computations

DOI10.1016/0166-218X(91)90098-HzbMath0734.68036OpenAlexW2007159761WikidataQ125259819 ScholiaQ125259819MaRDI QIDQ811118

Branislav Rovan, Anna Slobodová, Juhani Karhumäki, Juraj Hromkovič

Publication date: 1991

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90098-h

zbMATH Keywords

communication of parallel processesnondeterministic and deterministic space classessynchronized alternating machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (18)

Synchronized tree automata ⋮ Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ On communication-bounded synchronized alternating finite automata ⋮ The Communication Hierarchy of Time and Space Bounded Parallel Machines ⋮ A communication hierarchy of parallel computations ⋮ Complexity of EOL structural equivalence ⋮ WIRELESS MOBILE COMPUTING AND ITS LINKS TO DESCRIPTIVE COMPLEXITY ⋮ One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages ⋮ Complexity of E0L structural equivalence ⋮ Some properties of space-bounded synchronized alternating Turing machines with universal states only ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ An infinite hierarchy induced by depth synchronization ⋮ Communication for alternating machines ⋮ A note on realtime one-way synchronized alternating one-counter automata ⋮ The generative capacity of block-synchronized context-free grammars ⋮ On the synchronized derivation depth of context-free grammars ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ On Models of a Nondeterministic Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equivalence problem for deterministic two-tape automata
• Alternating multihead finite automata
• Tradeoffs for language recognition on alternating machines
• Multitape one-way nonwriting automata
• On some transducer equivalence problems for families of languages
• Alternation
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• k + 1 Heads Are Better than k
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications

This page was built for publication: On the power of synchronization in parallel computations