Deterministic versus nondeterministic space in terms of synchronized alternating machines
type: Item
instance of: scholarly article
title: Deterministic versus nondeterministic space in terms of synchronized alternating machines
zbMATH Open document ID: 0821.68056
DOI: 10.1016/0304-3975(94)90238-0
author: Juraj Hromkovič
author: Branislav Rovan
author: Anna Slobodová
published in: Theoretical Computer Science
publication date: 1994-09-25T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 643679
zbMATH Keywords: synchronized alternating machines
zbMATH Keywords: globally deterministic synchronization
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)90238-0
OpenAlex ID: W2055366844
cites work: Alternation
cites work: Q3975141
cites work: Q3359749
cites work: Q5636862
cites work: One way multihead deterministic finite automata
cites work: On the power of alternation in automata theory
cites work: Tradeoffs for language recognition on alternating machines
cites work: A note on realtime one-way synchronized alternating one-counter automata
cites work: Q3982063
cites work: ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
cites work: On the power of synchronization in parallel computations
cites work: Q4266537
cites work: New results concerning synchronized finite automata
cites work: Nondeterministic Space is Closed under Complementation
cites work: Alternating multihead finite automata
cites work: On Multi-Head Finite Automata
cites work: k + 1 Heads Are Better than k
cites work: Q3795229
cites work: Communication for alternating machines
cites work: Some properties of space-bounded synchronized alternating Turing machines with universal states only
cites work: One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages
cites work: The method of forced enumeration for nondeterministic automata
cites work: Q3795617
cites work: Q3031934
Recommended article: On space-bounded synchronized alternating Turing machines
Recommended article: Q3782784
Recommended article: Some properties of space-bounded synchronized alternating Turing machines with universal states only
Recommended article: Q3681938
Recommended article: Q4449194
Recommended article: Determinism versus non-determinism for linear time RAMs (extended abstract)
Recommended article: Synchronizable deterministic pushdown automata and the decidability of their equivalence
Recommended article: Speedups of deterministic machines by synchronous parallel machines
Recommended article: Non-closure property of space-bounded two-dimensional alternating Turing machines
Recommended article: Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
description: scientific article; zbMATH DE number 643679