Deterministic versus nondeterministic space in terms of synchronized alternating machines

DOI10.1016/0304-3975(94)90238-0zbMath0821.68056OpenAlexW2055366844MaRDI QIDQ1334670

Juraj Hromkovič, Branislav Rovan, Anna Slobodová

Publication date: 25 September 1994

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

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

zbMATH Keywords

synchronized alternating machinesglobally deterministic synchronization

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

Synchronized tree automata ⋮ A communication hierarchy of parallel computations ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Complexity of E0L structural equivalence ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ A note on realtime one-way synchronized alternating one-counter automata ⋮ The generative capacity of block-synchronized context-free grammars ⋮ New results concerning synchronized finite automata ⋮ Decidability of equivalence for deterministic synchronized tree automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of synchronization in parallel computations
• One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages
• On the power of alternation in automata theory
• The method of forced enumeration for nondeterministic automata
• Alternating multihead finite automata
• Tradeoffs for language recognition on alternating machines
• Some properties of space-bounded synchronized alternating Turing machines with universal states only
• Communication for alternating machines
• A note on realtime one-way synchronized alternating one-counter automata
• One way multihead deterministic finite automata
• Nondeterministic Space is Closed under Complementation
• Alternation
• ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
• k + 1 Heads Are Better than k
• New results concerning synchronized finite automata
• On Multi-Head Finite Automata

This page was built for publication: Deterministic versus nondeterministic space in terms of synchronized alternating machines