Symmetric space-bounded computation
type: Item
instance of: scholarly article
title: Symmetric space-bounded computation
zbMATH Open document ID: 0491.68045
DOI: 10.1016/0304-3975(82)90058-5
author: Harry R. Lewis
author: Christos Papadimitriou
published in: Theoretical Computer Science
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03D40
zbMATH DE Number: 3772950
zbMATH Keywords: symmetric Turing machine
zbMATH Keywords: space symmetric classes
zbMATH Keywords: deterministic and nondeterministic classes
zbMATH Keywords: stack automata
zbMATH Keywords: symmetric complexity space class
zbMATH Keywords: space complexity classes
zbMATH Keywords: word problem for balanced Thue systems
zbMATH Keywords: space-time complexity classes
MaRDI profile type: Publication
Wikidata QID: Q55891641
full work available at URL: 0304-3975(82)90058-5
OpenAlex ID: W2039302045
cites work: Translational lemmas, polynomial time, and \((\log n)^j\)-space
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: The directed subgraph homeomorphism problem
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q4141219
cites work: Nonerasing stack automata
cites work: Q5592246
cites work: A Note Concerning Nondeterministic Tape Complexities
cites work: Space-bounded reducibility among combinatorial problems
cites work: New problems complete for nondeterministic log space
cites work: The subgraph homeomorphism problem
cites work: Q3915990
cites work: Recursive Unsolvability of a problem of Thue
cites work: Q5672171
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: A Polynomial Solution to the Undirected Two Paths Problem
DBLP publication ID: journals/tcs/LewisP82
description: scientific article; zbMATH DE number 3772950