Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
type: Item
instance of: scholarly article
title: Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
zbMATH Open document ID: 0684.68062
DOI: 10.1016/0020-0190(89)90158-0
author: Andrzej Szepietowski
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4121439
zbMATH Keywords: alternating hierarchy
zbMATH Keywords: complement
zbMATH Keywords: space complexity
zbMATH Keywords: nondeterminism
zbMATH Keywords: Turing machine
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90158-0
OpenAlex ID: W2061378925
cites work: Q3692869
cites work: Alternation
cites work: Erratum to: Some observations concerning alternating Turing machines using small space
cites work: Space bounds for processing contentless inputs
cites work: Q3912023
cites work: On tape bounds for single letter alphabet language processing
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q5180413
cites work: Q3309910
cites work: Halting space-bounded computations
cites work: Q5636862
cites work: The method of forced enumeration for nondeterministic automata
cites work: Remarks on languages acceptable in log log n space
cites work: If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
description: scientific article; zbMATH DE number 4121439