Alternating space is closed under complement and other simulations for sublogarithmic space
type: Item
instance of: scholarly article
title: Alternating space is closed under complement and other simulations for sublogarithmic space
zbMATH Open document ID: 1364.68215
author: Viliam Geffert
published in: Information and Computation
publication date: 2017-03-16T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 6695588
zbMATH Keywords: computational complexity
zbMATH Keywords: alternation
zbMATH Keywords: sublogarithmic space
MaRDI profile type: Publication
full work available at URL: j.ic.2017.02.001
OpenAlex ID: W2590387946
cites work: On the computational power of pushdown automata
cites work: The size-cost of Boolean operations on constant height deterministic pushdown automata
cites work: On languages accepted with simultaneous complexity bounds and their ranking problem
cites work: Q4846806
cites work: The alternation hierarchy for sublogarithmic space is infinite
cites work: Alternation
cites work: Space bounded computations: Review and new separation results
cites work: Inductive counting for width-restricted branching programs
cites work: Q3326840
cites work: A speed-up theorem without tape compression
cites work: A hierarchy that does not collapse : alternations in low level space
cites work: Bridging across the \(\log(n)\) space frontier
cites work: Sublogarithmic Bounds on Space and Reversals
cites work: UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)
cites work: Q5636862
cites work: Q5180413
cites work: One-tape, off-line Turing machine computations
cites work: A tradeoff theorem for space and reversal
cites work: Q4506483
cites work: Nondeterministic Space is Closed under Complementation
cites work: ${\text{ASPACE}}(o(\log \log n))$ is Regular
cites work: Nondeterminism is essential in small two-way finite automata with few reversals
cites work: Alternating Pushdown and Stack Automata
cites work: The Sublogarithmic Alternating Space World
cites work: Descriptional complexity of two-way pushdown automata with restricted head reversals
cites work: TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
cites work: On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Halting space-bounded computations
cites work: The method of forced enumeration for nondeterministic automata
cites work: Turing machines with sublogarithmic space
DOI: 10.1016/J.IC.2017.02.001
description: scientific article; zbMATH DE number 6695588