A remark on middle space bounded alternating Turing machines
type: Item
instance of: scholarly article
title: A remark on middle space bounded alternating Turing machines
zbMATH Open document ID: 0875.68395
DOI: 10.1016/0020-0190(95)00151-2
author: Carlo Mereghetti
author: Giovanni Pighizzini
published in: Information Processing Letters
publication date: 1997-02-27T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 983971
zbMATH Keywords: Alternation
zbMATH Keywords: Computational complexity
zbMATH Keywords: Computational lower bounds
zbMATH Keywords: Formal languages
Wikidata QID: Q61677536
MaRDI profile type: Publication
full work available at URL: 0020-0190(95)00151-2
OpenAlex ID: W1984165512
cites work: Q3692869
cites work: Alternation
cites work: Space bounds for processing contentless inputs
cites work: Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
cites work: Some Results on Tape-Bounded Turing Machines
cites work: ${\text{ASPACE}}(o(\log \log n))$ is Regular
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Q5636862
cites work: Remarks on languages acceptable in log log n space
cites work: Turing machines with sublogarithmic space
Recommended article: On reversal bounded alternating Turing machines
Recommended article: Some observations concerning alternating Turing machines using small space
Recommended article: On space-bounded synchronized alternating Turing machines
Recommended article: On the power of alternation on reversal-bounded alternating Turing machines with a restriction
Recommended article: A note on alternating on-line Turing machines
Recommended article: Q4871672
Recommended article: Non-closure property of space-bounded two-dimensional alternating Turing machines
Recommended article: Q3692869
Recommended article: A note on alternating one-pebble Turing machines with sublogarithmic space
Recommended article: Q4723712
description: scientific article; zbMATH DE number 983971